计数排序
计数排序的原理
设被排序的数组为A,排序后存储到B,C为临时数组。所谓计数,首先是通过一个数组C[i]计算大小等于i的元素个数,此过程只需要一次循环遍历就可以;在此基础上,计算小于或者等于i的元素个数,也是一重循环就完成。下一步是关键:逆序循环,从length[A]到1,将A[i]放到B中第C[A[i]]个位置上。原理是:C[A[i]]表示小于等于a[i]的元素个数,正好是A[i]排序后应该在的位置。而且从length[A]到1逆序循环,可以保证相同元素间的相对顺序不变,这也是计数排序稳定性的体现。在数组A有附件属性的时候,稳定性是非常重要的。
计数排序的前提及适用范围
A中的元素不能大于k,而且元素要作为数组的下标,所以元素应该为非负整数。而且如果A中有很大的元素,不能够分配足够大的空间。所以计数排序有很大局限性,其主要适用于元素个数多,但是普遍不太大而且总小于k的情况,这种情况下使用计数排序可以获得很高的效率。由于用来计数的数组C的长度取决于待排序数组中数据的范围(等于待排序数组的最大值与最小值的差加上1),这使得计数排序对于数据范围很大的数组,需要大量时间和内存。例如:计数排序是用来排序0到100之间的数字的最好的算法,但是它不适合按字母顺序排序人名。但是,计数排序可以用在基数排序中的算法来排序数据范围很大的数组。
当输入的元素是 n 个 0 到 k 之间的整数时,它的运行时间是 Θ(n + k)。计数排序不是比较排序,排序的速度快于任何比较排序算法。
计数排序算法的步骤:
1.找出待排序的数组中最大和最小的元素
2.统计数组中每个值为i的元素出现的次数,存入数组C的第i项
3.对所有的计数累加(从C中的第一个元素开始,每一项和前一项相加)
4.反向填充目标数组:将每个元素i放在新数组的第C(i)项,每放一个元素就将C(i)减去1
实现代码:
void CountSort(int *a, int size) { int min = a[0], max = a[0]; int i = 0; for ( i = 0; i < size; i++) { if (min > a[i]) { min = a[i];//找出数组中最小的数 } if (max < a[i]) { max = a[i];//找出数组中的最大数 } } int range = max - min + 1; int *count = new int[range]; //初始化数组 //memset(count, 0, sizeof(int)*range); for (i = 0; i < range; i++) { count[i] = 0; } //把数组a中数变成数组count中的0,1,2.... for (i = 0; i < size; i++) { //把数组count中对应位置制成数字,代表这个位置有几个相同的数 //列如制成1,代表这个位置有一个数 //列如制成2,代表这个位置有两个相同的数 count[a[i] - min]++; } int j = 0; //把count中的数还原回数组a中,它就排好序了 for (i = 0; i < range; i++) { //重复了n次,就拿回去n次 while (count[i]>0) { a[j++] = i + min; count[i]--; } } delete[] count; }
基数排序
算法思想:
待排序数组[62,14,59,88,16]简单点五个数字
分配10个桶,桶编号为0-9,以个位数数字为桶编号依次入桶,变成下边这样
| 0 | 0 | 62 | 0 | 14 | 0 | 16 | 0 | 88 | 59 |
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |桶编号
将桶里的数字顺序取出来,
输出结果:[62,14,16,88,59]
再次入桶,不过这次以十位数的数字为准,进入相应的桶,变成下边这样:
由于前边做了个位数的排序,所以当十位数相等时,个位数字是由小到大的顺序入桶的,就是说,入完桶还是有序
| 0 | 14,16 | 0 | 0 | 0 | 59 | 62 | 0 | 88 | 0 |
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |桶编号
因为没有大过100的数字,没有百位数,所以到这排序完毕,顺序取出即可
最后输出结果:[14,16,59,62,88]
实现代码:
//获取最大位数 static int GetMaxRadix(int *a, int size) { int radix = 10; int count = 1; for (int i = 0; i < size; i++) { //注意这里必须是">=",假如你的最大数是100,如果 //没有“=”的话,你获取最大位就是两位 while (a[i]>=radix) { radix *= 10; count++; } } return count; } static void _RadixSort(int* a, int size, int divisor, int* tmp) { int count[10] = { 0 }; int start[10] = { 0 }; //如果你处理的是个位,count代表就是数据个位在 //count对应位置出现的个数。十位,百位类似。 for (int i = 0; i < size; i++) { int num1 = a[i] / divisor; count[num1 % 10]++; } //个位,十位,百位等出现的起始位置 for (int j = 1; j < 10; j++) { start[j] = start[j - 1] + count[j - 1]; } //根据start,将a中的数据放在tmp中,已排好序 for (int k = 0; k < size; k++) { int num2 = a[k] / divisor; tmp[start[num2 % 10]++] = a[k]; } //把排好序的数据放回a中 for (int n = 0; n < size; n++) { a[n] = tmp[n]; } } void RadixSort(int *arr, int size) { assert(arr); int *tmp = new int[size]; int n = GetMaxRadix(arr, size); for (int i = 1; i <= n; i++) { int divisor = 1; int k = i; while (--k) { divisor *= 10; } _RadixSort(arr, size, divisor, tmp); } delete[] tmp; }
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。