排序算法，别让教育束缚你

zfzhuman123

实用排序算法（复杂度小于等于O(n^2)）中效率最低但实现并不是最简单的的两个，C、C++教材却总喜欢拿来大讲特讲，非常不利于初学者养成“程序效率”的思维。

实际上，各种排序算法里，除了堆排序实现较为复杂外，从代码量的角度，大多数算法都不比冒泡、选择算法复杂多少。

举几个高速的排序算法的例子，这些才适合进入教材

鸽巢排序，排序字节串、宽字节串最快的排序算法，计数排序的变种（将计数缓冲区大小固定，少一次遍历开销），速度是STL中std::sort的20多倍，更重要的是实现极其简单！缺点是需要一个size至少等于待排序数组取值范围的缓冲区，不适合int等大范围数据
C/C++ code

1. void PigeonholeSort(BYTE *array, int length)
   
2. {
   
3.     int b[256] = {0};
   
4.     int i,k,j = 0;
   
5.     for(i=0; i<length; i++)
   
6.         b[array[i]]++;
   
7.     for(i=0; i<256; i++)
   
8.         for(k=0; k<b[i]; k++)
   
9.             array[j++] = i;
   
10. }

复制代码

多一次遍历的计数排序，排序字节串的话速度约是鸽巢排序的一半
C/C++ code

1. void CountingSort(BYTE *array, int length)
   
2. {
   
3.     int t;
   
4.     int i, z = 0;
   
5.     BYTE min,max;
   
6.     int *count;
   
7.     min = max = array[0];
   
8.     for(i=0; i<length; i++)
   
9.     {
   
10.         if(array[i] < min)
    
11.             min = array[i];
    
12.         else if(array[i] > max)
    
13.             max = array[i];
    
14.     }
    
15.     count = (int*)malloc((max-min+1)*sizeof(int));
    
16.     for(i=0; i<max-min+1; i++)
    
17.         count[i] = 0;
    
18.     for(i = 0; i < length; i++)
    
19.         count[array[i]-min]++;
    
20. 
    
21.     for(t = 0; t <= 255; t++)
    
22.         for(i = 0; i < count[t-min]; i++)
    
23.             array[z++] = (BYTE)t;
    
24.     free(count);
    
25. }
    

复制代码

快速排序，快排最标准的递归实现，速度约是std::sort的一半
C/C++ code

1. void swap(BYTE *a,BYTE *b)
   
2. {
   
3.     BYTE tmp;
   
4.     if ( a != b )
   
5.     {
   
6.         tmp = *a;
   
7.         *a = *b;
   
8.         *b = tmp;
   
9.     }
   
10. }
    
11. 
    
12. int partition(BYTE *arr,int left, int right)
    
13. {
    
14.     int i = left - 1, j = right;
    
15.     BYTE v = arr[right];
    
16.     while(1)
    
17.     {
    
18.         while(arr[++i] < v);
    
19.         while(arr[--j] > v)
    
20.             if(j == 1)
    
21.                 break;
    
22.         if(i >= j)
    
23.             break;
    
24.         swap(&arr[i],&arr[j]);
    
25.     }
    
26.     swap(&arr[i],&arr[right]);
    
27.     return i;
    
28. }
    
29. 
    
30. void quicksort(BYTE *arr, int left, int right)
    
31. {
    
32.     if (left < right)
    
33.     {
    
34.         int i = partition(arr,left,right);
    
35. 
    
36.         quicksort(arr,left,i-1);
    
37.         quicksort(arr,i+1,right);
    
38.     }
    
39. }
    
40. 
    
41. void QuickSort(BYTE *array,int length)
    
42. {
    
43.     quicksort(array,0,length-1);
    
44. }
    
45. 
    
46. 
    

复制代码

这是速度与std::sort相当的三路划分快排
C/C++ code

1. void swap(BYTE *a,BYTE *b)
   
2. {
   
3.     BYTE tmp;
   
4.     if ( a != b )
   
5.     {
   
6.         tmp = *a;
   
7.         *a = *b;
   
8.         *b = tmp;
   
9.     }
   
10. }
    
11. 
    
12. void quicksort(BYTE *arr, int left, int right)
    
13. {
    
14.     if (left < right)
    
15.     {
    
16.         BYTE v = arr[right];
    
17.         int i = left - 1,j = right,p = left - 1,q = right,k=0;
    
18.         while (1)
    
19.         {
    
20.             while (arr[++i] < v);
    
21.             while (arr[--j] > v)
    
22.                 if(j==left)
    
23.                     break;
    
24.             if (i >= j)
    
25.                 break;
    
26.             swap(&arr[i], &arr[j]);
    
27.             if(arr[i] == v)
    
28.             {
    
29.                 p++;
    
30.                 swap(&arr[p],&arr[i]);
    
31.             }
    
32.             if(arr[j] == v)
    
33.             {
    
34.                 q--;
    
35.                 swap(&arr[q],&arr[j]);
    
36.             }
    
37.         }
    
38.         swap(&arr[i],&arr[right]);
    
39.         j = i - 1;
    
40.         i++;
    
41.         for(k=left; k<=p; k++,j--)
    
42.             swap(&arr[k],&arr[j]);
    
43.         for(k=right-1; k>=q; k--,i++)
    
44.             swap(&arr[k],&arr[i]);
    
45.         quicksort(arr,left,j);
    
46.         quicksort(arr,i,right);
    
47.     }
    
48. }
    
