计数排序
计数排序假设n个输入元素(适用于小范围区间)中的每一个都是在0到k区间内的一个整数,其中k为某个整数。当k=O(n)时,排序的运行时间为.
计数排序的基本思想:对每一个输入的元素x,确定小于x的元素个数。利用这一信息,就可以直接把x放到它在输出数组中的位置上了。例如,如果有17个元素小于x,则x就应该在第18个输出位置上。当有几个元素相同时,这一方案要略做修改。因为不能把它们放在同一个输出位置上。
我们假设个数组 A[0...n-1 ], A.length = n, k 为A中最大元素,我们还需要两个数组:B(0...n)存放排序的输出,C[0...k] 提供临时存储空间
伪代码:
COUNTING-SORT(A , B , k)
let C[0...k] be a new array
for i = 0 to k //将数组C都置为0
C[ i ] = 0
for j = 0 to A.length
C[ A [ j ] ] = C[ A [ j ] ] + 1
for i = 1 to k //找到元素的位置
C [ i ] = C[ i ] + C[ i -1 ];
for j = A.length downto 0
B[ C[ A[ j ] ] - 1 ] =A[ j ]
C[ A[ j ] ] = C[ A[ j ] ] -1
看图理解:
根据上图排完序后相同元素的位置与排之前相同,所以计数排序是稳定的排序。
算法分析:
COUNTING-SORT(A , B , k)
let C[0...k] be a new array 1
for i = 0 to k k+1
C[ i ] = 0 k
for j = 0 to A.length n+1
C[ A [ j ] ] = C[ A [ j ] ] + 1 n
for i = 1 to k k
C [ i ] = C[ i ] + C[ i -1 ]; k-1
for j = A.length downto 0 n+1
B[ C[ A[ j ] ] - 1 ] =A[ j ] n
C[ A[ j ] ] = C[ A[ j ] ] -1 n
可知时间消耗为
我们写一个存在负数的计数排序代码:
#include<iostream>
using namespace std;
//计数排序
void COUNTING_SORT(int A[], int B[],int k,int size,int n)
{
int* C = (int*)malloc(sizeof(int) * k);
for (int i = 0; i < k; ++i)
{
C[i] = 0;
}
for (int j = 0; j < size; ++j)
{
C[A[j] + n]++;
}
for (int i = 1; i < k; ++i)
{
C[i] = C[i] + C[i - 1];
}
for (int j = size - 1; j >= 0; --j)
{
B[C[A[j]+n]-1] = A[j];
C[A[j] + n]--;
}
free(C);
}
//打印
void Print(int A[], int size)
{
for (int i = 0; i < size; ++i)
{
cout << A[i] << " ";
}
cout << endl;
}
int main()
{
int A[] = { 13,-3,-25,20,-3,-16,-23,18,20,-7,12,-5,-22,15,-4,7 };//想要负数存入计数数组C中,要将负数变为正数
int size = sizeof(A) / sizeof(int);
int n = 25; //每个元素都加上n值存入数组C
int k = 46;
int B[16];
cout << "要排列的数组为:" << endl;
Print(A, size);
COUNTING_SORT(A, B, k, size,n);
cout << "使用计数排序后:" << endl;
Print(B, size);
}
结果:
要排列的数组为:
13 -3 -25 20 -3 -16 -23 18 20 -7 12 -5 -22 15 -4 7
使用计数排序后:
-25 -23 -22 -16 -7 -5 -4 -3 -3 7 12 13 15 18 20 20