线性排序总结（c++实现）

前面介绍了一些常用的比较排序算法，它们都是通过比较两个元素的大小进行排序，归并排序和堆排序在最坏情况下的复杂度为O(nlgn)，可以证明（使用决策树模型），通过比较进行排序，算法的下界为O(nlgn)，因此，归并排序和堆排序是渐进最优的算法，快速排序在平均情况也可达到该下界。

不过，对于一些特殊的输入元素，可以在线性时间完成排序，常见的算法有计数排序、基数排序、桶排序。

计数排序

计数排序假设n个输入元素每一个都是在0到k之间的整数，k为某个整数，当k=O(n)时，计数排序的运行时间为O(n)。

思想：对于每一个输入元素x，计算小于x的元素个数，通过这一信息，可以确定x在排序后的位置，将其正确放置即可。如小于x的元素有4个，那么x应该放在第5个位置上，以此类推。当然，若有多个元素相同，又不可能将它们放置在同一位置，则要在遍历过程中动态修改小于等于x的个数，如：有a个元素小于等于x，且x的值重复出现b次，则遇到第一个x时，将其放在第a位，并使a减1，下次遇到x，则放在第a-1位，最终，b个x放置的位置为(a-b ... a)。算法的核心步骤是如何在线性时间确定小于x的元素个数，这就是假设元素在0到k之间的原因。

#include<iostream>
#define k 100  //输入元素大小在0-99之间。 
using namespace std;
void counting_sort(int* A, int* B, int len){
    int c[k] = {0};
    for(int i=0;i<len;i++)
        c[A[i]] += 1;
    for(int i=1;i<k;i++)
        c[i] += c[i-1];
    for(int i=len-1;i>=0;i--){  //从后往前遍历数组，可以保证排序的稳定性，具有相同值的元素在排序后相对次序不变。
        B[c[A[i]]-1] = A[i];  
        c[A[i]] -= 1;
    }
}

int main(){
    int A[10] = {29,5,13,54,99,8,8,18,21};
    int B[10];//排序后的数组
    counting_sort(A, B, 10);
    for(int i=0;i<10;i++)
        cout<<B[i]<<" ";
    cout<<endl;
}

基数排序

基数排序是一种用在卡片排序机上的算法，其基本过程是对于n个d位整数，从低位到高位依次进行排序，d位数则需要进行d次排序操作，排序使用稳定的排序算法，如计数排序。

为何需要稳定的排序算法呢？下面举个简单的例子说明一下：

假设输入元素为4个3位数，

375

491

604

465

第一次，对最低位进行排序（最右列），结果为

491

604

375

465

第二次，对中间列进行排序：

604

375

465

491

第三次，对最高位进行排序：

375

465

491

604

以上是稳定排序的结果，若排序算法不稳定，那么在第三次排序后得到的结果可能是

375

491

465

604

这是错误的，虽然保证了最高位按照顺序排列，但最高位相同时，中间列的大小关系就起到关键作用，不稳定的排序算法会导致中间列的相对顺序改变，从而得到错误的结果。

桶排序

桶排序假设输入数据服从均匀分布，则平均情况下，时间代价为O(n)。

思想：桶排序与计数排序类似，都对输入数据进行假设，桶排序假设输入数据由一个随机过程均匀独立的分布在[0,1)区间上，将[0,1)区间划分为n个大小相同的子区间（桶），然后将n个输入数据分别放在各个桶中，先对每个桶中元素排序，然后按照桶的次序输出桶中的元素。

#include<iostream>
#define len 10
using namespace std;
struct node{
    double key;
    struct node* next;
};  //定义链表结点 

void Insert_Sort(node*& head){  //对链表使用插入排序 
    node* t = head;
    while(t->next){
        node* p = head;
        node* pre = NULL;
        node* q = t->next;
        while(p != q){
            if(p->key >= q->key)
                break;
            pre = p;
            p = p->next;
        }
        if(pre == NULL){
            head = q;
            t->next = q->next;
            q->next = p;    
        }
        else if(p != q){
            pre->next = q;
            t->next = q->next;
            q->next = p;    
        }
        else    
            t = t->next;
    }
}

void Bucket_Sort(double A[]){  
    node* B[len];   //使用指针数组B作为桶存放数据。 
    for(int i=0;i<len;i++)
        B[i] = NULL;
    for(int i=0;i<len;i++){   //将输入元素A[]放入桶中（B[])。 
        node* p = new node;
        p->key = A[i];
        p->next = B[int(len*A[i])];
        B[int(len*A[i])] = p;
    }
    int j = 0;
    for(int i=0;i<len;i++)   //将桶中数据排序后依次插入数组A中 
        if(B[i] != NULL){
            Insert_Sort(B[i]);
            node* t = B[i];
            while(t){
                A[j++] = t->key;
                node* d = t;
                t = t->next;
                delete d;
            }
        }    
}

int main(int argc, char* argv[]){
    double A[len] = {0.93, 0.41, 0.44, 0.26, 0.82, 0.31, 0.67, 0.94, 0.37, 0.62};
    Bucket_Sort(A);
    for(int i=0;i<len;i++)
        cout<<A[i]<<" ";
    cout<<endl;
    return 0;
}