锐客网

  1. 首页 > it技术 > >

《算法导论》读书笔记--计数排序&基数排序

算法

计数排序是用空间换取时间的算法，其假设n个输入元素中的每一个都在0到k区间内的一个整数，其中k为某个整数。当k=O(n)时，排序的运行时间为Theta(n)。
基本思想：对每一个输入元素x，确定小于x的元素个数。利用这一信息，就可以直接把x放到它在输出数组中的位置上了。
输入数组为A[1..n]
辅助数组：B[1..n]存放排序的输出，C[1..k]提供临时存储空间(存放A中数组元素值的出现次数)。
伪代码：

COUNTING-SORT(A,B,k) let C[0..k] be a new array for i = 0 to k //后面需要使用数组C来存储A中各元素的出现次数，所以需要清零操作 C[i] = 0 for j = 1 to A.length C[A[j]] = C[A[j]] + 1 //统计A中各元素的出现次数存储在C中，C中下标为A中的元素值，与其对应的数组元素为出现次数，如C[1] = 0，即为“1”在A中的出现次数为0 for i = 1 to k C[i] = C[i] + C[i-1] //计算A中小于等于i的一共有多少个，方便此后将i放在数组B中正确的位置上 for j = A.length downto 1 B[C[A[j]]] = A[j] //使用A中元素A[j]的出现次数作为B中的下标，把每个元素放在B中适当的位置 C[A[j]] = C[A[j]] -1 //在B中放入一个元素，与其对应C中出现的次数-1。这样，当遇到下一个等于A[j]的输入元素时，该元素可以被直接放到B中A[j]的前一位置上


12 3 4 5 6 7 80 1 2 3 4 51 2 3 4 5 6 7 8
A[2 5 3 0 2 3 0 3]C[2 2 4 7 7 8]B[3]
0 1 2 3 4 50 1 2 3 4 5
C[2 0 2 3 0 1]C[2 2 4 6 7 8]
(a)(b)(c)


1 2 3 4 5 6 7 81 2 3 4 5 6 7 81 2 3 4 5 6 7 8
B[03]B[03 3]B[0 0 2 2 3 3 3 5]
0 1 2 3 4 50 1 2 3 4 5
C[1 2 4 6 7 8]C[1 2 4 5 7 8]
(d)(e)(f)
步骤(a)为伪代码中第二个for循环，统计A中各元素的出现次数
步骤(b)为伪代码中第三个for循环，统计A中小于等于i元素的数量
步骤(c)(d)(e)为伪代码中第四个for循环，进行排序
步骤(f)为排序结果。


计数排序为稳定的排序算法，通常被用做基数排序算法的一个子过程，为了使基数排序能够正确运行，计数排序必须是稳定的。



计数排序Demo：

#include #include #include #define LENGTH 8 void counting_sort(int *A,int *B,int k) { int *C=(int *)malloc(k*sizeof(int)); for(int i = 0; i < k; i++) C[i] = 0; for(int i = 0; i < LENGTH; i++) C[A[i]]++; for(int i = 1; i < k; i++)//i应从1开始,若从0开始，则C[i-1]越界 C[i] = C[i] + C[i-1]; for(int i = LENGTH-1; i >= 0; i--) { B[C[A[i]]-1] = A[i]; //B数组的下标从0开始，C[A[i]]中的元素数量的总和从1开始计数，所以存放到B中时需要减1，才能放到正确的位置上 想象当A中只有一个元素，C[A[i]] = 1，要存放进B中，就是B[C[A[i]]-1] C[A[i]]--; } free(C); C = NULL; }int main() { int A[LENGTH],B[LENGTH]; for(int i = 0; i < LENGTH; i++) std::cin >> A[i]; //scanf("%d",A[i]); counting_sort(A,B,6); //k决定了数组中数的取值范围 0<=x<=k for(int i = 0; i < LENGTH; i++) printf("%d ",B[i]); printf("\n"); system("pause"); return 0; }




基数排序： 算法描述参照 算法总结系列之五: 基数排序(Radix Sort) -- Jeffrey Sun
radix_sort Demo：
【《算法导论》读书笔记--计数排序&基数排序】
#include #include #include using namespace std; #define LENGTH 4 #define NUM_LEN 3 //最大数位长度 void radix_sort(int *A,int d) { int sort_num = 0; int B[LENGTH]; for(int j = 1; j <= d; j++)//d是总位数，位数由低到高进行排序 { //计数排序部分 int p = (int)pow(10,j-1); //用于A[i]/p%10 获取整个数组第j位的值，本轮是按照数组的第j位进行排序 int C[10]; //每一位的取值共有0-9十个情况 for(int i = 0; i < 10; i++) C[i] = 0; for(int i = 0; i < LENGTH; i++) C[A[i]/p%10]++; for(int i = 1; i < 10; i++)//i应从1开始 C[i] = C[i] + C[i-1]; for(int i = LENGTH-1; i >= 0; i--) { B[C[ A[i]/p%10 ]-1] = A[i]; //B数组的下标从0开始，C[A[i]]中的元素数量的总和从1开始计数，所以存放到B中时需要减1，才能放到正确的位置上 想象当A中只有一个元素，C[A[i]] = 1，要存放进B中，就是B[C[A[i]]-1] C[A[i]/p%10]--; } //end for(int i = 0; i < LENGTH; i++)//将本轮排序结果赋值回原数组 A[i] = B[i]; } }int main() { int A[LENGTH]; for(int i = 0; i < LENGTH; i++) cin >> A[i]; radix_sort(A,NUM_LEN); for(int i = 0; i < LENGTH; i++) cout << A[i] <<" "; cout<



    推荐阅读


    上一篇：kernel version 367.48. does not match DSO version 367.57

    下一篇：Hello Mr.J——开个新坑，Docker！