算法和数据结构排序线性时间排序

计数排序

#include <iostream> 
#include <iomanip> 
#include <time.h> 
#include <stdlib.h> 
#define MIN -65536 
using namespace std;

int * Create_Array (int *, int, int); 
void Print_Array (int *, int); 
int * Count_Sort (int *, int *, int *, int, int);

int main (void) 
{ 
 int *Array = NULL, *B_Array = NULL, *C_Array = NULL; 
 int max, num; 
 cout << "生成随机数个数："; 
 cin >> num; 
 cout << "随机数最大值为："; 
 cin >> max; 
 cout << endl; 
 Array = Create_Array (Array, num + 1, max); 
 cout << "排序前：" << endl; 
 Print_Array (Array, num + 1); 
 cout << endl; 
 cout << "排序后：" << endl; 
 B_Array = Count_Sort (Array, B_Array, C_Array, max + 2, num + 1); 
 Print_Array (B_Array, num + 1); 
 cout << endl; 
 return 0; 
}

int * Create_Array (int * Array, int num, int max) 
{ 
 Array = new int [num]; 
 Array[0] = MIN; 
 srand ((unsigned)time (NULL)); 
 for (int i = 1; i < num; ++ i) 
  Array[i] = rand() % max + 1; 
 return Array; 
}

void Print_Array (int *Array, int num) 
{ 
 int count = 0; 
 for (int i = 1; i < num; ++ i) 
 { 
  cout << setw(7) << Array[i]; 
  ++ count; 
  if (count % 10 == 0) 
   cout << endl; 
 } 
}

int * Count_Sort (int *Array, int *B_Array, int *C_Array, int k, int num) 
{ 
 B_Array = new int [num]; 
 C_Array = new int [k]; 
 B_Array[0] = MIN; 
 for (int i = 0; i < k; ++ i) 
  C_Array[i] = 0; 
 for (int j = 1; j < num; ++ j) 
  C_Array[Array[j]] = C_Array[Array[j]] + 1; 
 for (int i = 1; i < k; ++ i) 
  C_Array[i] = C_Array[i] + C_Array[i - 1]; 
 for (int j = num - 1; j > 0; -- j) 
 {  
  B_Array[C_Array[Array[j]]] = Array[j]; 
  C_Array[Array[j]] = C_Array[Array[j]] - 1; 
 } 
 delete []C_Array; 
 return B_Array; 
}

 基数排序

RADIX-SORT(A,d)
{
for i=[1,d]
do counting-sort on digit i for array A;
}

 桶排序

简单来说，就是把数据分组，放在一个个的桶中，然后对每个桶里面的在进行排序。

例如要对大小为[1..1000]范围内的n个整数A[1..n]排序。可以把桶设为大小为10的范围，具体而言，设集合B[1]存储[1..10]的整数，集合B[2]存储(10..20]的整数，……集合B[i]存储( (i-1)*10, i*10]的整数，i = 1,2,..100。总共有100个桶。然后对A[1..n]从头到尾扫描一遍，把每个A[i]放入对应的桶B[j]中。

然后再对这100个桶中每个桶里的数字排序，这时可用冒泡，选择，乃至快排，一般来说任何排序法都可以。

最后依次输出每个桶里面的数字，且每个桶中的数字从小到大输出，这样就得到所有数字排好序的一个序列了。