所有排序总结（内排序）（续）——线性时间排序

 

一、前言

      这里稍微证明一下基于比较的排序算法的下界，采用决策树模型。下图是一个含三个元素的输入序列，采用插入排序算法的决策树。每一个结点里面包含（i,j）。左子树代表i<=j的情况，右子树代表i>j的情况。

      各位，如果有跟我一样，半天看不懂的话，我就稍微解释一下。拿（1,2,3）这个序列的得出，稍作说明。在根节点处，1和2比较（输入位置为1的元素与输入位置为2的元素比较，不是1和2比较，下同）。 1<2，进入到左子树。  2和3比较，  2<3，还是到左子树   得出排序后的序列（1,2,3）。

      有一点要说明的是：任何一个正确的排序算法，都能产生全部n!个序列。这n!个序列对应决策树中的所有叶节点。

      从这个模型明显可以得出结论：从根节点到任意一个叶节点之间最长路径的长度，也即决策树的高度（每一本书所说的高度概念不一致，这里取图中的高度为3），表示排序算法在最坏情况下的比较次数。

      利用决策树模型对基于比较的排序算法时间下界的证明：

      考虑一个高为 h，  叶节点个数为l的  决策树。  输入序列为n。  显然  n!<=l。（说明:如果不考虑n个元素有相等的情况，n!应该等于l）.

      又，一个高度为h的完全二叉树的叶节点的数目为2h。   l <= 2h 

      即      n!<=l<=2h.

      取对数可得到   h>=lg(n!)。

      又， lg(n!) = Θ(nlgn);
      得到   h>=Ω(nlgn);

      说明一下这个：lg(n!) = Θ(nlgn);

     （注：好长时间没看这些，应该是从来没有认真看过==...  都没有搞清楚  Ο  Θ   Ω  这个几个符号的意思。翻了导论前面几章才算明白。   这个的证明要用到斯特灵公式。    我感觉已经超出我的能力范围之外了，不想花时间再去研究这玩意儿了 。）

      斯特林公式参看这里 http://zh.wikipedia.org/wiki/%E6%96%AF%E7%89%B9%E9%9D%88%E5%85%AC%E5%BC%8F）

      简单说就是：

      f(n) = Θ(g(n)) 当且仅当f(n) =  Ω(nlgn)和f(n) = Ο(nlgn)。  这里的“=”并不是等号的意思。  f(n) = Θ(g(n)) 是 f(n) 属于 Θ(g(n)) 的意思，Θ(g(n)) 是一个集合。

      lg(n!) = Θ(nlgn);  就是说存在  c1和c2  所有的n>=n0,有 0<=c1(nlgn) <= lg(n!) <= c2(nlgn) 。

二、三种线性时间排序

 

1、计数排序

     计数排序就是根据元素的值统计元素的个数，然后直接把元素放到合适的位置，以达到Θ(n)的目的。思路也很简单，废话不多说，直接上代码

 1 #include <stdio.h>
 2 #include <stdlib.h>
 3 void countingSort(int *A,int n,int *B,int *C,int k)
 4 {
 5     //A为待排序的数组；
 6     //n为A数组的长度；
 7     //B为保存的结果；
 8     //C为临时存储区  长度为k
 9     //k为n个数据输入的范围； 0~~k-1
10     for(int i=0;i<k;i++)
11        C[i] = 0;
12     for(int j=0;j<n;j++)
13        C[A[j]] += 1;      //统计每个位置的个数
14     for(int i=1;i<k;i++)
15        C[i] += C[i-1];   //c[i]表示小于等于i的个数
16     for(int j = n-1;j>=0;j--)//放到合适的位置,因为是从0开始  要减1
17     {
18         B[C[A[j]]-1] = A[j]; //c[i]表示小于等于i的个数  B[]从0开始  c[i]-1 表示在B中的位置
19         C[A[j]] -= 1;
20     }
21 }
22 int main()
23 {
24     int n=11;//待排序的长度
25     int k=11;//数字范围 为 0~~k-1
26     int a[n] ;
27     int b[n] ;
28     int c[k] ;
29     for(int i=0;i<n;i++)
30        a[i] = rand()%k ;
31     for(int i=0;i<n;i++)
32        printf("%d ",a[i]);
33     printf("\n");
34     countingSort(a,n,b,c,k);
35     for(int i=0;i<n;i++)
36      printf("%d ",b[i]);
37     return 0;
38 }

       写代码的时候，习惯从0开始了。导致第四个for循环的时候忘记减1了，纠结了好久。。。。显然可以看出上面的计数排序的Θ(n+k)。好吧，我一开始也不知道这个是怎么来的。一共四个循环，Θ(2n+2k)，去掉常数就是Θ(n+k)，n表示待排序数组，k表示要排序的的值的范围。这样，计数排序就很有局限了，k的值注定了这种排序的适用范围很小。

