学步园

序言

    非比较排序，不需要比较，交换，在线性时间内完成排序。缺点：空间要求较多，不是原地排序，典型的空间换取时间。

计数排序

    计数排序利用一个特点：已经排好序（例如从小到大）的数组中，第i个元素为x，则数组中一定有：小于等于x的元素有i个。计数排序需要一个空间代价：n + max_num.

桶排序

    桶排序包含两个步骤：分发元素到每个桶内；顺序回收桶内元素。伪代码如下：

BUCKET_SORT (A)

1. n
   ← length [A]
2. For i = 1 to n do
3.     Insert A[i] into list
   B[nA[i]]
4. For i = 0 to n-1 do
5.     Sort list B with Insertion sort
6. Concatenate the lists B[0], B[1], . . B[n-1] together in order.
   

代码实现

 #include <iostream><br /> #include <algorithm><br /> #include <limits><br /> #include <vector><br /> #include <ctime><br /> #include <cassert></p> <p>using namespace std;</p> <p>void BucketSort(int *array, int length)<br /> {<br /> const int MAX = 256;</p> <p> int bucket[MAX];</p> <p> for (unsigned int i(0); i<MAX; i++) bucket[i] = 0;</p> <p> for(unsigned int i=0; i<length; i++)<br /> bucket[array[i]]++;</p> <p> for(unsigned i=0, idx=0; i<MAX; i++)<br /> for(unsigned int k=bucket[i]; k>0; k--) // 回收每个桶内元素<br /> array[idx++] = i;<br /> }</p> <p>/** sort array values, store the results in dst array<br /> @param arr point to source array<br /> @param dst point to destinate array<br /> @param length the array size.<br /> @note Need O( N+Max_Num ) assistant space. space ==> time<br /> **/<br /> void counting_sort(int* arr, int* dst, int length)<br /> {<br /> const int max_num = 255;<br /> int count[max_num];</p> <p> for (int i(0); i<max_num; i++) count[i] = 0;</p> <p> for (int i(0); i<length; i++)<br /> count[ arr[i] ]++;</p> <p> for (int i(1); i<max_num; i++)<br /> count[i] += count[i-1];</p> <p> for (int i=length-1; i>=0; i--)<br /> {<br /> dst[ count[arr[i]]-1 ] = arr[i]; // 必须减一<br /> count[ arr[i] ]--;<br /> }<br /> }</p> <p>int main ()<br /> {<br /> #define P_2</p> <p>#ifdef P_1<br /> {<br /> int myints[] = {10,20,30,5,15};<br /> int length = sizeof(myints)/sizeof(myints[0]);<br /> int* result = new int[length];</p> <p> counting_sort(myints, result, length);</p> <p> for (int i(0); i<length; i++) cout << result[i] << " ";<br /> cout << endl;</p> <p> delete result; result = 0;<br /> }<br /> #endif // P_1</p> <p>#ifdef P_2<br /> {<br /> const int test_num = 10000000; // 1 million<br /> srand((int)time(0));</p> <p> cout << "Test number " << "/t:/t/t" << test_num << std::endl;</p> <p> int* testPtr = new int[test_num];<br /> int* testPtr1 = new int[test_num];<br /> int* testPtr2 = new int[test_num];</p> <p> for(int idx=0; idx<test_num; idx++)<br /> testPtr2[idx] = testPtr1[idx] = testPtr[idx] = rand()%255;</p> <p> clock_t t = clock();<br /> // sort<br /> // keep the testPtr1, change the testPtr.<br /> counting_sort(testPtr1, testPtr, test_num);<br /> cout << "count_sort " << "/t:/t/t" << clock() - t << std::endl;</p> <p> t = clock();<br /> BucketSort(testPtr1, test_num);<br /> cout << "BucketSort " << "/t:/t/t" << clock() - t << std::endl;</p> <p> t = clock();<br /> std::sort(testPtr2, testPtr2+test_num);<br /> cout << "std::sort " << "/t:/t/t" << clock() - t << std::endl;</p> <p> // Test the result validity<br /> for(int idx=0; idx<test_num; idx++)<br /> if (testPtr[idx]!=testPtr1[idx] || testPtr1[idx]!= testPtr2[idx])<br /> cout << "wrong";</p> <p> delete[] testPtr; testPtr = 0;<br /> delete[] testPtr1; testPtr1 = 0;<br /> delete[] testPtr2; testPtr2 = 0;<br /> }<br /> #endif // P_2</p> <p>#ifdef P_3<br /> #endif // P_3</p> <p> system("PAUSE");</p> <p> return 0;<br /> }

测试结果：

 Test number : 10000000<br /> count_sort : 112<br /> BucketSort : 70<br /> std::sort : 4646

计数和桶排序时间上的优势不用说了，但是这些非比较排序算法对空间要求比较高，而且跟排序数据的分布也有关。上面的测试结果是基于所有随机数据都在[0-255]之间的假设前提。数据分布越散乱，空间复杂度越高。

后记

桶排序的思路尤其适合字符串数组的排序，因为acsii字符都位于0，255之间。更加一般的桶排序可以使用链表，有时间再续吧~