算法基础03——排序之桶、基数、希尔排序

桶排序

桶排序 (Bucket sort)或所谓的箱排序,是一个排序算法,工作的原理是将数组分到有限数量的桶子里。每个桶子再个别排序(有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序)。桶排序是鸽巢排序的一种归纳结果。当要被排序的数组内的数值是均匀分配的时候,桶排序使用线性时间(Θ(n))。但桶排序并不是 比较排序,他不受到 O(n log n) 下限的影响。

桶排序是将待排序集合中处于同一个值域的元素存入同一个桶中,也就是根据元素值特性将集合拆分为多个区域,则拆分后形成的多个桶,从值域上看是处于有序状态的。对每个桶中元素进行排序,则所有桶中元素构成的集合是已排序的。

回想快速排序我们将集合拆分为两个值域,这里称为两个桶,再分别对两个桶进行排序,最终完成排序。桶排序则是将集合拆分为多个桶,对每个桶进行排序,则完成排序过程。两者不同之处在于,快排是在集合本身上进行排序,属于原地排序方式,且对每个桶的排序方式也是快排。桶排序则是提供了额外的操作空间,在额外空间上对桶进行排序,避免了构成桶过程的元素比较和交换操作,同时可以自主选择恰当的排序算法对桶内进行排序。

当然桶排序更是对计数排序的改进,计数排序申请的额外空间跨度从最小元素值到最大元素值,若待排序集合中元素不是依次递增的,则必然有空间浪费情况。桶排序则是弱化了这种浪费情况,将最小值到最大值之间的每一个位置申请空间,更新为最小值到最大值之间每一个固定区域申请空间,尽量减少了元素值大小不连续情况下的空间浪费情况。

桶排序过程中存在两个关键环节:

  1. 元素值域的划分,也就是元素到桶的映射规则。映射规则需要根据待排序集合的元素分布特性进行选择,若规则设计的过于模糊、宽泛,则可能导致待排序集合中所有元素全部映射到一个桶上,则桶排序向比较性质排序算法演变。若映射规则设计的过于具体、严苛,则可能导致待排序集合中每一个元素值映射到一个桶上,则桶排序向计数排序方式演化。

  2. 排序算法的选择,从待排序集合中元素映射到各个桶上的过程,并不存在元素的比较和交换操作,在对各个桶中元素进行排序时,可以自主选择合适的排序算法,桶排序算法的复杂度和稳定性,都根据选择的排序算法不同而不同。

算法过程

  1. 根据待排序集合中最大元素和最小元素的差值范围和映射规则,确定申请的桶个数;
  2. 遍历待排序集合,将每一个元素移动到对应的桶中;
  3. 对每一个桶中元素进行排序,并移动到已排序集合中。

public class BucketSort {

    public static void bucketSort(int[] arr) {
        // 新建一个桶的集合
        ArrayList<LinkedList<Integer>> buckets = new ArrayList<LinkedList<Integer>>();
        for (int i = 0; i < 10; i++) {
            // 新建一个桶,并将其添加到桶的集合中去。
            // 由于桶内元素会频繁的插入,所以选择 LinkedList 作为桶的数据结构
            buckets.add(new LinkedList<Integer>());
        }
        // 将输入数据全部放入桶中并完成排序
        for (int data : arr) {
            int index = getBucketIndex(data);
            insertSort(buckets.get(index), data);
        }
        // 将桶中元素全部取出来并放入 arr 中输出
        int index = 0;
        for (LinkedList<Integer> bucket : buckets) {
            for (Integer data : bucket) {
                arr[index++] = data;
            }
        }
    }
 
    /**
     * 计算得到输入元素应该放到哪个桶内
     */
    public static int getBucketIndex(int data) {
        // 实际开发中需要根据场景具体设计
        return data;
    }
 
    /**
     * 用插入排序作为桶内元素排序的方法 每当有一个新元素到来时将其插入到恰当的位置
     */
    public static void insertSort(List<Integer> bucket, int data) {
        ListIterator<Integer> it = bucket.listIterator();
        boolean insertFlag = true;
        while (it.hasNext()) {
            if (data <= it.next()) {
                it.previous(); // 把迭代器的位置偏移回上一个位置
                it.add(data); // 把数据插入到迭代器的当前位置
                insertFlag = false;
                break;
            }
        }
        if (insertFlag) {
            bucket.add(data); // 否则把数据插入到链表末端
        }
    }
}

基数排序

