各种排序笔记---基于非比较排序部分

在计算机科学中，排序是一门基础的算法技术，许多算法都要以此作为基础，不同的排序算法有着不同的时间开销和空间开销。排序算法有非常多种，如我们最常用的快速排序和堆排序等算法，这些算法需要对序列中的数据进行比较，因为被称为基于比较的排序。

基于比较的排序算法是不能突破O(NlogN)的。简单证明如下：

N个数有N!个可能的排列情况，也就是说基于比较的排序算法的判定树有N!个叶子结点，比较次数至少为log(N!)=O(NlogN)(斯特林公式)。

而非基于比较的排序，如计数排序，桶排序，和在此基础上的基数排序，则可以突破O(NlogN)时间下限。但要注意的是，非基于比较的排序算法的使用都是有条件限制的，例如元素的大小限制，相反，基于比较的排序则没有这种限制(在一定范围内)。但并非因为有条件限制就会使非基于比较的排序算法变得无用，对于特定场合有着特殊的性质数据，非基于比较的排序算法则能够非常巧妙地解决。

基于非比较的排序算法有三种，计数排序，桶排序和基数排序。

-----------------------------我是分割线-------------------------------------------------------

1. 计数排序

计数排序（Counting sort）是一种稳定的线性时间排序算法。计数排序使用一个额外的数组C，其中第i个元素是待排序数组A中值等于i的元素的个数。然后根据数组C来将A中的元素排到正确的位置。

 特征：

当输入的元素是n个0到k之间的整数时，它的运行时间是Θ(n + k)。计数排序不是比较排序，排序的速度快于任何比较排序算法。

由于用来计数的数组C的长度取决于待排序数组中数据的范围（等于待排序数组的最大值与最小值的差加上1），这使得计数排序对于数据范围很大的数组，需要大量时间和内存。例如：计数排序是用来排序0到100之间的数字的最好的算法，但是它不适合按字母顺序排序人名。但是，计数排序可以用在基数排序算法中，能够更有效的排序数据范围很大的数组。

通俗地理解，例如有10个年龄不同的人，统计出有8个人的年龄比A小，那A的年龄就排在第9位，用这个方法可以得到其他每个人的位置，也就排好了序。当然，年龄有重复时需要特殊处理（保证稳定性），这就是为什么最后要反向填充目标数组，以及将每个数字的统计减去1的原因。算法的步骤如下：

1. 找出待排序的数组中最大和最小的元素
2. 统计数组中每个值为i的元素出现的次数，存入数组 C 的第 i 项
3. 对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）
4. 反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1

java 实现：

public class CountingSort {
    public static void main(String[] argv) {
        int[] A = CountingSort.countingSort(new int[]{16, 4, 10, 14, 7, 9, 3, 2, 8, 1});
        Utils.print(A);
    }

    public static int[] countingSort(int[] A) {
        int[] B = new int[A.length];
        // 假设A中的数据a'有，0<=a' && a' < k并且k=100
        int k = 100;
        countingSort(A, B, k);
        return B;
    }

    private static void countingSort(int[] A, int[] B, int k) {
        int[] C = new int[k];
        // 计数
        for (int j = 0; j < A.length; j++) {
            int a = A[j];
            C[a] += 1;
        }
        Utils.print(C);
        // 求计数和
        for (int i = 1; i < k; i++) {
            C[i] = C[i] + C[i - 1];
        }
        Utils.print(C);
        // 整理
        for (int j = A.length - 1; j >= 0; j--) {
            int a = A[j];
            B[C[a] - 1] = a;
            C[a] -= 1;
        }
    }
}


//针对c数组的大小，优化过的计数排序
public class CountSort{
    public static void main(String []args){
        //排序的数组
        int a[] = {100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 95};
        int b[] = countSort(a);
        for(int i : b){
            System.out.print(i + "  ");
        }
        System.out.println();
    }
    public static int[] countSort(int []a){
        int b[] = new int[a.length];
        int max = a[0], min = a[0];
        for(int i : a){
            if(i > max){
                max = i;
            }
            if(i < min){
                min = i;
            }
        }
        //这里k的大小是要排序的数组中，元素大小的极值差+1
        int k = max - min + 1;
        int c[] = new int[k];
        for(int i = 0; i < a.length; ++i){
            c[a[i]-min] += 1;//优化过的地方，减小了数组c的大小
        }
        for(int i = 1; i < c.length; ++i){
            c[i] = c[i] + c[i-1];
        }
        for(int i = a.length-1; i >= 0; --i){
            b[--c[a[i]-min]] = a[i];//按存取的方式取出c的元素
        }
        return b;
    }
}

优化后的代码：

public static void Sort(int[] A, int k)
        {
            Debug.Assert(k > 0);
            Debug.Assert(A != null);

            int[] C = new int[k + 1];

            for (int j = 0; j < A.Length; j++)
            {
                C[A[j]]++;
            }

            int z = 0;

            for (int i = 0; i <= k; i++)
            {
                while (C[i]-- > 0)
                {
                    A[z++] = i;
                }
            }
        }

