#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;}