基数排序：先按照最低位进行排序，然后对倒数第二位，以此类推。基于计数排序的基础上的一种排序方法。属于稳定排序，时间复杂度O（n），以空间换时间，需要额外的辅助空间。
计数排序：假设n个输入元素的每一个都是在0到k区间内的一个整数，其中k是一个整数。运行时间是O（n）.
计数排序的基本思想是：对每一个输入元素x,确定小于x的元素个数，从而，直接把x放在它输出数组中的位置。
计数排序伪代码：
CountingSort( A, B, k ) // A：输入数组； B输出数组；k 数组元素最大值
C[ k ] = { 0 }
for j = 1 to A.length
C[A[j]] = C[A[j]] + 1 // 统计数组中某一元素的个数
for i = 2 to k
C[ i ] = C[ i ] + C[ i - 1 ] // 计算数组中小于C[i] 的元素的个数
for j = A.length downto 1
B[ C[ A[ j ] ] ] = A[ j ] //注：在代码中，我在这里是先进行：C[A[j]] = C[A[j]] - 1 ， 然后 B[C[A[j]]] = A[j] 。C[A[j]] 的最大值是 A.length，会超出数组B的下标范围。
C[ A[ j ] ] = C[ A[ j ] ] - 1
计数排序代码：
#include<iostream> #include<vector> using namespace std; vector<int> CountingSort(vector<int>A,int Max,int Number) //参数： K，最大数值; Number 数组中元素个数 { int max = Max + 1; vector<int> B(Number); vector<int>C(max, 0); for (int i = 0; i < Number; i++) C[A[i]] ++; for (int i = 1; i < max; i++) C[i] += C[i - 1]; for (int j = Number - 1; j >= 0; j--) { C[A[j]]--; B[C[A[j]]] = A[j]; } return B; }
测试代码：
int main() { vector<int> arry = { 21, 97, 9, 1, 5, 8, 19, 4, 7, 10, 15, 17, 21, 41, 51, 61, 81, 71, 91, 100 }; cout << "排序前" << endl; for (int i = 0; i < 20; i++) cout << arry[i] << " "; cout << endl; int Max = 100; int Number = 20; vector<int>B = CountingSort(arry, Max, Number); for (int i = 0; i < 20; i++) cout << B[i] << " "; cout << endl; cout << "BigThink" << endl; system("pause"); return 0; }
基数排序：
RadixSort(A,d) // A 是输入数组，d是数组中最大值的位数
for i=1 to d
使用稳定排序法对A中数组的第 i位进行排序
基数排序代码：
#include<iostream> #include<vector> using namespace std; //求取输入输入的最大数字的位数 int GetInt(vector<int>A,int Number) //Number 输入数组个数 { int d = 1; int Max = A[0]; for (int i = 0; i < Number; i++) if (A[i]>Max) Max = A[i]; while (Max > 10) { Max = Max / 10; d++; } return d; } //基数排序法 vector<int> Radix_Sort(vector<int>A, int Number) //参数 d 最大元素值的位数,Number是数组中元素个数 { int d = GetInt(A, Number); vector<int>B(Number); int radix = 1; for (int i = 1; i <= d; i++) { vector<int> Arry(Number, 0); vector<int> C(10, 0); for (int j = 0; j < Number; j++) { Arry[j] = (A[j] / radix) % 10; C[Arry[j]]++; } for (int j = 1; j < 10; j++) C[j] += C[j - 1]; for (int j = Number - 1; j >= 0; j--) { B[C[Arry[j]]-1] = A[j]; C[Arry[j]]--; } for (int j = 0; j < Number; j++) A[j] = B[j]; radix = radix * 10; } return B; }
测试代码：
int main() { vector<int>arry = { 3, 7, 9, 14, 25, 52, 36, 78, 95, 28, 11, 32, 24, 250, 620, 140, 8, 91, 20,620 }; cout << "排序前" << endl; for (int i = 0; i < 20; i++) cout << arry[i] << " "; cout << endl; vector<int>B = Radix_Sort(arry, 20); cout << "排序后：" << endl; for (int i = 0; i < 20; i++) cout << B[i] << " "; cout << endl; cout << "BigThink" << endl; system("pause"); return 0; }
原文：http://www.cnblogs.com/hello-gogo/p/7107964.html