由于C数组下标 i 就是A 的值，所以我们不需要保留A中原来的数了，这个代码减少了一个数组B，而且要比原来的代码简化了很多。

-----------------------------我是分割线------------------------------------------------------

2. 桶排序

可能你会发现，计数排序似乎饶了点弯子，比如当我们刚刚统计出C，C[i]可以表示A中值为i的元素的个数，此时我们直接顺序地扫描C，就可以求出排序后的结果。的确是这样，不过这种方法不再是计数排序，而是桶排序(Bucket Sort)，确切地说，是桶排序的一种特殊情况。

无序数组有个要求,就是成员隶属于固定(有限的)的区间,如范围为[0-9](考试分数为1-100等)

例如待排数字[6 2 4 1 5 9]

准备10个空桶,最大数个空桶

[6 2 4 1 5 9]           待排数组

[0 0 0 0 0 0 0 0 0 0]   空桶

[0 1 2 3 4 5 6 7 8 9]   桶编号(实际不存在)

1,顺序从待排数组中取出数字,首先6被取出,然后把6入6号桶,这个过程类似这样:空桶[ 待排数组[ 0 ] ] = 待排数组[ 0 ]

[6 2 4 1 5 9]           待排数组

[0 0 0 0 0 0 6 0 0 0]   空桶

[0 1 2 3 4 5 6 7 8 9]   桶编号(实际不存在)

2,顺序从待排数组中取出下一个数字,此时2被取出,将其放入2号桶,是几就放几号桶

[6 2 4 1 5 9]           待排数组

[0 0 2 0 0 0 6 0 0 0]   空桶

[0 1 2 3 4 5 6 7 8 9]   桶编号(实际不存在)

3,4,5,6省略,过程一样,全部入桶后变成下边这样

[6 2 4 1 5 9]           待排数组

[0 1 2 0 4 5 6 0 0 9]   空桶

[0 1 2 3 4 5 6 7 8 9]   桶编号(实际不存在)

0表示空桶,跳过,顺序取出即可:1 2 4 5 6 9

void bucketSort(int a[], int n, int max)
{
    int i,j;
    int buckets[max];

    // 将buckets中的所有数据都初始化为0。
    memset(buckets, 0, max*sizeof(int));

    // 1. 计数
    for(i = 0; i < n; i++) 
        buckets[a[i]]++; 

    // 2. 排序
    for (i = 0, j = 0; i < max; i++) 
    {
        while( (buckets[i]--) >0 )
            a[j++] = i;
    }
}

这种特殊实现的方式时间复杂度为O(N+K)，空间复杂度也为O(N+K)，同样要求每个元素都要在K的范围内。更一般的，如果我们的K很大，无法直接开出O(K)的空间该如何呢？

首先定义桶，桶为一个数据容器，每个桶存储一个区间内的数。依然有一个待排序的整数序列A，元素的最小值不小于0，最大值不超过K。假设我们有M个桶，第i个桶Bucket[i]存储K * (i/M) 至 k * (i+1)/M之间的数，有如下桶排序的一般方法：

1. 扫描序列A，根据每个元素的值所属的区间，放入指定的桶中(顺序放置)。
2. 对每个桶中的元素进行排序，什么排序算法都可以，例如快速排序。
3. 依次收集每个桶中的元素，顺序放置到输出序列中。

对该算法简单分析，如果数据是期望平均分布的，则每个桶中的元素平均个数为N/M。如果对每个桶中的元素排序使用的算法是快速排序，每次排序的时间复杂度为O(N/Mlog(N/M))。则总的时间复杂度为O(N)+O(M)O(N/Mlog(N/M)) = O(N+ Nlog(N/M)) =O(N + NlogN - NlogM)。当M接近于N是，桶排序的时间复杂度就可以近似认为是O(N)的。就是桶越多，时间效率就越高，而桶越多，空间却就越大，由此可见时间和空间是一个矛盾的两个方面。

桶中元素的顺序放入和顺序取出是有必要的，因为这样可以确定桶排序是一种稳定排序算法，配合基数排序是很好用的。

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
using namespace std;
struct linklist
{
    linklist *next;
    int value;
    linklist(int v,linklist *n):value(v),next(n){}
    ~linklist() {if (next) delete next;}
};
inline int cmp(const void *a,const void *b)
{
    return *(int *)a-*(int *)b;
}
/*
为了方便，我把A中元素加入桶中时是倒序放入的，而收集取出时也是倒序放入序列的，所以不违背稳定排序。
*/
void BucketSort(int *A,int *B,int N,int K)
{
    linklist *Bucket[101],*p;//建立桶
    int i,j,k,M;
    M=K/100;
    memset(Bucket,0,sizeof(Bucket));
    for (i=1;i<=N;i++)
    {
        k=A[i]/M; //把A中的每个元素按照的范围值放入对应桶中
        Bucket[k]=new linklist(A[i],Bucket[k]);
    }
    for (k=j=0;k<=100;k++)
    {
        i=j;
        for (p=Bucket[k];p;p=p->next)
            B[++j]=p->value; //把桶中每个元素取出，排序并加入B
        delete Bucket[k];
        qsort(B+i+1,j-i,sizeof(B[0]),cmp);
    }
}
int main()
{
    int *A,*B,N=100,K=10000,i;
    A=new int[N+1];
    B=new int[N+1];
    for (i=1;i<=N;i++)
        A[i]=rand()%K+1; //生成1..K的随机数
    BucketSort(A,B,N,K);
    for (i=1;i<=N;i++)
        printf("%d ",B[i]);
    return 0;
}

 例题：