基数排序(radix sort)属于“分配式排序”(distribution sort),又称“桶子法”(bucket sort)或bin sort,顾名思义,它是透过键值的部份资讯,将要排序的元素分配至某些“桶”中,藉以达到排序的作用,基数排序法是属于稳定性的排序,其时间复杂度为O (nlog(r)m),其中r为所采取的基数,而m为堆数,在某些时候,基数排序法的效率高于其它的稳定性排序法。

基数排序就是以每一位的数值为关键字来排序,也就是说,是按位排序(一般从低位向高位枚举)

  1. 创建10个桶(队列)分别给每个数位(0到9)

  2. 遍历每个数位

  3. 遍历数列中的每个元素

  4. 将元素移至相应的桶中

  5. 在每个桶中,从最小的数位开始

  6. 当桶不是空的

  7. 将元素恢复至数列中

基数排序算法可视过程

/**
 * 基数排序 
 * 和桶排序 差不多不过 是用的位数的基数进行的排序
 * @author yixunfei
 *
 */
public class RadixSort {

    public int[] sort(int[] sourceArray) throws Exception {
        // 对 arr 进行拷贝,不改变参数内容
        int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);

        int maxDigit = getMaxDigit(arr);
        return radixSort(arr, maxDigit);
    }

    /**
     * 获取最高位数
     */
    private int getMaxDigit(int[] arr) {
        int maxValue = getMaxValue(arr);
        return getNumLenght(maxValue);
    }

    private int getMaxValue(int[] arr) {
        int maxValue = arr[0];
        for (int value : arr) {
            if (maxValue < value) {
                maxValue = value;
            }
        }
        return maxValue;
    }

    protected int getNumLenght(long num) {
        if (num == 0) {
            return 1;
        }
        int lenght = 0;
        for (long temp = num; temp != 0; temp /= 10) {
            lenght++;
        }
        return lenght;
    }

    private int[] radixSort(int[] arr, int maxDigit) {
        int mod = 10;
        int dev = 1;

        for (int i = 0; i < maxDigit; i++, dev *= 10, mod *= 10) {
            // 考虑负数的情况,这里扩展一倍队列数,其中 [0-9]对应负数,[10-19]对应正数 (bucket + 10)
            int[][] counter = new int[mod * 2][0];

            for (int j = 0; j < arr.length; j++) {
                int bucket = ((arr[j] % mod) / dev) + mod;
                counter[bucket] = arrayAppend(counter[bucket], arr[j]);
            }

            int pos = 0;
            for (int[] bucket : counter) {
                for (int value : bucket) {
                    arr[pos++] = value;
                }
            }
        }

        return arr;
    }

    /**
     * 自动扩容,并保存数据
     *
     * @param arr
     * @param value
     */
    private int[] arrayAppend(int[] arr, int value) {
        arr = Arrays.copyOf(arr, arr.length + 1);
        arr[arr.length - 1] = value;
        return arr;
    }
}

希尔排序

希尔排序(Shell's Sort)是插入排序的一种又称“缩小增量排序”(Diminishing Increment Sort),是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法因D.L.Shell于1959年提出而得名。

希尔排序是把记录按下标的一定增量分组,对每组使用直接插入排序算法排序;随着增量逐渐减少,每组包含的关键词越来越多,当增量减至1时,整个文件恰被分成一组,算法便终止。

我们知道插入排序在对大部分已经有序的数据操作时,效率高,即可以达到线性排序的效率;

但插入排序一般来说是低效的,因为插入排序每次只能将数据移动一位;

希尔排序的基本思想是:首先把较大的数据集合分割成若干个小组(逻辑上分组),然后对每一个小组分别进行插入排序,此时,插入排序所作用的数据量比较小(每一个小组),插入的效率比较高。

public class ShellSort {

	public static void sort(int[] arr) {
		// 增量每次都/2
		for (int step = arr.length / 2; step > 0; step /= 2) {
			// 从增量那组开始进行插入排序,直至完毕
			for (int i = step;  i < arr.length;  i ++) {
				int j = i;
				int temp = arr[j];
				// j - step 就是代表与它同组隔壁的元素
				while (j - step >= 0 && arr[j - step] > temp) {
					arr[j] = arr[j - step];
					j = j - step;
				}
				arr[j] = temp;
			}
		}
	}
}


更新时间:2020-03-02 10:50:47

本文由 寻非 创作,如果您觉得本文不错,请随意赞赏
采用 知识共享署名4.0 国际许可协议进行许可
本站文章除注明转载/出处外,均为本站原创或翻译,转载前请务必署名
原文链接:https://www.zhouning.group/archives/算法基础03排序之桶基数希尔排序
最后更新:2020-03-02 10:50:47

评论

Your browser is out of date!

Update your browser to view this website correctly. Update my browser now

×