[原创]各种排序方法总结【2008年7月7日更新】(页 1) - C语言论坛 - 编程论坛

StarWing83 发表于 2008-5-10 15:57

[原创]各种排序方法总结【2008年7月7日更新】

代码全部重新编写，去掉了一些很dirty的地方，并增加了几种排序方法。
现在一共收录了插入，选择，冒泡，归并，希尔，堆排，快排，计数等八种常用的排序方法，并做了效率比较，其中对1万个随机数排序使用了所有的方法，而对100万个随机数排序则只使用了后五种高级排序，因为对于简单排序，速度已经慢得难以忍受了……有耐心的朋友倒是可以等等，看看究竟需要多少时间。

[bo]五月14日更新了归并排序，按照飞燕的提示只分配了一个数组，速度快了近一倍！虽然还是没有超过希尔排序:)[/bo]

每个排序都经过简单的测试，如果发现有实现错误导致产生错误的结果，请跟帖反映，不胜感激~~~~
在我的电脑上运行如下（Athron64x2 3600+，2G内存，Vista操作系统，GCC编译器）:[code]
一万个数字对所有排序的测试：
InsertSort Use time:31ms
SelectSort Use time:100ms
BubbletSort Use time:222ms
CountSort Use time:0ms
QuickSort Use time:1ms
HeapSort Use time:1ms
ShellSort Use time:2ms
MergeSort Use time:5ms