（1）sort color

Given an array with n objects colored red, white or blue, sort them so that objects of the same color are adjacent, with the colors in the order red, white and blue.

Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.

Notice

You are not suppose to use the library's sort function for this problem. 

You should do it in-place (sort numbers in the original array).

Have you met this question in a real interview?

Yes

Example

Given [1, 0, 1, 2], sort it in-place to [0, 1, 1, 2].

次优方法 桶排序／计数排序 代码：

public class Solution {
    public void sortColors(int[] nums) {
        int[] count = new int[3];
        for (int i = 0; i < nums.length; i++) {
            count[nums[i]]++;
        }
        int j = 0;
        for (int i = 0; i < nums.length;i++) {
            if (count[j] > 0) {
                nums[i] = j;
                count[j]--;
            } else  {
                j++;
                i--;
            }
        }
    }
}

由于这个题目只有3个值，也就是拿到数，可以判断是前中后哪个部分的。所以可以用2根指针遍历的方式去实现

最优方法 两根指针

public class Solution {
    public void sortColors(int[] nums) {
        int red = 0, current = 0, blue = nums.length - 1;
        while (current <= blue) {
            if (nums[current] == 0) {
                swap(red, current, nums);
                red++;
                current++;
            } else if (nums[current] == 2) {
                swap(current, blue, nums);
                blue--;
            } else {
                current++;
            }
        }
        
        
        
    }
    private static void swap(int i, int j, int[] nums) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

 

-----------------------------我是分割线----------------------------------------------------------------------

3 基数排序(Radix Sort)

上述的基数排序和桶排序都只是在研究一个关键字的排序，现在我们来讨论有多个关键字的排序问题。

假设我们有一些二元组(a,b)，要对它们进行以a为首要关键字，b的次要关键字的排序。我们可以先把它们先按照首要关键字排序，分成首要关键字相同的若干堆。然后，在按照次要关键值分别对每一堆进行单独排序。最后再把这些堆串连到一起，使首要关键字较小的一堆排在上面。按这种方式的基数排序称为MSD(Most Significant Dight)排序。

第二种方式是从最低有效关键字开始排序，称为LSD(Least Significant Dight)排序。首先对所有的数据按照次要关键字排序，然后对所有的数据按照首要关键字排序。要注意的是，使用的排序算法必须是稳定的，否则就会取消前一次排序的结果。由于不需要分堆对每堆单独排序，LSD方法往往比MSD简单而开销小。下文介绍的方法全部是基于LSD的。

通常，基数排序要用到计数排序或者桶排序。使用计数排序时，需要的是Order数组。使用桶排序时，可以用链表的方法直接求出排序后的顺序。下面是一段用桶排序对二元组基数排序的程序：

基数排序是非比较排序算法,算法的时间复杂度是O(n). 相比于快速排序的O(nlgn),从表面上看具有不小的优势.但事实上可能有些出入,因为基数排序的n可能具有比较大的系数K.因此在具体的应用中,应首先对这个排序函数的效率进行评估.

基数排序的主要思路是,将所有待比较数值(注意,必须是正整数)统一为同样的数位长度,数位较短的数前面补零. 然后, 从最低位开始, 依次进行一次稳定排序(我们常用上一篇blog介绍的计数排序算法, 因为每个位可能的取值范围是固定的从0到9).这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列.

比如这样一个数列排序: 342 58 576 356, 以下描述演示了具体的排序过程(红色字体表示正在排序的数位)

第一次排序(个位):

3 4 2

5 7 6

3 5 6

0 5 8

第二次排序(十位):

3 4 2

3 5 6

0 5 8

5 7 6

第三次排序(百位):

0 5 8

3 4 2

3 5 6

5 7 6

结果: 58 342 356 576

两个问题:

• 为什么要从低位开始向高位排序?

        如果要从高位排序, 那么次高位的排序会影响高位已经排好的大小关系. 在数学中, 数位越高,数位值对数的大小的影响就越大.从低位开始排序,就是对这种影响的排序. 数位按照影响力从低到高的顺序排序, 数位影响力相同则比较数位值.

• 为什么同一数位的排序子程序要使用稳定排序?

        稳定排序的意思是指, 待排序相同元素之间的相对前后关系,在各次排序中不会改变.比如实例中具有十位数字5的两个数字58和356, 在十位排序之前356在58之前,在十位排序之后, 356依然在58之前.

        稳定排序能保证,上一次的排序成果被保留,十位数的排序过程能保留个位数的排序成果,百位数的排序过程能保留十位数的排序成果.

-----------------------------我是分割线-----------------------------------------------------