你所忽视的排序算法（下）

你所不知道的排序算法下篇更新啦，相比于上篇介绍的，下篇的几种排序算法相对来说比较少见。最近也花了一点时间来理解。话不多说，我们进入正文。

今天出场的是：快速排序，堆排序，计数排序，桶排序。

快速排序

快速排序（Quicksort），又称划分交换排序（partition-exchange sort），简称快排。最早是由东尼·霍尔提出来。快速排序的基本思想是使用分治法（Divide and conquer）策略来把一个序列（list）分为两个子序列（sub-lists）。其中一个序列关键字均比另一个序列关键字小，则可分别对这两个子序列继续进行排序，已达到整个序列有序。

逻辑描述
  • 从数列中挑出一个元素，称为“基准”（pivot）
  • 重新排序数列，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面（相同的数可以到任何一边）。在这个分割结束之后，该基准就处于数列的中间位置。这个称为分割（partition）操作。
  • 递归地（recursively）把小于基准值元素的子数列和大于基准值元素的子数列排序

递归到最底部时，数列的大小是零或一，也就是已经排序好了。这个算法一定会结束，因为在每次的迭代（iteration）中，它至少会把一个元素摆到它最后的位置去。

代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public static void quickSort(int[] arr, int head, int tail) {
        if (head >= tail || arr == null || arr.length <= 1) {
            return;
        }
        int i = head, j = tail;
    	int pivot = arr[(head + tail) / 2];
        while (i <= j) {
            while (arr[i] < pivot) {
                ++i;
            }
            while (arr[j] > pivot) {
                --j;
            }
            if (i < j) {
                int t = arr[i];
                arr[i] = arr[j];
                arr[j] = t;
                ++i;
                --j;
            } else if (i == j) {
                ++i;
            }
        }
        quickSort(arr, head, j);
        quickSort(arr, i, tail);
    }

算法分析

快速排序是二叉查找树（二叉搜索树）的一个空间最优化版本。不是循序地把数据项插入到一个明确的树中，而是由快速排序组织这些数据项到一个由递归调用所隐含的树中。快速排序的最直接竞争者是堆排序（Heapsort）。堆排序比快速排序稍微慢，但是最坏情况的运行时间总是{\displaystyle O(n\log n)}

堆排序

堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构，并同时满足堆积的性质：即子节点的键值或索引总是小于（或者大于）它的父节点。

这里多一句嘴来帮助理解一下堆有关的操作。

堆节点的访问：通常堆是通过一维数组来实现的，在数组起始位置为0的情况下：

  • 父节点i的左子节点在位置2i+1；
  • 父节点i的右子节点在位置2i+2；
  • 子节点i的父节点在位置floor((i-1)/2)；

堆的操作：在堆的数据结构中，堆中的最大值总是位于根节点（在优先队列中使用堆的话，队中的最小值位于根节点）。堆中定义一下几种操作：

  • 最大堆调整（Max Heapify）：将堆的末端子节点作调整，使得子节点永远小于父节点
  • 创建最大堆（Build Max Heap）：将堆中的所有数据重新排序
  • 堆排序（Heap Sort）：移除位在第一个数据的根节点，并做最大堆调整的递归运算
