前面介绍了一些常用的比较排序算法，它们都是通过比较两个元素的大小进行排序，归并排序和堆排序在最坏情况下的复杂度为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] = {};

    for(int i=;i<len;i++)

        c[A[i]] += ;

    for(int i=;i<k;i++)

        c[i] += c[i-];

    for(int i=len-;i>=;i--){  //从后往前遍历数组，可以保证排序的稳定性，具有相同值的元素在排序后相对次序不变。

        B[c[A[i]]-] = A[i];

        c[A[i]] -= ;

    }

}

int main(){

    int A[] = {,,,,,,,,};

    int B[];//排序后的数组

    counting_sort(A, B, );

    for(int i=;i<;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=;i<len;i++)

        B[i] = NULL;

    for(int i=;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 = ;

    for(int i=;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=;i<len;i++)

        cout<<A[i]<<" ";

    cout<<endl;

    return ;

}

巴特西

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

计数排序

基数排序

桶排序

最新文章

热门文章