2.8 鸽巢排序

2017-01-21 17:19:08 4,379 2

基数排序(radix sort)属于“分配式排序”(distribution sort),又称“桶排序”(bucket sort)。为了说明这一算法,我们先以基数排序的一个特例鸽巢排序(Pigeonhole sort)来进行讲解

鸽巢排序

1、数组中没有重复的元素,且每个元素都>=0

先考虑一种最简单的情况,对一个数组array:{11, 13, 56, 23, 63, 98 ,87}进行排序,注意这个数组中没有重复的元素,且都是>=0那么:

第一步:遍历这个数组,找出其中最大数字(maxNum)

第二步:创建一个辅助数组bucketArray,大小是maxNum+1,辅助元素中的每一个元素称之为一个"桶"

第三步:遍历待排序的数组array,将每一个元素分配(distribution)到辅助数组bucketArray中,分配的方式很简单,bucketArray[array[i]]=array[i],即直接将这个位置上的数字array[i]bucketArray数组的下标,并给其赋值为array[i],即数组的下标和数组元素的值是相同的

QQ截图20170121162306.png

第四步:可以看到,经过第三步排序之后,辅助数组bucketArray中的元素已经有序的了,现在只需要迭代辅助数组,将不是null的元素依次拷贝到待排序数组中,即完成了排序

代码实现如下:

public class PigeonholeSort {
    /**
     * 第一种情况:所有元素都>=0
     */
    public static void sort(int[] arr){

        //第一步,确定数组中最大的元素
        int max=arr[0];
        for (int i : arr) {
            if(i>max){
                max=i;
            }
        }

        //第二步:创建辅助数组,大小为max+1,注意这里是Integer,所以默认每个元素的值都是null
        Integer[] bucketArray=new Integer[max+1];

        //第三步:将数组中的分配到bucket数组中
                for (int i = 0; i < array.length; i++) {
                    bucketArray[array[i]-minNum]=array[i];
                }

        //第四步:迭代辅助数组,将不是null的元素依次拷贝到待排序数组中
                int index=-1;
                for (int i = 0; i < bucketArray.length; i++) {
                    if(bucketArray[i]!=null){
                        array[++index]=bucketArray[i];
                    }
                }
    }
    
      public static void main(String[] args) {
        int[] arr={11, 13, 56, 23, 63, 98 ,87};
        System.out.println("排序前:"+ Arrays.toString(arr));
        sort(arr);
        System.out.println("排序后:"+ Arrays.toString(arr));
    }
}

运行程序,输出

排序前:[11, 13, 56, 23, 63, 98, 87]

排序后:[11, 13, 23, 56, 63, 87, 98]

2、数组中没有重复的元素,数据元素有正有负

在上面的案例中,我们假设所有的元素都是>=0,因此可以直接按照数组下标进行分配,那么如果现在存在负数呢?此时我们要按照如下方案进行修改:

第一步应该找出最大数字maxNum和最小数字minNum

  • 第二步:辅助数组bucketArray的长度不再是待排序数组array的最大元素maxNum+1,而是maxNum-minNum+1

  • 第三步:在分配元素到临时数组时,下标应该按照如下方案计算:bucketArray[array[i]-minNum]=array[i]  

  • 第四步:不变

修改后的代码如下所示:

public class PigeonholeSort {

    public static void sort(int[] array){

        //第一步,确定数组中最大的元素和最小元素
        int maxNum=array[0];
        int minNum=array[0];
        for (int i : array) {
            if(i>maxNum){
                maxNum=i;
            }
            if(i<minNum){
                minNum=i;
            }
        }

        //第二步:创建辅助数组,大小为max-min+1,注意这里是Integer,所以默认每个元素的值都是null
        int bucketArrayLength = maxNum - minNum + 1;
        Integer[] bucketArray=new Integer[bucketArrayLength];

        //第三步:将数组中的分配到bucket数组中
        for (int i = 0; i < array.length; i++) {
            bucketArray[array[i]-minNum]=array[i];
        }

        //第四步:迭代辅助数组,将不是null的元素依次拷贝到待排序数组中
        int index=-1;
        for (int i = 0; i < bucketArray.length; i++) {
            if(bucketArray[i]!=null){
                array[++index]=bucketArray[i];
            }
        }
    }

    public static void main(String[] args) {
        int[] arr={11, 13, 56, -23, 63, 98 ,87};//注意这个数组中存在一个负数
        System.out.println("排序前:"+ Arrays.toString(arr));
        sort(arr);
        System.out.println("排序后:"+ Arrays.toString(arr));
    }
}

运行程序,输出


排序前:[11, 13, 56, -23, 63, 98, 87]

排序后:[-23, 11, 13, 56, 63, 87, 98]

3、数组中存在重复的元素,数据元素有正有负


  当数组中存在重复的元素时,例如所有元素都相同{5,5,5,5,4},那么按照上面的计算辅助数组大小就会有错,此时按照如下方式计算辅助数组长度:

MAX((maxNum-minNum+1),array.length)

 此外,在给辅助数据分配元素的时候,可能存在相同元素的值,已经占用了一个位置,因此考虑顺延到下一个位置

修改后的代码如下所示:

public class PigeonholeSort {

    public static void sort(int[] array){

        //第一步,确定数组中最大的元素和最小元素
        int maxNum=array[0];
        int minNum=array[0];
        for (int i : array) {
            if(i>maxNum){
                maxNum=i;
            }
            if(i<minNum){
                minNum=i;
            }
        }

        //第二步:创建辅助数组,大小为max-min+1,注意这里是Integer,所以默认每个元素的值都是null
        int bucketArrayLength = Math.max(maxNum - minNum + 1,array.length);
        Integer[] bucketArray=new Integer[bucketArrayLength];

        //第三步:将数组中的分配到bucket数组中
        for (int i = 0; i < array.length; i++) {
            int distributionIndex = array[i] - minNum;
            while (true){
                if(bucketArray[distributionIndex]==null){
                    bucketArray[distributionIndex]=array[i];
                    break;
                }else{
                    distributionIndex++;
                }
            }

        }

        //第四步:迭代辅助数组,将不是null的元素依次拷贝到待排序数组中
        int index=-1;
        for (int i = 0; i < bucketArray.length; i++) {
            if(bucketArray[i]!=null){
                array[++index]=bucketArray[i];
            }
        }
    }

    public static void main(String[] args) {
        int[] arr={11, 13, 56,56, -23, 63, 56 ,87};//注意这个数组中存在一个负数,且有重复元素
        System.out.println("排序前:"+ Arrays.toString(arr));
        sort(arr);
        System.out.println("排序后:"+ Arrays.toString(arr));
    }
}

运行程序输出

排序前:[11, 13, 56, 56, -23, 63, 56, 87]

排序后:[-23, 11, 13, 56, 56, 56, 63, 87]

总结

鸽巢排序的时间复杂度为(O(n)),执行速度快于任何一种排序,但其却需要很大的辅助空间,而且其适用于很少的数值范围内的排序。当待排序数组中出现很多不相等的元素是,鸽巢排序的效率会降低。鸽巢排序的辅助数组的大小取决与待排序数组的数值范围,辅助空间的大小为待排序数组中的最大值与最小值之差加1。比如有序列{11, 13, 56, 23, 63, 23, 98 ,87},则复制数组需要98-11+1=88个空间。 

我们一般很少使用鸽巢排序, 因为它很少可以在灵活性, 简便性, 尤是速度上超过其他排序算法. 事实上, 桶排序较鸽巢排序更加的实用


上一篇:2.7 快速排序 下一篇:3.1 二叉树