快速排序 学习

今天学习了下排序算法 快速排序 实现了一下 ^^

排序100mb随机数 在我的古董记本上用了47秒 在台式机上只要15秒  hoho

 

#include "stdafx.h"

#define NUM 25 * 1024 * 1024

static void quick_sort_rec (int *list, int left, int right)
{
    int k = left;
    int i;
    int tmp;

#if 0
    printf ("left = %d right = %d\n", left, right);
    for (int j = 0; j < NUM; j ++)
        printf ("%d ", list[j]);
    printf ("\n------------------------------------\n");
#endif

    if (left >= right)
        return;
        
    for (i = left + 1; i <= right; i++) {
        if (list[i] < list[left]) {
            k++;
            tmp = list[i];
            list[i] = list[k];
            list[k] = tmp;    
        }
    }
    tmp = list[left];
    list[left] = list[k];
    list[k] = tmp;
    
    quick_sort_rec (list, left, k - 1);
    quick_sort_rec (list, k + 1, right);
}

void quick_sort (int *list, int size)
{
    quick_sort_rec (list, 0, size - 1);
}

int _tmain(int argc, _TCHAR* argv[])
{
    srand (::GetTickCount());
    
    int *list;
    list = (int *) malloc (NUM * sizeof (int));
    for (int i = 0; i < NUM; i ++)
        list[i] = rand () % (NUM * 3);
    
    LARGE_INTEGER pcount1;    
    QueryPerformanceCounter (&pcount1);
    
    quick_sort (list, NUM);
    
    LARGE_INTEGER pcount2;
    LARGE_INTEGER pfreq;
    QueryPerformanceCounter (&pcount2);
    QueryPerformanceFrequency (&pfreq);
    printf ("quick sort 100MB random data totally use %d ms \n", (pcount2.QuadPart - pcount1.QuadPart) * 1000 / pfreq.QuadPart);
    /*
    for (int i = 0; i < NUM; i ++)
        printf ("%d ", list[i]);
    */
    return 0;
}