线性时间排序

  夜深人静的时候，最好写代码，趁着大家熟睡之际，复习一下这几种排序方法。原理再算法导论上都有。


计数排序


     计数排序算法的基本思想是对于给定的输入序列中的每一个元素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);   
}