一些非比较排序

在LeetCode中有个题目叫Maximum Gap。是求一个非排序的正数数列中按顺序排列后的最大间隔。这个题用桶排序和基数排序都能够实现。以下说一下桶排序、基数排序和计数排序这三种非比較排序。

桶排序

这样的排序的主要思想是。把数列分配到多个桶中，然后再在各个桶中使用排序算法进行排序。当然也能够继续使用桶排序。

如果数组的最大值是A，最小值是B，长度是L，则每一个桶的大小能够是S=Max(1,(A-B)/(L-1))则能够分为(A-B)/S+1个桶。

对于数列中的数字x。用(x-B)/S 来得到x应该在的桶的序号，然后把x放在对应的桶中。

循环上面步骤。

桶排序对于数列中的数字是均匀排列的情况很适用。

以下贴一个Leetcode Maximum Gap 的代码，当中用了桶排序的思想

class Solution:

    # @param num, a list of integer

    # @return an integer

    def maximumGap(self, num):

        N = len(num)

        if N < 2:

            return 0

        A = min(num)

        B = max(num)

        bucketRange = max(1, int((B - A - 1) / (N - 1)) + 1) #ceil( (B - A) / (N - 1) )

        bucketLen = ((B - A) / bucketRange + 1)

        buckets = [None] * bucketLen

        for K in num:

            loc = (K - A) / bucketRange

            bucket = buckets[loc]

            if bucket is None:

                bucket = {'min' : K, 'max' : K}

                buckets[loc] = bucket

            else:

                bucket['min'] = min(bucket['min'], K)

                bucket['max'] = max(bucket['max'], K)

        maxGap = 0

        for x in range(bucketLen):

            if buckets[x] is None:

                continue

            y = x + 1

            while y < bucketLen and buckets[y] is None:

                y += 1

            if y < bucketLen:

                maxGap = max(maxGap, buckets[y]['min'] - buckets[x]['max'])

            x = y

        return maxGap

基数排序

基数排序严蔚敏的数据结构中有具体介绍。主要是思想是用数字的keyword基数进行分配。这里的keyword基数一般是是进制的基数。比方十进制的话就是10，二进制就是2。通常使用链式基数排序，主要就是分配和和收集的过程。分配是里按keyword的不同值分配到各个队列中。然后收集。反复运行这个过程。

计数排序

计数排序是直接计算数字x在数列中应该在的位置。统计比它小的数字有多少个就知道它的位置了。

一个简单的C代码

void COUNTINGSORT(int *A, int *B, int array_size, int k)

{

        int C[k+1], i, value, pos;

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

        {

            C[i] = 0;

        }

        for(i=0; i< array_size; i++)

        {

            C[A[i]] ++;

        }

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

        {

            C[i] = C[i] + C[i-1];

        }

        for(i=array_size-1; i>=0; i--)

        {

            value = A[i];

            pos = C[value];

            B[pos-1] = value;

            C[value]--;

        }

}

最后贴一张各个排序算法的时间复杂度

參考文献：

1、 http://www.cnblogs.com/kaituorensheng/archive/2013/02/23/2923877.html

2、http://bookshadow.com/weblog/2014/12/14/leetcode-maximum-gap/

3、http://hxraid.iteye.com/blog/646760