49. 
    
50. void QuickSort(BYTE *array,int length)
    
51. {
    
52.     quicksort(array,0,length-1);
    
53. }
    

复制代码

相当简单的梳排序，效率是std::sort的三分之一
C/C++ code

1. void CombSort(BYTE *arr, int size)
   
2. {
   
3.     UINT gap = size, swapped = 1, i = 0;
   
4.     BYTE swap = 0;
   
5.     while ((gap > 1) || swapped)
   
6.     {
   
7.         if (gap > 1)
   
8.             gap = gap / 1.3;
   
9.         swapped = 0;
   
10.         i = 0;
    
11.         while ((gap + i) < size)
    
12.         {
    
13.             if (arr[i] - arr[i + gap] > 0)
    
14.             {
    
15.                 swap = arr[i];
    
16.                 arr[i] = arr[i + gap];
    
17.                 arr[i + gap] = swap;
    
18.                 swapped = 1;
    
19.             }
    
20.             ++i;
    
21.         }
    
22.     }
    
23. }
    
24. 
    

复制代码

LSD基数排序，与std::sort速度相当，但是需要一个与输入缓冲一样大的缓冲区
C/C++ code

1. #define R 256
   
2. 
   
3. #define digit(a, d)    ( a >> 8*d )
   
4. 
   
5. static BYTE *aux;
   
6. 
   
7. void radix_sort(BYTE *arr, int left, int right)
   
8. {
   
9.     if(left < right)
   
10.     {
    
11.         int d = 0;
    
12.         for(d=3; d>=0; d--)
    
13.         {
    
14.             int i=0, j=0, count[R+1];
    
15.             for(j=0; j<R; j++)
    
16.                 count[j] = 0;
    
17.             for(i=left; i<=right; i++)
    
18.                 count[digit(arr[i],d) + 1]++;
    
19.             for(j=1; j<R; j++)
    
20.                 count[j] += count[j-1];
    
21.             for(i=left; i<=right; i++)
    
22.                 aux[count[digit(arr[i],d)]++] = arr[i];
    
23.             for(i=left; i<=right; i++)
    
24.                 arr[i] = aux[i-1];
    
25.         }   
    
26.     }
    
27. }
    
28. 
    
29. void RadixSort(BYTE *array,int length)
    
30. {
    
31.     aux = (BYTE*)malloc(length);
    
32.     radix_sort(array,0,length-1);
    
33.     free(aux);
    
34. }
    
35. 
    
36. 
    

复制代码

归并排序，效率越是std::sort的六分之一，通常的实现是递归，但和快排不同，归并改循环极其容易
C/C++ code

1. void merge(BYTE *array, int low, int mid, int high)
   
2. {
   
3.     int i, k;
   
4.     BYTE *temp = (BYTE *) malloc(high-low+1);
   
5.     int begin1 = low;
   
6.     int end1 = mid;
   
7.     int begin2 = mid + 1;
   
8.     int end2 = high;
   
9. 
   
10.     for (k = 0; begin1 <= end1 && begin2 <= end2; ++k)
    
11.         if(array[begin1]<array[begin2])
    
12.             temp[k] = array[begin1++];
    
13.         else
    
14.             temp[k] = array[begin2++];   
    
15.     while(begin1<=end1)
    
16.         temp[k++] = array[begin1++];
    
17.     while(begin2<=end2)
    
18.         temp[k++] = array[begin2++];
    
19.     for (i = 0; i < (high-low+1); i++)
    
20.         array[low+i] = temp[i];
    
21.     free(temp);
    
22. }
    
23. 
    
24. void merge_sort(BYTE *array, UINT first, UINT last)
    
25. {
    
26.     UINT mid,i;
    
27.     for(mid=1; mid<=last-first; mid += mid)
    
28.         for(i=first; i<=last-mid; i+=mid+mid)
    
29.             merge(array,i,i+mid-1,min(i+mid+mid-1,last));
    
30. }
    
31. 
    
32. void MergeSort(BYTE *array, UINT length)
    
33. {
    
34.     merge_sort(array,0,length-1);
    
35. }

复制代码

JX机械

先收藏下来。。。

我挖

看帖就要回帖支持下

fishmo

看看，支持下

hehex

确实不错，学习了。

Cocol

看看，回复支持下