由Maximum Gap,对话桶排序,基数排序和统计排序

一些非比较排序

在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]--;
}
}

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

由Maximum Gap,对话桶排序,基数排序和统计排序

由Maximum Gap,对话桶排序,基数排序和统计排序

參考文献:

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

版权声明:本文博客原创文章,博客,未经同意,不得转载。

上一篇:Web QQ自动强制加好友代码


下一篇:mysql 查表失败