2、桶排序

     也许看完上面的计数排序，你会发现既然C数组已经统计完了每个值的个数，那么直接扫描一遍C数组，依次序输出也就OK了。这个就算是桶排序了，这里的每个桶只能存储一个值，算作是特殊的桶排序吧。将上面的代码稍作改变就可以得到：

 1 void BucketSort(int *A,int n,int *B,int *C,int k)
 2 {
 3     //A为待排序的数组；
 4     //n为A数组的长度；
 5     //B为保存的结果；
 6     //C为临时存储区  长度为k
 7     //k为n个数据输入的范围； 0~~k-1
 8     for(int i=0;i<k;i++)
 9        C[i] = 0;
10     for(int j=0;j<n;j++)
11        C[A[j]] += 1; //统计每个位置的个数
12     int j=0;
13     for(int i=0;i<k;i++)
14     {
15         while(C[i]!=0)
16         {
17             B[j++] = i;
18             C[i]--;
19         }
20     }
21 }

      一般桶排序的操作步骤就是：

      1、确定要排序数组的取值范围，并划分成M个区间；

      2、给这个M区间划分M个桶，并对每个桶内进行排序；

      3、再依次序把这M个桶的元素串接起来。

      这里上一幅导论里面的图，它讲100划分成10个区间，设计10个桶。然后将数组里面的元素放到相应的桶里面去。

     附上我写的代码（实际是参考别人写的==！  一个链表操作写了好长时间，还被别人鄙视了无数遍。。。。。。。。。）

#include <stdio.h>
#include <stdlib.h>
struct Node
{
    int value;
    Node *next;
};
void BucketSort(int *array,int n,int low,int high,int interval)
{//low和high分别代表  元素的最小值 和最大值
 //n为待排序数组长度，interval间隔
    int BucketNum = (high-low)/interval;//有多少个桶
    Node *BucketArray = new Node[BucketNum];
    Node *pre,*cur;
    int count=0;
    for(int i=0;i<10;i++)
    {
        BucketArray[i].value = 0;
        BucketArray[i].next = NULL;  //初始化。。。。
    }
    for(int i=0;i<n;i++)
    {
        Node *insert = new Node();
        insert->value = array[i];    //待插入的节点
        int num = array[i]/interval;
        if(BucketArray[num].next == NULL)
        {
            BucketArray[num].next = insert;   //每个桶的第一个节点保持空
        }
        else
        {
            pre = &BucketArray[num];
            cur = BucketArray[num].next;
            while(cur!=NULL && cur->value<=array[i])//找到合适的位置。
            {
                cur = cur->next;
                pre = pre->next;
            }
            insert->next = cur;
            pre->next = insert;

        }
    }
    for(int i=0;i<BucketNum;i++)
    {
        cur = BucketArray[i].next;
        if(cur == NULL)
            continue;
        while(cur!=NULL)
        {
            array[count++] = cur->value;
            cur = cur->next;
        }
    }
}
int main()
{
    int a[10];
    for(int i=0;i<10;i++)
    {
        a[i] = rand()%100;//随机数
    }
    BucketSort(a,10,0,100,10);
    for(int i=0;i<10;i++)
    {
        printf("%d ",a[i]);
    }
    return 0;
}

     这段代码里面，设元素有N个，M个桶，平均每个桶里面有N/M个元素。在桶里面的，我没有采用其他的排序算法，简单的插入。因此桶里面为Θ(N/M)。总的时间复杂度为   Θ(N * N/M)=Θ(N2/M) ，可以看出来，当桶的数量越多。。。趋近于N时，时间复杂度就为Θ(N)了。

