处理海量数据的三大排序之——快速排序(C++)
代码实现
#include "stdafx.h" #include <iostream> #include <ctime> using namespace std; int a[1000000]; int tempA[1000000]; #define BEGIN_RECORD \ { clock_t ____temp_begin_time___; ____temp_begin_time___=clock(); #define END_RECORD(dtime) \ dtime=float(clock()-____temp_begin_time___)/CLOCKS_PER_SEC;} /* 快速排序(挖坑填数) a - 待排序的数组 l - 排序区域的左边界 r - 排序区域的右边界 */ void quickSort(int a[], int l, int r) { if(l < r) //快排每次把一个数排到正确位置,便以此点把原排序区域细分为两个更小的排序区域。通过不断递归,当新的排序区域右边界不再大于左边界时,说明已不需要排序,则停止递归,排序完毕 { int i,j,x; i = l; j = r; x = a[i]; //选取排序区域左边第一个数作为本次排序的数 while(i < j) //该循环可称之为换坑过程,i,j相当于左右两边坑的位置,当右边坑位置不再大于左边坑位置时(此时两坑位置必定相同),说明已比较到中点,结束换坑过程 { while(i < j && x < a[j]) //从右向左找小于x的值 { j--; } if(i < j) //找过后就将其换到左边第1个位置,下一次则填入左边第2个位置,以此类推 { a[i++] = a[j]; } while(i < j && x > a[i]) //从左向右找大于x的值 { i++; } if(i < j) //找到后将其填入右边第1个位置,下一次则填入右边第2个位置,以此类推 { a[j--] = a[i]; } } a[i] = x; //当换坑过程结束后,在i位置以左的值都小于x,i位置以右的值都大于x,说明x找到了正确的位置,将x值填入(填坑过程) //将x值位置以左,以右分为两个新的排序区域,重复换坑填坑的过程 quickSort(a, l, i-1); quickSort(a, i+1, r); } } void printArray(int a[], int length) { cout << "数组内容:"; for(int i = 0; i < length; i++) { if(i == 0) cout << a[i]; else cout << "," << a[i]; } cout << endl; } int _tmain(int argc, _TCHAR* argv[]) { float tim; for (int i = 0; i < 1000000; i++) { a[i] = int(rand() % 100000); } BEGIN_RECORD //printArray(a, sizeof(a)/sizeof(int)); quickSort(a, 0, sizeof(a)/sizeof(int) - 1); //printArray(a, sizeof(a)/sizeof(int)); END_RECORD(tim) cout << "运行时间:" << tim << "s" << endl; system("pause"); return 0; }
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。