计数排序算法实现举例
C代码
#include
#include
#define MAX 1000
//函数原型
void counting_sort(int A[],int length_A,int B[],int k);
//测试代码
int main()
{
int A[]={-1,2,6,5,4,8,9,7,1,10,3};//1到10,十个测试数据
int B[11]={0};
int k=10;//所有测试数据都处于0到k之间
counting_sort(A,10,B,k);
for(int i=1;i<11;i++)
printf("%d ",B[i]);
getch();
}
//计数排序
void counting_sort(int A[],int length_A,int B[],int k)
{
int C[MAX]={0};//C是临时数组
for(int i=1;i<=length_A;i++)
C[A[i]]++;
//此时C[i]包含等于i的元素个数
for(int i=1;i<=k;i++)
C[i]=C[i]+C[i-1];
//此时C[i]包含小于或者等于i的元素个数
for(int i=length_A;i>=1;i--)//从length_A到1逆序遍历是为了保证相同元素排序后的相对顺序不改变
{ //如果从1到length_A,则相同元素的相对顺序会逆序，但结果也是正确的
B[C[A[i]]]=A[i];
C[A[i]]--;
}
}
可以使用链表节省辅助数组C的空间，只存储出现的出现元素情况。
§5 Proxmap Sort
Proxmap Sort
Proxmap Sort是桶排序和基数排序的改进。ProxMap的排序采用不同的方法来排序，这在概念上是类似哈希。该算法使用桶技术对哈希方法进行改变，桶的大小不相同。
Technique:
Create 4 arrays and initialize
int HitList[ARRAYSIZE] -- Keeps a count of the number of hits at each index in the sorted array. HitList[x] holds a count of the number of items whose keys hashed to x. Initialize to all 0.
int Location[ARRAYSIZE] -- Indices in the sorted array calculated using the hash function. Item x in the unsorted array has its hash index stored in Location[x]. Does not need to be initialized.
int ProxMap[ARRAYSIZE] -- Starting index in the sorted array for each bucket. If HitList[x] is not 0 then ProxMap[x] contains the starting index for the bucket of keys hashing to x. Initialize to all keys to -1 (unused).
StructType DataArray2[ARRAYSIZE] -- Array to hold the sorted array. Initialize to all -1 (unused).
Use the keys of the unsorted array and a carefully chosen hash function to generate the indices into the sorted array and save these. The hash function must compute indices always in ascending order. Store each hash index in the Location[] array. Location[i] will hold the calculated hash index for the ith structure in the unsorted array.
HIdx = Hash(DataArray[i]);
Location[i] = HIdx;
Care must be taken in selecting the hash function so that the keys are mapped to the entire range of indexes in the array. A good approach is to convert the keys to integer values if they are strings, then map all keys to floats in the range 0<= Key < 1. Finally, map these floats to the array indices using the following formulas:
/* Map all integer keys to floats in range 0<= Key < 1 */
KeyFloat = KeyInt / (1 + MAXKEYINTVALUE);
/* Map all float keys to indices in range 0<= Index < ARRAYSIZE */
Index = floor(ARRAYSIZE * KeyFloat);
This will then produce indices insuring that all the keys are kept in ascending order (hashs computed using a mod operator will not.)
Keep a count of the number of hits at each hash index. HitList[Hidx]++
Create the ProxMap (short for proximity map) from the hit list giving the starting index in the sorted array for each bucket.
RunningTotal = 0; /* Init counter */
for(i=0; i 0) /* There were hits at this address */
{
ProxMap[i] = RunningTotal; /* Set start index for this set */
RunningTotal += HitList[i];
}
}
Move keys from the unsorted array to the sorted array using an insertion sort technique for each bucket.
In this diagram 5 sets of structures are sorted when delta = 5
Analysis: ProxMap sorting runs in a surprisingly fast O(n) time.
C代码
/******************************************************/
/* ProxmapSort.c */
/*