计数排序，基数排序，桶排序

//CountingSort.cpp

void CountingSort(int arrSrc[],int arrDst[],int arrLength,int upperLimit)

{

int* arrCount = new int[upperLimit+1];

 

for(int i=0;i<=upperLimit;i++)//初始化arrCount

arrCount[i] = 0;

 

for(int i=0;i<arrLength;i++)//arrCount[i]记录arrSrc[]中等于i的元素个数

arrCount[arrSrc[i]] += 1;

 

for(int i=1;i<=upperLimit;i++)//arrCount[i]记录arrSrc[]中小于等于i的元素个数

arrCount[i] += arrCount[i-1];

 

for(int i=arrLength-1;i>=0;i--)

{

arrDst[arrCount[arrSrc[i]]-1] = arrSrc[i];

arrCount[arrSrc[i]] -= 1;

}

 

delete []arrCount;

}

#include <iostream>

#include <stdlib.h>

using namespace std;

 

void CountingSort(int arrSrc[],int arrDst[],int arrLength,int upperLimit);

 

void main()

{

int arrLength = 10;

int upperLimit = 50;

 

int* a = new int[arrLength];

 

for(int i=0;i<arrLength;i++)

a[i]= rand()%(upperLimit+1);

 

for(int i=0;i<arrLength;i++)

cout << a[i] <<"  ";

cout << endl;

 

int* b = new int[arrLength];

CountingSort(a,b,arrLength,upperLimit);

 

for(int i=0;i<arrLength;i++)

cout << b[i] <<"  ";

cout << endl;

 

delete []b;

}

 

桶排序也是基于一定的假设。假定：输入是由一个随机过程产生的[0, 1)区间上均匀分布的实数。将区间[0, 1)划分为n个大小相等的子区间（桶），每桶大小1/n：[0, 1/n)， [1/n, 2/n)， [2/n, 3/n)，…，[k/n, (k+1)/n )，…将n个输入元素分配到这些桶中，对桶中元素进行排序，然后依次连接桶输入0 ≤A[1..n] <1辅助数组B[0..n-1]是一指针数组，指向桶（链表）。