Chinaunix首页 | 论坛 | 博客
  • 博客访问: 69844
  • 博文数量: 20
  • 博客积分: 1400
  • 博客等级: 上尉
  • 技术积分: 402
  • 用 户 组: 普通用户
  • 注册时间: 2006-10-08 17:53
文章分类

全部博文(20)

文章存档

2010年(6)

2009年(2)

2008年(8)

2006年(4)

我的朋友
最近访客

分类: C/C++

2008-12-10 13:03:09

今天学习了下排序算法 快速排序 实现了一下 ^^
排序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;
}

 

 

阅读(1237) | 评论(0) | 转发(1) |
0

上一篇:MoonDict 0.1 英汉词典

下一篇:自杀代码!!

给主人留下些什么吧!~~