3、基数排序

      基数排序是对多个关键字的排序。两种方式，一是从首要关键字到次要关键字，另外一种是从次要关键字到首要关键字。导论上面说的是第二种。如果是从首要关键字开始，就要对首要关键字相同的进行分堆，再根据次要关键字排序。增加开销，有点桶排序的味道了。

      这里我以技术排序为基础，从次要关键字开始，写了这个基数排序：

 1 #include <stdio.h>
 2 #include <stdlib.h>
 3 #include <math.h>
 4 void countingSort(int *A,int n,int *C,int k,int d)
 5 {
 6     //A为待排序的数组；
 7     //n为A数组的长度；
 8     //B为保存的结果；
 9     //C为临时存储区  长度为k
10     //k为n个数据输入的范围； 0~~k-1
11     int B[n];
12     int key=0;
13     for(int i=0;i<k;i++)
14        C[i] = 0;
15     for(int j=0;j<n;j++)
16     {
17         key = (A[j]/(int)(pow(10,d)))%10;//分离位数用。。。。
18         C[key] += 1;      //统计每个位置的个数
19     }
20     for(int i=1;i<k;i++)
21        C[i] += C[i-1];   //c[i]表示小于等于i的个数
22     for(int j = n-1;j>=0;j--)//放到合适的位置,因为是从0开始  要减1
23     {
24         key = (A[j]/(int)(pow(10,d)))%10;
25         B[C[key]-1] = A[j]; //c[i]表示小于等于i的个数  B[]从0开始  c[i]-1 表示在B中的位置
26         C[key] -= 1;
27     }
28     for(int i=0;i<n;i++)
29     {
30         A[i]=B[i];
31     }
32 }
33 void radixSort(int A[],int n,int d)
34 {
35     int k=10;//数字范围 为 0~~k-1
36     int C[k] ;
37     for(int i=0;i<d;i++)
38     {
39         countingSort(A,n,C,k,i);
40     }
41 }
42 int main()
43 {
44     int A[10];
45     for(int i=0;i<10;i++)
46        A[i] = rand()%999;
47     for(int i=0;i<10;i++)
48        printf("%d ",A[i]);
49     printf("\n");
50     radixSort(A,10,3);
51     for(int i=0;i<10;i++)
52      printf("%d ",A[i]);
53     return 0;
54 }

      有人跟我说，代码里面key对 位数的获取 ，可以用位操作，我想了想，需要BCD码，没有想到特别好的解决方案，还是这样易懂。我总觉得硬性搞成位操作反而有点麻烦了，没有多大意义。没有让人眼睛一亮的解决方案。上面的代码时间复杂度为Θ(d(n+k));

三、总结

     显然，线性时间排序有很大的局限，对数据值范围有要求。

     另外，写这三个排序，原本以为半天多都可以搞定，结果弄了两三天。遭到了无数的鄙视。。最关键还是自己不够熟悉。。

     关于排序，暂时就到这里吧。开学了，下学期专业课压死人。每学期好多门课，但是都感觉没一门学得扎实。

     以后如果有新的认识，我会再继续写写的。我觉得还会有续的，就是不知道多久了。。。。

     持续关注数据结构算法，一来，它很重要，二来，还是有点兴趣。

最后，推荐一篇文章   挺有启发意义的。

http://mindhacks.cn/2008/06/13/why-is-quicksort-so-quick/

  

【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/xibaohe/p/2648136.html