处理海量数据的三大排序之——快速排序(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;
}

 

处理海量数据的三大排序之——快速排序(C++),古老的榕树,5-wow.com

郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。