逻辑描述
  • 将初始待排序关键字序列(R1,R2….Rn)构建成大顶堆，此堆为初始的无序区
  • 将堆顶元素R[1]与最后一个元素R[n]交换，此时得到新的无序区(R1,R2,……Rn-1)和新的有序区(Rn),且满足R[1,2…n-1]<=r[n]
  • 由于交换后新的堆顶R[1]可能违反堆的性质，因此需要对当前无序区(R1,R2,……Rn-1)调整为新堆，然后再次将R[1]与无序区最后一个元素交换，得到新的无序区(R1,R2….Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到有序区的元素个数为n-1，则整个排序过程完成
代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
package org.pross.sort;

import java.util.Arrays;

/**
 * Author: shawn pross
 * Date: 2018/11/9
 * Description: 堆排序
 */
public class HeapSort {
        private int[] arr;
        public HeapSort(int[] arr){
            this.arr = arr;
        }

        public void sort(){
            /**
             *  第一步：将数组堆化
             *  beginIndex = 第一个非叶子节点。
             *  从第一个非叶子节点开始即可。无需从最后一个叶子节点开始。
             *  叶子节点可以看作已符合堆要求的节点，根节点就是它自己且自己以下值为最大。
             */
            int len = arr.length - 1;
            int beginIndex = (len - 1) >> 1;
            for(int i = beginIndex; i >= 0; i--){
                maxHeapify(i, len);
            }

            /**
             * 第二步：对堆化数据排序
             * 每次都是移出最顶层的根节点A[0]，与最尾部节点位置调换，同时遍历长度 - 1。
             * 然后从新整理被换到根节点的末尾元素，使其符合堆的特性。
             * 直至未排序的堆长度为 0。
             */
            for(int i = len; i > 0; i--){
                swap(0, i);
                maxHeapify(0, i - 1);
            }
        }

        private void swap(int i,int j){
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }

        /**堆调整
         * 调整索引为 index 处的数据，使其符合堆的特性。
         * @param index 需要堆化处理的数据的索引
         * @param len 未排序的堆（数组）的长度
         */
        private void maxHeapify(int index,int len){
            // 左子节点索引
            int li = (index << 1) + 1;
            // 右子节点索引
            int ri = li + 1;
            // 子节点值最大索引，默认左子节点。
            int cMax = li;

            // 左子节点索引超出计算范围，直接返回。
            if(li > len) return;
            // 先判断左右子节点，哪个较大。
            if(ri <= len && arr[ri] > arr[li])
                cMax = ri;
            if(arr[cMax] > arr[index]){
                // 如果父节点被子节点调换，
                swap(cMax, index);
                // 则需要继续判断换下后的父节点是否符合堆的特性。
                maxHeapify(cMax, len);
            }
        }

        public static void main(String[] args) {
            int[] arr = new int[]{3,5,3,0,8,6,1,5,8,6,2,4,9,4,7,0,1,8,9,7,3,1,2,5,9,7,4,0,2,6};
            new HeapSort(arr).sort();
            System.out.println(Arrays.toString(arr));
        }
}

计数排序

计数排序（CountingSort）是一种稳定的线性时间排序算法。其核心在于将输入的数据值转化为键存储在额外开辟的数组空间中，作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。

逻辑描述
  • 找出待排序的数组中最大和最小的元素
  • 统计数组中每个值为i的元素出现的次数，存入数组C的第i项
  • 对所有的计数累加（从数组C中的第一个元素开始，每一项和前一项相加）
  • 反向填充目标数组：将每个元素i在新数组的第C(i)项，每放一个元素就将C(i)减去1
代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
package org.pross.sort;

/**
 * Author: shawn pross
 * Date: 2018/11/9
 * Description: 计数排序
 */
public class CountingSort {

    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;
        }
        // 求计数和
        for (int i = 1; i < k; i++) {
            C[i] = C[i] + C[i - 1];
        }
        // 整理
        for (int j = A.length - 1; j >= 0; j--) {
            int a = A[j];
            B[C[a] - 1] = a;
            C[a] -= 1;
        }
    }

    public static void main(String[] args) {
        int[] A = CountingSort.countingSort(new int[]{16, 4, 10, 14, 7, 9, 3, 2, 8, 1});
        for (int digint : A) {
            System.out.print(digint + ",");
        }
    }
}
算法分析

计数排序是一个稳定的排序算法。当输入的元素是n个0到k之间的整数时，时间复杂度是O(n+k)，空间复杂度也是O(n+k)，其排序速度快于任何比较排序算法。

桶排序

桶排序（Bucket sort）或所谓的箱排序，是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。桶排序的工作的原理：假设输入数据服从均匀分布，将数据分到有限数量的桶里，每个桶再分别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排）。

逻辑描述
  • 设置一个定量的数组当作空桶
  • 遍历输入数据，并且把数据一个一个放到对应的桶里去
  • 对每个不是空的桶进行排序
  • 从不是空的桶里把排好序的数据拼接起来。
代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
package org.pross.sort;

import java.util.ArrayList;
import java.util.List;

/**
 * Author: shawn pross
 * Date: 2018/11/10
 * Description:
 */
public class BucketSort {

    private static int indexFor(int a, int min, int step) {
        return (a - min) / step;
    }

    public static int[] bucketSort(int[] array) {
        int max = array[0], min = array[0];
        for (int a : array) {
            if (max < a)
                max = a;
            if (min > a)
                min = a;
        }
        // bucketNum的值可以根据实际情况选择
        int bucketNum = max / 10 - min / 10 + 1;
        List buckList = new ArrayList<List<Integer>>();
        // create bucket
        for (int i = 1; i <= bucketNum; i++) {
            buckList.add(new ArrayList<Integer>());
        }
        // push into the bucket
        for (int i = 0; i < array.length; i++) {
            int index = indexFor(array[i], min, 10);
            ((ArrayList<Integer>) buckList.get(index)).add(array[i]);
        }
        ArrayList<Integer> bucket = null;
        int index = 0;
        for (int i = 0; i < bucketNum; i++) {
            bucket = (ArrayList<Integer>) buckList.get(i);
            insertSort(bucket);
            for (int k : bucket) {
                array[index++] = k;
            }
        }
        return array;
    }

    // 把桶內元素插入排序
    private static void insertSort(List<Integer> bucket) {
        for (int i = 1; i < bucket.size(); i++) {
            int temp = bucket.get(i);
            int j = i - 1;
            for (; j >= 0 && bucket.get(j) > temp; j--) {
                bucket.set(j + 1, bucket.get(j));
            }
            bucket.set(j + 1, temp);
        }
    }

    public static void main(String[] args) {
        int[] array = {100, 93, 97, 92, 96, 99, 92, 89, 93, 97, 90, 94, 92, 95};
        int[] sort = bucketSort(array);
        for(int digint:sort){
            System.out.print(digint+",");
        }
    }
}
算法分析

桶排序最好情况下使用线性时间O(n)，桶排序的时间复杂度，取决与对各个桶之间数据进行排序的时间复杂度，因为其它部分的时间复杂度都为O(n)。很显然，桶划分的越小，各个桶之间的数据越少，排序所用的时间也会越少。但相应的空间消耗就会增大。