非比较排序试用于元素比较集中的序列。
创新互联公司主营巴林左旗网站建设的网络公司,主营网站建设方案,重庆App定制开发,巴林左旗h5成都小程序开发搭建,巴林左旗网站营销推广欢迎巴林左旗等地区企业咨询
1、计数排序
找出待排序的数组中最大和最小的元素
统计数组中每个值为i的元素出现的次数，存入数组C的第i项
对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）
反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1
void CountSort(int *a, int size)
{
assert(a);
int max = a[0];
int min = a[0];
for (int i = 1; i < size; i++)
{
if (max < a[i])
max = a[i];
if (min > a[i])
min = a[i];
}
int CountSize = max - min + 1;//该序列的范围在min~max之间，所以开辟max-min+1
int *CountArray = new int[CountSize];
memset(CountArray,0,CountSize*sizeof(int));
for (int i = 0; i < size; i++)
{
CountArray[a[i]-min]++;//比如序列在1万到2万之间，那么1万应该存在下标为0的数组上
}
int index = 0;
for (int i = 0; i <= CountSize; i++)
{
int count = CountArray[i];
while (count-- > 0)
{
a[index++] = i+ min;//那么此时下标为0的数，就是1万
}
}
}2、基数排序
基数排序指的是先把序列中的每个数中的个位排序，然后十位排序，直到超过序列中最大数的位数
void DigitSort(int *a, int size)
{
assert(a);
int bit = 1, sum = 10;
for (int i = 0; i < size; i++)
{
while (a[i] >= sum) //取最大数的位数
{
bit++;
sum *= 10;
}
}
int digit = 1;
int *bucket = new int[size];
while (digit <= bit)
{
int count[10] = { 0 };
int position[10] = { 0 };
for (int i = 0; i < size; i++)
{
int numbit = pow(10,digit-1);
int bitvalue = (a[i] / numbit) % 10;
count[bitvalue]++;
}
for (int i = 1; i < 10; i++)
{
position[i] = position[i - 1] + count[i - 1];
}
for (int i = 0; i < size; i++)
{
int numbit = pow(10, digit - 1);
int bitvalue = (a[i] / numbit) % 10;
bucket[position[bitvalue]++] = a[i];
}
digit++;
memcpy(a,bucket,size*sizeof(int));
}
}