100万个数字，对高级排序的测试：
CountSort Use time:9ms
QuickSort Use time:135ms
HeapSort Use time:354ms
ShellSort Use time:570ms
MergeSort Use time:609ms
请按任意键继续. . .
[/code]下面是源代码：
[quote][font=新宋体][size=2][color=#008000]/*****************************************************************
** HighlightCodeV3.0 software by yzfy(雨中飞燕) [url]http://yzfy.org[/url] **
*****************************************************************/
[/color][color=#FF0000]#include <ctime>
[/color][color=#FF0000]#include <iostream>
[/color][color=#0000FF]using namespace [/color][color=#FF0000]std[/color];

[color=#FF0000]#define [/color][color=#800080]SWAP[/color](i,j) [color=#800000]{[/color][color=#0000FF]int [/color]t=(i);(i)=(j);(j)=t;[color=#800000]}

[/color][color=#008000]//插入排序
[/color][color=#0000FF]void [/color][color=#008080]InsertSort[/color]([color=#0000FF]int[/color]*a,[color=#0000FF]int [/color]len)
[color=#800000]{
[/color][color=#0000FF]for [/color]([color=#0000FF]int [/color]i=[color=#800080]1[/color];i<len;i++)
[color=#800000]{
      [/color][color=#0000FF]int [/color]j=i,x=a[color=#800000][[/color]i[color=#800000]][/color];
      [color=#0000FF]while [/color](j && a[color=#800000][[/color]j-[color=#800080]1[/color][color=#800000]][/color]>x)a[color=#800000][[/color]j[color=#800000]][/color]=a[color=#800000][[/color]j-[color=#800080]1[/color][color=#800000]][/color],j--;
      a[color=#800000][[/color]j[color=#800000]][/color]=x;
[color=#800000]}
}

[/color][color=#008000]//选择排序
[/color][color=#0000FF]void [/color][color=#008080]SelectSort[/color]([color=#0000FF]int[/color]*a,[color=#0000FF]int [/color]len)
[color=#800000]{
[/color][color=#0000FF]for [/color]([color=#0000FF]int [/color]i=[color=#800080]1[/color],j,k;i<len;i++)
[color=#800000]{
      [/color][color=#0000FF]for [/color](j=i,k=i-[color=#800080]1[/color];j<len;j++)
         [color=#0000FF]if [/color](a[color=#800000][[/color]j[color=#800000]][/color]<a[color=#800000][[/color]k[color=#800000]][/color])k=j;
      [color=#0000FF]if [/color](k>=i)[color=#800080]SWAP[/color](a[color=#800000][[/color]i-[color=#800080]1[/color][color=#800000]][/color],a[color=#800000][[/color]k[color=#800000]][/color]);
[color=#800000]}
}

[/color][color=#008000]//冒泡排序
[/color][color=#0000FF]void [/color][color=#008080]BubbletSort[/color]([color=#0000FF]int[/color]*a,[color=#0000FF]int [/color]len)
[color=#800000]{
[/color][color=#0000FF]for [/color]([color=#0000FF]bool [/color]bSwap=true;bSwap;len--)
[color=#800000]{
      [/color]bSwap=false;
      [color=#0000FF]for [/color]([color=#0000FF]int [/color]j=[color=#800080]1[/color];j<len;j++)
         [color=#0000FF]if [/color](a[color=#800000][[/color]j-[color=#800080]1[/color][color=#800000]][/color]>a[color=#800000][[/color]j[color=#800000]][/color])[color=#800000]{[/color][color=#800080]SWAP[/color](a[color=#800000][[/color]j-[color=#800080]1[/color][color=#800000]][/color],a[color=#800000][[/color]j[color=#800000]][/color]);bSwap=true;[color=#800000]}
}
}

[/color][color=#008000]//计数排序
[/color][color=#0000FF]void [/color][color=#008080]CountSort[/color]([color=#0000FF]int[/color]*a,[color=#0000FF]int [/color]len)
[color=#800000]{
[/color][color=#0000FF]int [/color]c[color=#800000][[/color][color=#800080]RAND_MAX[/color]+[color=#800080]1[/color][color=#800000]][/color]=[color=#800000]{[/color][color=#800080]0[/color][color=#800000]}[/color];
[color=#0000FF]for [/color]([color=#0000FF]int [/color]i=[color=#800080]0[/color];i<len;i++)c[color=#800000][[/color]a[color=#800000][[/color]i[color=#800000]]][/color]++;
[color=#0000FF]for [/color]([color=#0000FF]int [/color]i=[color=#800080]RAND_MAX[/color];i>=[color=#800080]0[/color];)
         [color=#0000FF]if [/color](c[color=#800000][[/color]i[color=#800000]][/color])a[color=#800000][[/color]--len[color=#800000]][/color]=i,c[color=#800000][[/color]i[color=#800000]][/color]--; [color=#0000FF]else [/color]i--;
[color=#800000]}

[/color][color=#008000]//堆调整
[/color][color=#0000FF]void [/color][color=#008080]HeapAdjust[/color]([color=#0000FF]int [/color]*a,[color=#0000FF]int [/color]root,[color=#0000FF]int [/color]len)
[color=#800000]{
[/color][color=#0000FF]int [/color]child,x=a[color=#800000][[/color]root[color=#800000]][/color];
[color=#0000FF]while [/color](child=root<<[color=#800080]1[/color]|[color=#800080]1[/color],child<len)
[color=#800000]{
      [/color][color=#0000FF]if [/color](child<len-[color=#800080]1 [/color]&& a[color=#800000][[/color]child[color=#800000]][/color]<a[color=#800000][[/color]child+[color=#800080]1[/color][color=#800000]][/color])child++;
      [color=#0000FF]if [/color](x<a[color=#800000][[/color]child[color=#800000]][/color])[color=#800000]{[/color]a[color=#800000][[/color]root[color=#800000]][/color]=a[color=#800000][[/color]child[color=#800000]][/color];root=child;[color=#800000]}
      [/color][color=#0000FF]else break[/color];
[color=#800000]}
[/color]a[color=#800000][[/color]root[color=#800000]][/color]=x;
[color=#800000]}

[/color][color=#008000]//堆排序
[/color][color=#0000FF]void [/color][color=#008080]HeapSort[/color]([color=#0000FF]int[/color]*a,[color=#0000FF]int [/color]len)
[color=#800000]{
[/color][color=#0000FF]for [/color]([color=#0000FF]int [/color]i=len/[color=#800080]2[/color]-[color=#800080]1[/color];i>=[color=#800080]0[/color];i--)
      [color=#008080]HeapAdjust[/color](a,i,len);
[color=#0000FF]while [/color](--len)
[color=#800000]{
      [/color][color=#800080]SWAP[/color](a[color=#800000][[/color][color=#800080]0[/color][color=#800000]][/color],a[color=#800000][[/color]len[color=#800000]][/color]);
      [color=#008080]HeapAdjust[/color](a,[color=#800080]0[/color],len);
[color=#800000]}
}

[/color][color=#008000]//归并
[/color][color=#0000FF]void [/color][color=#008080]Merge[/color]([color=#0000FF]int[/color]*a,[color=#0000FF]int [/color]center,[color=#0000FF]int [/color]len)
[color=#800000]{
[/color][color=#0000FF]int [/color]*tmp=[color=#0000FF]new int[/color][color=#800000][[/color]len+[color=#800080]2[/color][color=#800000]][/color];
[color=#0000FF]for [/color]([color=#0000FF]int [/color]i=[color=#800080]0[/color];i<center;i++)tmp[color=#800000][[/color]i[color=#800000]][/color]=a[color=#800000][[/color]i[color=#800000]][/color];
[color=#0000FF]for [/color]([color=#0000FF]int [/color]i=center+[color=#800080]1[/color];i<=len;i++)tmp[color=#800000][[/color]i[color=#800000]][/color]=a[color=#800000][[/color]i-[color=#800080]1[/color][color=#800000]][/color];
tmp[color=#800000][[/color]center[color=#800000]][/color]=tmp[color=#800000][[/color]len+[color=#800080]1[/color][color=#800000]][/color]=[color=#800080]INT_MAX[/color];
[color=#0000FF]for [/color]([color=#0000FF]int [/color]i=[color=#800080]0[/color],j=center+[color=#800080]1[/color],k=[color=#800080]0[/color];k<len;k++)
      a[color=#800000][[/color]k[color=#800000]][/color]=tmp[color=#800000][[/color](tmp[color=#800000][[/color]i[color=#800000]][/color]<tmp[color=#800000][[/color]j[color=#800000]][/color]?i:j)++[color=#800000]][/color];
[color=#0000FF]delete[/color][color=#800000][] [/color]tmp;
[color=#800000]}

[/color][color=#008000]//归并排序
[/color][color=#0000FF]void [/color][color=#008080]MergeSort[/color]([color=#0000FF]int[/color]*a,[color=#0000FF]int [/color]len)
[color=#800000]{
[/color][color=#0000FF]if [/color](len>[color=#800080]1[/color])
[color=#800000]{
      [/color][color=#0000FF]int [/color]c=len/[color=#800080]2[/color];
      [color=#008080]MergeSort[/color](a,c);
      [color=#008080]MergeSort[/color](a+c,len-c);
      [color=#008080]Merge[/color](a,c,len-c);
[color=#800000]}
}

[/color][color=#008000]//划分
[/color][color=#0000FF]int [/color][color=#008080]Partition[/color]([color=#0000FF]int[/color]*a,[color=#0000FF]int [/color]len)
[color=#800000]{
[/color][color=#0000FF]int [/color]x=a[color=#800000][[/color]--len[color=#800000]][/color],i=-[color=#800080]1[/color];
[color=#0000FF]for [/color]([color=#0000FF]int [/color]j=[color=#800080]0[/color];j<len;j++)
      [color=#0000FF]if [/color](a[color=#800000][[/color]j[color=#800000]][/color]<x)[color=#800000]{[/color]i++;[color=#800080]SWAP[/color](a[color=#800000][[/color]i[color=#800000]][/color],a[color=#800000][[/color]j[color=#800000]][/color]);[color=#800000]}
[/color][color=#800080]SWAP[/color](a[color=#800000][[/color]i+[color=#800080]1[/color][color=#800000]][/color],a[color=#800000][[/color]len[color=#800000]][/color]);
[color=#0000FF]return [/color]i+[color=#800080]1[/color];
[color=#800000]}

[/color][color=#008000]//快速排序
[/color][color=#0000FF]void [/color][color=#008080]QuickSort[/color]([color=#0000FF]int[/color]*a,[color=#0000FF]int [/color]len)
[color=#800000]{
[/color][color=#0000FF]if [/color](len > [color=#800080]0[/color])
[color=#800000]{
      [/color][color=#0000FF]int [/color]q=[color=#008080]Partition[/color](a,len);
      [color=#0000FF]if [/color](q<len-q)
      [color=#800000]{
         [/color][color=#008080]QuickSort[/color](a,q);
         [color=#008080]QuickSort[/color](a+q+[color=#800080]1[/color],len-q-[color=#800080]1[/color]);
      [color=#800000]}
      [/color][color=#0000FF]else
      [/color][color=#800000]{
         [/color][color=#008080]QuickSort[/color](a+q+[color=#800080]1[/color],len-q-[color=#800080]1[/color]);
         [color=#008080]QuickSort[/color](a,q);
      [color=#800000]}
}
}

[/color][color=#008000]//希尔插入
[/color][color=#0000FF]void [/color][color=#008080]ShellInsert[/color]([color=#0000FF]int[/color]*a,[color=#0000FF]int [/color]inc,[color=#0000FF]int [/color]len)
[color=#800000]{
[/color][color=#0000FF]for [/color]([color=#0000FF]int [/color]i=inc;i<len;i+=inc)
[color=#800000]{
      [/color][color=#0000FF]int [/color]j=i,x=a[color=#800000][[/color]i[color=#800000]][/color];
      [color=#0000FF]while [/color](j>[color=#800080]0 [/color]&& a[color=#800000][[/color]j-inc[color=#800000]][/color]>x)a[color=#800000][[/color]j[color=#800000]][/color]=a[color=#800000][[/color]j-inc[color=#800000]][/color],j-=inc;
      a[color=#800000][[/color]j[color=#800000]][/color]=x;
[color=#800000]}
}

[/color][color=#008000]//插入式希尔排序
[/color][color=#0000FF]void [/color][color=#008080]ShellSort[/color]([color=#0000FF]int[/color]*a,[color=#0000FF]int [/color]len)
[color=#800000]{
[/color][color=#0000FF]int [/color]inc=len;
[color=#0000FF]do
[/color][color=#800000]{
      [/color]inc=inc/[color=#800080]3[/color]+[color=#800080]1[/color];
      [color=#0000FF]for [/color]([color=#0000FF]int [/color]s=[color=#800080]0[/color];s<inc;s++)
         [color=#008080]ShellInsert[/color](a-s,inc,len+s);
[color=#800000]}
[/color][color=#0000FF]while [/color](inc>[color=#800080]1[/color]);
[color=#800000]}

[/color][color=#FF0000]#define [/color][color=#800080]N 1000000
[/color][color=#FF0000]#define [/color][color=#008080]SortTest[/color]([color=#FF8000]sort[/color],len) [color=#800080]\
[/color][color=#0000FF]do [/color][color=#800000]{ [/color][color=#800080]\
      [/color][color=#0000FF]for[/color]([color=#0000FF]int [/color]i=[color=#800080]0[/color];i<len;i++)a[color=#800000][[/color]i[color=#800000]][/color]=s[color=#800000][[/color]i[color=#800000]][/color]; [color=#800080]\
      [/color]clock_t t=[color=#008080]clock[/color](); [color=#800080]\
      [/color][color=#FF8000]sort[/color](a,len); [color=#800080]\
      [/color][color=#FF0000]printf[/color]([color=#FF0000]#sort[/color][color=#FF00FF]" Use time:%ldms\n"[/color],[color=#008080]clock[/color]()-t); [color=#800080]\
[/color][color=#800000]}[/color][color=#0000FF]while[/color](false)

[color=#0000FF]int [/color]a[color=#800000][[/color][color=#800080]N[/color][color=#800000]][/color],s[color=#800000][[/color][color=#800080]N[/color][color=#800000]][/color];

[color=#0000FF]int [/color][color=#FF0000]main[/color]()
[color=#800000]{
[/color][color=#008080]srand[/color](([color=#0000FF]unsigned[/color])[color=#008080]time[/color]([color=#800080]NULL[/color]));
[color=#0000FF]for [/color]([color=#0000FF]int [/color]i=[color=#800080]0[/color];i<[color=#800080]N[/color];i++)s[color=#800000][[/color]i[color=#800000]][/color]=[color=#008080]rand[/color]();

[color=#FF0000]printf[/color]([color=#FF00FF]"一万个数字对所有排序的测试：\n"[/color]);
[color=#008080]SortTest[/color](InsertSort,[color=#800080]10000[/color]);
[color=#008080]SortTest[/color](SelectSort,[color=#800080]10000[/color]);
[color=#008080]SortTest[/color](BubbletSort,[color=#800080]10000[/color]);
[color=#008080]SortTest[/color](CountSort,[color=#800080]10000[/color]);
[color=#008080]SortTest[/color](QuickSort,[color=#800080]10000[/color]);
[color=#008080]SortTest[/color](HeapSort,[color=#800080]10000[/color]);
[color=#008080]SortTest[/color](ShellSort,[color=#800080]10000[/color]);
[color=#008080]SortTest[/color](MergeSort,[color=#800080]10000[/color]);

[color=#FF0000]printf[/color]([color=#FF00FF]"\n100万个数字，对高级排序的测试：\n"[/color]);
[color=#008080]SortTest[/color](CountSort,[color=#800080]N[/color]);
[color=#008080]SortTest[/color](QuickSort,[color=#800080]N[/color]);
[color=#008080]SortTest[/color](HeapSort,[color=#800080]N[/color]);
[color=#008080]SortTest[/color](ShellSort,[color=#800080]N[/color]);
[color=#008080]SortTest[/color](MergeSort,[color=#800080]N[/color]);

[color=#0000FF]return [/color][color=#800080]0[/color];
[color=#800000]}[/color][/size][/font][/quote]

[[it] 本帖最后由 StarWing83 于 2008-7-7 17:46 编辑 [/it]]

中学者 发表于 2008-5-10 16:04

顶一个.........

中学者 发表于 2008-5-10 16:04

看了你的qsort又学习了////

zjl138 发表于 2008-5-10 16:05

支持一下，可否让我把代码搬回家[tk03]

zjl138 发表于 2008-5-10 16:07

我也要做一下总结才行了。

StarWing83 发表于 2008-5-10 16:15

现在快排已经改好了，使用的是CLRS上的方法……沮丧……
希尔排序使用的是中学者的递进方法，我原先使用是inc[k]=2^(len-k+1)+1的方法，但是发现没有中学者的快……Orz……
不打算写基数排序了。在不使用STL数据结构的情况下空间复杂度为O(d*n+k)，对于n=10^6的规模无法忍受……

[[it] 本帖最后由 StarWing83 于 2008-5-12 04:08 编辑 [/it]]

走一圈 发表于 2008-5-10 16:26

辛苦了顶你个[tk05] [tk05]

中学者 发表于 2008-5-10 16:28

Star兄，没有基数排???

sunkaidong 发表于 2008-5-10 16:32

翅膀你的电脑好好啊...我测试下...我好像要26****ms..学校机器太破啊...[tk01]

雨中飛燕 发表于 2008-5-10 16:32

好像没写Shell-Insert

[img]http://blog.programfan.com/upfile/200804/20080430094836.gif[/img][color=white]

StarWing83 发表于 2008-5-10 16:41

Orz已经晕了……早饭+午饭都没吃……撑不住了……出去吃饭了回来再看…………

StarWing83 发表于 2008-5-10 16:43

晚上来补完！！[tk03]

sunkaidong 发表于 2008-5-10 16:47

我都是让同学帮带的..呵呵[tk05]

菜鸟选手 发表于 2008-5-10 18:28

帖子顶起再看 .！
收回去了 , 呵呵 ,给出原创链接！

卧龙孔明 发表于 2008-5-10 18:37

qsort怎么在递归中写随机划分啊（在一个函数中，不要两个函数的）？
我只会先将数组中的元素随机乱序一下，曾经试过在递归函数中写随机划分，总是有问题

中学者 发表于 2008-5-10 18:39

看算法导论吧，上面好像有，不过我跳过没看....[tk03]

卧龙孔明 发表于 2008-5-10 18:39

我的qsort(随机乱序输入的数据，从而使之趋向于平衡）
void sort(int low,int high,int key[])
{
   int i,j,tag;
   i=low; j=high;
   if(i<j)
   {
   tag=key[i];
   do
   {
      while(tag<key[j] && i<j) j--;
      if(i<j)
      {
            key[i]=key[j];
            i++;
            while(tag>=key[i] && i<j) i++;
            if(i<j)
            {
                     key[j]=key[i];
                     j--;
            }
      }
   }while(i<j);
   key[i]=tag;
   sort(low,j-1,key);
   sort(i+1,high,key);
   }
}
int main(void)
{
int i,tmp[3];
int n;
int key[200000];
scanf("%d",&n);
for(i=0;i<n;i++) scanf("%d",&key[i]);
for(i=n/2;i<n;i++)
{
   tmp[0]=((rand()<<4)+rand())%n;
   tmp[1]=((rand()<<4)+rand())%n;
   tmp[2]=key[tmp[0]];
   key[tmp[0]]=key[tmp[1]];
   key[tmp[1]]=tmp[2];
}
sort(0,n-1,key);
for(i=0;i<n;i++)
{
   printf("%d ",key[i]);
}
printf("\n");
return 0;
}

StarWing83 发表于 2008-5-10 21:52

Orz....居然睡着了，一觉醒来发现十点了………………
那个，希尔我有种简单的解决方法，可以很轻松搞定。
基数按复杂度看似乎没有桶排快。而且很难写。我准备看看再说，看来我背着写也就这水平了。明天翻了算法导论再来补完。
快排的高效版的划分没头绪。我算了下，原来的想法是错误的。反而会降低效率，所以决定舍弃原来那种，改用算法导论上面的……Orz算法导论是交换为主啊……那么效率……
不管了……推到明天吧，累死了……

StarWing83 发表于 2008-5-10 21:55

孔明啊……我想要短小精悍的划分代码……555……

卧龙孔明 发表于 2008-5-11 09:16

[quote][bo]以下是引用 [un]StarWing83[/un] 在 2008-5-10 21:55 的发言：[/bo]

孔明啊……我想要短小精悍的划分代码……555…… [/quote]
貌似如果数据是随机的，那么我上面发的那个快排函数比大部分人写的（网上流传的）要快1/4，而且也比较简洁。
就是不知道怎么样把这个函数改成随机划分的

页: [1] 2 3

编程论坛's Archiver

[原创]各种排序方法总结【2008年7月7日更新】