算法导论 第二版 8.2 计数排序

本文主要是介绍算法导论 第二版 8.2 计数排序，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

根据伪码编写:

#include <iostream>
#include <ctime>
using namespace std;void counting_sort(int *A, int *B, int *C, int k, int n)//B是排序输出,C用来计数
{for(int i = 0; i <= k; i++)//初始化CC[i] = 0;for(int j = 0; j <= n; j++)C[A[j]] = C[A[j]] + 1;//C[i]存放A中等于i的元素个数for(int i = 1; i <= k; i++)C[i] = C[i] + C[i-1];//C[i]存放小于等于i的元素个数for(int j = n; j >= 1; j--)//对A遍历(其实从低到高也可以){B[C[A[j]]] = A[j];//C[A[j]]即为A[j]在B中的正确位置(小于等于A[j]的元素共有C[A[j]]个,故A[j]排在第C[A[j]]号位)C[A[j]] = C[A[j]] - 1;//计数-1}
}int main()
{int A[9] = {-1,2,5,3,0,2,3,0,3};//算法下标从1开始.A[0]不用int B[9];int n = sizeof(A)/sizeof(int) - 1;int k = 5;int *C = (int*)malloc(sizeof(int)*(k+1));counting_sort(A, B, C, k, n);for(int i = 0; i <= n; i++)//输出cout << B[i] << " ";
}

输出:1501354696 0 0 2 2 3 3 3 5

这篇关于算法导论 第二版 8.2 计数排序的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---