算法导论第8章—线性时间排序

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

计数排序: 不做元素间的比较
输入: A[1..n], 其中 A[j] ∈{1,2,…,k}
输出: B[1..n], 有序.
辅助存储计数空间: C[1..k].
对于A中元素 x ，如果A中存在 17 元素小于x ，则 x 在输出中的位置应该是18。
如果A有若干元素的值相同?
第一 个放位置18，第二 个放位置19，第三 个放位置20，…
如果A中有 17 个元素不大于x ?
将最后一个x 放位置 17，倒数第二个x 放位置 16，…

#include<iostream>
#include<vector>
using namespace std;void Print(int *B,int size){
for(int i=1;i<=size;i++)
cout<<B[i]<<" ";
cout<<endl;
}void Counting_Sort(int *A,int *B,int k,int size){
vector<int> C;         //灵活的使用内存空间
//int C[10];
for(int i=0;i<=k;i++)
C.push_back(0);
for(int j=1;j<=size;j++)
C[A[j]]=C[A[j]]+1;
for(int i=1;i<=k;i++)
C[i]=C[i]+C[i-1];
for(int j=size;j>=1;j--){
B[C[A[j]]]=A[j];
C[A[j]]=C[A[j]]-1;
}
}int main(){
int A[10];
int B[10];
int size,k;
cout<<"输入元素个数和最大数：";
cin>>size>>k;
cout<<"输入元素:";
for(int i=1;i<=size;i++)
cin>>A[i];
Counting_Sort(A,B,k,size);
Print(B,size);
return 0;
}

这篇关于算法导论第8章—线性时间排序的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---