夜深人静的时候，最好写代码，趁着大家熟睡之际，复习一下这几种排序方法。原理再算法导论上都有。
计数排序
计数排序算法的基本思想是对于给定的输入序列中的每一个元素x，确定该序列中值小于x的元素的个数。一旦有了这个信息，就可以将x直接存放到最终的输出序列的正确位置上。 当然，如果有多个元素具有相同的值时，我们不能将这些元素放在输出序列的同一个位置上，因此，上述方案还要作适当的修改。
时间复杂度分析：o(n+k)，k数组中的最大值。计数排序是稳定的。但是对数据分布不均匀数组，计数排序的空间复杂度和时间复杂度毫无优势。例如：{2,1,4,10000}，用计数排序太大了。
[cpp] view plaincopyprint?
/*copyright @lsj on juyuan*/
#include
#include
#include
using namespace std;
void Output(int arr[],int len)
{
assert(arr && len>=0);
for(int i=0; i
cout<
cout<
}
void CountSort(int arr[],int len)
{
int maxElem = *max_element(arr,arr+len);
int *countArr = new int[maxElem+1];
memset(countArr,0,sizeof(int)*(maxElem+1));
int *temp = new int[len];
assert(temp && countArr);
int i;
for(i=0; i
countArr[arr[i]]++;
for(i=1; i<=maxElem; ++i)
countArr[i] += countArr[i-1];
for(i=len-1; i>=0; --i){
temp[countArr[arr[i]]-1] = arr[i];
--countArr[arr[i]];
}
memcpy(arr,temp,len*sizeof(int));
delete[] countArr;
delete[] temp;
}
int main()
{
const int size = 8;
int arr[size] = {12,3,4,53,5,6,11,90};
Output(arr,size);
CountSort(arr,size);
Output(arr,size);
system("pause");
return 0;
}
桶排序
先确定你的桶有多大，然后根据数组中的最大值和最小值算出max-min算出我们需要多少桶。
barrelNum = (max-min+1)/barrelSize + 1
然后，根据每个元素的大小，计算应该放在哪个桶里面:
index = (arr[i]-min)/barrelSize
最后对每个桶采用插入排序，本文简单的采用了快排（小数据时，插入排序性能更好）。最后合起来输出就ok了。
时间复杂度分析：期望运行时间为o(n)，即使输入不满足均匀分布也能满足。但是如果输入不满足均匀分布，空间复杂度太高，因为很多桶都是空着的，划不来。{2,1,4,10000}，几乎桶全部是空的。
[cpp] view plaincopyprint?
/*copyright @lsj on juyuan*/
#include
#include
#include
using namespace std;
void Output(int arr[],int len)
{
assert(arr && len>=0);
for(int i=0; i
cout<
cout<
}
const int barrelSize = 10;
typedef struct __bucket{
int data[barrelSize];
int curNum;
}Bucket;
void BucketSort(int arr[],int len)
{
assert(arr && len>=0);
int maxElem = *max_element(arr,arr+len);
int minElem = *min_element(arr,arr+len);
int bucketNum = (maxElem - minElem + 1)/barrelSize + 1;
Bucket *pBarrel = new Bucket[bucketNum];
memset(pBarrel,0,sizeof(Bucket)*bucketNum);
assert(pBarrel);
int i;
for(i=0; i
int bucketIndex = (arr[i]-minElem)/barrelSize;
pBarrel[bucketIndex].data[pBarrel[bucketIndex].curNum++]=arr[i];
}
int pos = 0;
for(i=0; i
if(pBarrel[i].curNum!=0)
sort(pBarrel[i].data,pBarrel[i].data+pBarrel[i].curNum);
for(int j=0; j
arr[pos++] = pBarrel[i].data[j];
}
delete[] pBarrel;
}
int main()
{
const int size = 8;
int arr[size] = {12,3,4,13,5,6,11,90};
Output(arr,size);
BucketSort(arr,size);
Output(arr,size);
system("pause");
return 0;
}
基数排序
原理就不啰嗦了，下面程序中我利用了队列的先进先出原则。并没有像算法导论那样用到基数排序来做。感觉程序编的不是很好。这哥们说的对，我这么写，只是说明了一下基数的原理，没有把“鸡排的优势”发挥出来
基数排序的时间复杂度：给定n个d位数，每一个数位可以运行k种可能的值。如果所用的计数排序为o(d+k)，则基数排序的时间复杂度o(d(n+k))。
[cpp] view plaincopyprint?
/*copyright @lsj on juyuan*/
#include
#include
#include
#include
using namespace std;
void Output(int arr[],int len)
{
assert(arr && len>=0);
for(int i=0; i
cout<
cout<
}
void RadixSort(int arr[],int len)
{
assert(arr && len>=0);
vector > radixQueue(10);
int *temp = new int[len];
assert(temp);
int i = 0;
bool notFinish = true;
int base = 1;
while(notFinish){
notFinish = false;
for(i=0; i
int num = (arr[i] / base) % 10;
radixQueue[num].push(arr[i]);
if(arr[i]/(10*base) != 0)
notFinish = true;
}
int pos = 0;
for(i=0; i<=9; ++i){
while(!radixQueue[i].empty()){
temp[pos++] = radixQueue[i].front();
radixQueue[i].pop();
}
}
for(i=0; i
arr[i] = temp[i];
base *= 10;
}
delete[] temp;
}
int main()
{
const int size = 8;
int arr[size] = {12,32,4,1213,5,6,11,90};
Output(arr,size);
RadixSort(arr,size);
Output(arr,size);
system("pause");
return 0;
}
这个找最大的位数程序不错（这就是上面哥们写的代码，学习）
[cpp] view plaincopyprint?
int maxbit(int L[],int n) {
int d = 1,i=0; //保存最大的位数
int p=10;
for(i = 0;i < n; i++) {
while(L[i] >= p) {
p *= 10;
d++;
}
}
return d;
}
void radixsort(int L[],int len)
{
int d = maxbit(L,len);
long * tmp = (long *)malloc(len*sizeof(long));
long * count = (long *)malloc(10*sizeof(long));; //计数器,10个桶
long i,j,k;
int radix = 1;
for(i = 1; i <= d; i++)
{ //进行d次排序
for(j = 0; j < 10;j++) //每次分配前清空计数器
count[j] = 0;
for(j = 0;j < len; j++)
{ //统计每个桶中的记录数
k = (L[j]/radix)%10;
count[k]++;
}
for(j = 1;j < 10; j++) //将tmp中的位置依次分配给每个桶
count[j] = count[j-1] + count[j];
for(j = len-1;j >= 0;j--)
{ //将所有桶中记录依次收集到tmp中
k = (L[j]/radix)%10;
count[k]--;
tmp[count[k]] = L[j];
}
for(j = 0;j < len;j++) //将临时数组的内容复制到L中
L[j] = tmp[j];
radix = radix*10;
}
free(tmp);
free(count);
}
阅读(1354) | 评论(0) | 转发(0) |
