封面画师：Nengoro(ネんごろぅ)     封面ID：78467492

本文参考视频：小马哥教育(SEEMYGO) 2019年 恋上数据结构与算法（第二季）

源码仓库：mofan212/data-structure-and-algorithm (github.com)

辅助学习网址：数据结构和算法动态可视化     Data Structure Visualizations

执行流程：本文统一以升序为例子。

0. 初识排序

0.1 含义

什么是排序？

其实我不想说的，但是我觉得还是说一下好。😹

排序前： 3、1、6、9、2、5、8、4、7

排序后： 1、2、3、4、5、6、7、8、9（升序）或者9、8、7、6、5、4、3、2、1（降序）

0.2 十大排序算法

十大排序算法

以上表格是基于数组进行排序的一般性结论。

以上表格仅供参考，不同的人实现的算法不一样，会导致复杂度不一样。

冒泡、选择、插入、归并、快速、希尔、堆排序，属于比较排序（Comparison Sorting）

1. 冒泡排序

1.1 初步实现

冒泡排序（Bubble Sort）的升序排序流程：

1、从头开始比较每一对相邻元素，如果第一个比第二个大，就交换他们的位置

  • 执行完一轮后，最末尾那个元素就是最大的元素

2、忽略第一步中找到的最大元素，重复执行步骤一，直到全部元素有序

初始数据为{29, 10, 14, 37, 5, 18, 22}，冒泡排序过程动图：

BubbleSort

初步实现的代码如下：

1
2
3
4
5
6
7
8
9
10
11
static void bubbleSort1(Integer[] array) {
    for (int end = array.length - 1; end > 0; end--) {
        for (int begin = 1; begin <= end; begin++) {
            if (array[begin] < array[begin - 1]) {
                int tmp = array[begin];
                array[begin] = array[begin - 1];
                array[begin - 1] = tmp;
            }
        }
    }
}

1.2 优化一

如果序列已经完全有序，可以提前终止冒泡排序。

其实我们在第一趟排序的时候就可以知道这个序列是不是完全有序的了，即：第一次进入第二层for循环没有进入if判断就可以断定这个序列是有序的了。

从这里我们还可以引申一下： 如果我们进行了若干次第一层for循环后，序列很有可能已经完全有序了，这个时候也可以提前终止排序。

因此得到优化后的代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
static void bubbleSort2(Integer[] array) {
    for (int end = array.length - 1; end > 0; end--) {
        boolean sorted = true;
        for (int begin = 1; begin <= end; begin++) {
            if (array[begin] < array[begin - 1]) {
                int tmp = array[begin];
                array[begin] = array[begin - 1];
                array[begin - 1] = tmp;
                sorted = false;
            }
        }
        if (sorted) break;
    }
}

我们可以对优化前后的方法进行测试，生成 1w 个随机数，范围是[1, 10000] ，这两个方法耗时如下：

冒泡优化一后的随机测试比较

我们发现结果非常的Amazing啊，不是说优化吗？怎么优化后的耗时还变多了呢？😟

一脸懵逼

莫“ 方 ”，这是正常现象，我们的优化不是针对有序的序列进行优化的吗？而我们这里生成了1w个随机数，这么多的随机数是很难达到完全有序的。第二种方式相比于第一种多了三种操作：

冒泡优化一多做的操作

正是因为基本无法在第一层循环玩前达到完全有序，导致多做的操作反而成了“累赘”，导致效率降低。

如果我们生成1w个升序的数，范围是[1, 10000]，得到的测试结果如下：

冒泡优化一后的升序测试比较

这下我们发现耗时有了明显的减少，第二种方式甚至耗时为0，证明我们的优化是有作用的！

1.3 优化二

从优化一的测试中我们发现，序列完全有序的情况是很低的，像优化一那样做，很有可能导致最后的效率还没有我们最开始实现的方式效率高。

那有没有更好的优化方案呢？😕

那肯定是有的。😎

方法： 如果序列尾部已经局部有序，可以记录最后1次交换的位置，减少比较次数。

假设现有这样一组数据：

冒泡优化二数据

PS ： 最后一次交换的位置是 6 。

我们发现在这组数据中，末尾的几个数据都是有序（升序）的，那很明显这些有序数据进行一次比较记录下最后一次交换的位置就行了，后面就不需要比较它们了，以达到效率的提升。

同时我们还需要注意一点，当我们对末尾有序的序列进行若干次第一层for循环后，末尾有序的数据长度可能会增加，我们个时候对这些数据也不进行比较。（就是说末尾有序的数据长度可能会变，我们第一层for循环的结束位置也要跟着变）

为此，我们需要增加一个局部变量sortedIndex，用来记录最后一次交换的位置，然后在下次进行第一次for循环时就到sortedIndex位置结束即可。

因此得到优化后的代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
static void bubbleSort3(Integer[] array) {
    for (int end = array.length - 1; end > 0; end--) {
        // sortedIndex的初始值在数组完全有序的时候有用
        int sortedIndex = 1;
        for (int begin = 1; begin <= end; begin++) {
            if (array[begin] < array[begin - 1]) {
                int tmp = array[begin];
                array[begin] = array[begin - 1];
                array[begin - 1] = tmp;
                // 记录最后一次交换的位置
                sortedIndex = begin;
            }
        }
        end = sortedIndex;
    }
}

我们可以对三种方式进行测试，生成 1w 个升序的数，范围是[1, 10000]，得到的测试结果如下：

冒泡优化二后的升序测试比较

我们发现第二种方式和第三种方式的耗时一样，甚至为0，相比于第一种效率提高了不少。

如果我们生成 1w 个数，范围是[1, 10000]，其中前2k个数乱序的，后8k个是有序的 ，最终得到的测试结果如下：

冒泡优化二后的尾部有序测试比较

我们发现第三种方式相比于第二种的耗时又减少了不少，效率得到了提高，证明我们的优化是有作用的。😜

复杂度

最坏时间复杂度： O(n2)

最坏的情况就是在我们增加的操作完全没用上的情况下，这个时候的效率跟最开始实现的方式效率一样。

平均时间复杂度： O(n2)

最好时间复杂度： O(n)

最好的情况就是在我们进行排序的序列一开始就是完全有序的情况下。

空间复杂度： O(1)

1.4 排序算法的稳定性

稳定性（Stability），排序算法的稳定性指的是：如果相等的两个元素，在排序前后的相对位置保持不变，那么这就是稳定的排序算法。比如：

排序前： 5 , 1 , 3a , 4 , 7 , 3b

稳定的排序： 1 , 3a , 3b , 4 , 5 , 7

不稳定的排序： 1 , 3b , 3a , 4 , 5 , 7

我们在前文中进行排序的序列类型都是整形，但在一般情况下，我们需要对自定义对象进行排序 ，这个时候稳定性就会影响最终的排序效果。

我们前文说的冒泡排序就是一种稳定的排序算法。

但是需要注意的一点是：稍有不慎，稳定的排序算法也能写成不稳定的排序算法，比如下面给出的一种冒泡排序代码就是不稳定的：

1
2
3
4
5
6
7
8
for (int end = array.length - 1; end > 0; end--) {
    for (int begin = 1; begin <= end; begin++) {
         // 变成了小于等于，这个时候前后两数相等时也会进行交换
        if (cmp(begin, begin - 1) <= 0) {
           swap(begin, begin - 1);
        }
    }
}

1.5 原地算法

原地算法（In-place Algorithm），就是指不依赖额外的资源或者依赖少数的额外资源，仅依靠输出来覆盖输入 。

空间复杂度为 O(1) 的算法都可以认为是原地算法，

非原地算法，成为 Not-in-place 或者 Out-of-place 。

冒泡排序属于 In-place 。

2. 选择排序

选择排序（Selection Sort）的升序排序流程：

1、从序列中找出最大的那个元素，然后与最末尾的元素交换位置。

  • 执行完一轮后，最末尾那个元素就是最大的元素

2、忽略第一步中找到的最大元素，重复执行步骤一，直到全部元素有序

初始数据为{29, 10, 14, 37, 5, 18, 22}，选择排序过程动图：

PS： 当然选择排序也可以选出序列中最小的元素和首位的元素进行交换位置， 下图给出的是选择最小的元素进行交换 ，我们待会编码的时候可以选择最大的元素进行交换 ，方便与冒泡排序进行对比。

SelectionSort

我们选择最大的元素与最后的元素进行交换，初步实现的代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
static void selectionSort(Integer[] array) {
    for (int end = array.length - 1; end > 0; end--) {
        int maxIndex = 0;
        for (int begin = 1; begin <= end; begin++) {
            if (array[maxIndex] < array[begin]) {
                maxIndex = begin;
            }
        }
        int tmp = array[maxIndex];
        array[maxIndex] = array[end];
        array[end] = tmp;
    }
}

冒泡排序 VS 选择排序

选择排序的交换次数要远远少于冒泡排序，平均性能优于冒泡排序。

在冒泡排序的第二层for循环中，有一个比较，且每次比较都有可能需要交换一下，因为交换的代码是在比较（第二层for循环中）中的。对于选择排序的第二层for循环中，也有一个比较，但是不会立即进行交换，而是找出了最大（或最小）的元素后再进行交换，交换的代码在不在第二层for循环中。

复杂度

最好、最坏、平均时间复杂度都是： O(n2)

空间复杂度： O(1)

选择排序属于不稳定排序。

我们发现，选择排序中的重点就是一步步选出序列中的最大值，既然需要选出最大值，我们能想到一个数据结构： 堆！或者说最大堆。那我们似乎可以对选择排序进行优化？😕

3. 代码重构

3.1 定义父类

我们发现，在冒泡排序和插入排序中都使用到了比较操作和交换顺序操作，而且它们都是可以共用的，那么我们可以将它们提取出来，放在一个父类里，然后在编写排序算法的时候实现这个父类就可以了。

但还有个问题，不同排序算法的实现是存在区别的，那么我们应该在父类中怎么做呢？😟

我们可以将这个类设置成抽象类，在抽象类中放置一个抽象方法，这样在编写不同的排序算法时需要实现这个抽象方法，以达到不同的排序算法有不同的实现逻辑。

因此，这个父类的初步实现为：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
package com.yang.sort;
/**
 * @author 默烦
 * @date 2020/8/11
 */
public abstract class Sort{
    protected Integer[] array;

    public void sort(Integer[] array) {
        if (array == null || array.length < 2) return;
        this.array = array;
        sort();
    }

    protected abstract void sort();
}

我们一开始就说了，要实现交换元素和比较元素的方法共用，因此我们可以在这个父类中增加这些方法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
 * 返回值等于0，代表array[i1] == array[i2]
 * 返回值小于0，代表array[i1] < array[i2]
 * 返回值大于0，代表array[i1] > array[i2]
 */
protected int cmp(int i1, int i2) {
    return array[i1] - array[i2];
}

protected int cmpElements(Integer v1, Integer v2) {
    return v1 - v2;
}

protected void swap(int i1, int i2) {
    int tmp = array[i1];
    array[i1] = array[i2];
    array[i2] = tmp;
}

其实写到这就差不多了，我们所提出的需求已经完全实现了，但为了在测试的时候可以直观的看到耗时、比较次数、交换次数等信息，我们还可以在这个父类中添加一些辅助测试的方法：

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
package com.yang.sort;
import java.text.DecimalFormat;

public abstract class Sort{
    // 省略其他代码
    ......
        
    private int cmpCount; // 比较次数
    private int swapCount; // 交换次数
    private long time; // 排序所用时间
    // 格式化 保留两位小数
    private final DecimalFormat fmt = new DecimalFormat("#.00");
    
    @Override
    public String toString() {
        String timeStr = "耗时：" + (time / 1000.0) + "s(" + time + "ms)";
        String compareCountStr = "比较：" + numberString(cmpCount);
        String swapCountStr = "交换：" + numberString(swapCount);
        return "【" + getClass().getSimpleName() + "】\n"
                + timeStr + " \t"
                + compareCountStr + "\t "
                + swapCountStr + "\n"
                + "------------------------------------------------------------------";
    }

    private String numberString(int number) {
        if (number < 10000) return "" + number;
        if (number < 100000000) return fmt.format(number / 10000.0) + "万";
        return fmt.format(number / 100000000.0) + "亿";
    }
}

同时我们还需要修改前面一些已经编写好的方法，这样才能真正实现“直观的看到耗时、比较次数和交换次数”的需求：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public void sort(Integer[] array) {
    if (array == null || array.length < 2) return;
    this.array = array;
    long begin = System.currentTimeMillis();
    sort();
    time = System.currentTimeMillis() - begin;
}

protected int cmp(int i1, int i2) {
    cmpCount++;
    return array[i1] - array[i2];
}

protected int cmpElements(Integer v1, Integer v2) {
    cmpCount++;
    return v1 - v2;
}

protected void swap(int i1, int i2) {
    swapCount++;
    int tmp = array[i1];
    array[i1] = array[i2];
    array[i2] = tmp;
}

我们还可以进行最后一步优化，如果一次比较多个排序算法的效率，为了方便我们在控制台上清晰地观看效率，我们可以让打印出来的结果按照耗时多少进行排序。这样的话我们需要让Sort抽象父类实现Comparable接口，定义一套比较方式：

1
2
3
4
5
6
7
8
9
10
11
12
13
public abstract class Sort implements Comparable<Sort> {
    // 省略其他代码
    ......
    
    @Override
    public int compareTo(Sort o) {
        int result = (int) (time - o.time);
        if (result != 0) return result;
        result = cmpCount - o.cmpCount;
        if (result != 0) return result;
        return swapCount - o.swapCount;
    }
}

这样我们在测试的时候就可以调用JDK提供的Arrays.sort();方法对结果进行排序了。

以后编写排序算法时，就可以继承这个父类，以达到代码的整洁。

3.2 算法重构

编写好父类后，我们可以对前面编写的代码进行重构！

未优化的冒泡排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
package com.yang.sort;

/**
 * @author 默烦
 * @date 2020/8/11
 */
public class BubbleSort1 extends Sort {
    @Override
    protected void sort() {
        for (int end = array.length - 1; end > 0; end--) {
            for (int begin = 1; begin <= end; begin++) {
                // if (array[begin] < array[begin - 1]) {
                if (cmp(begin, begin - 1) < 0) {
                    swap(begin, begin - 1);
                }
            }
        }
    }
}

冒泡排序优化一

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
package com.yang.sort;

/**
 * @author 默烦
 * @date 2020/8/11
 */
public class BubbleSort2 extends Sort {
    @Override
    protected void sort() {
        for (int end = array.length - 1; end > 0; end--) {
            boolean sorted = true;
            for (int begin = 1; begin <= end; begin++) {
                // if (array[begin] < array[begin - 1]) {
                if (cmp(begin, begin - 1) < 0) {
                    swap(begin, begin - 1);
                    sorted = false;
                }
            }
            if (sorted) break;
        }
    }
}

冒泡排序优化二

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
package com.yang.sort;

/**
 * @author 默烦
 * @date 2020/8/11
 */
public class BubbleSort3 extends Sort {
    @Override
    protected void sort() {
        for (int end = array.length - 1; end > 0; end--) {
            // sortedIndex的初始值在数组完全有序的时候有用
            int sortedIndex = 1;
            for (int begin = 1; begin <= end; begin++) {
                // if (array[begin] < array[begin - 1]) {
                if (cmp(begin, begin - 1) < 0) {
                    swap(begin, begin - 1);
                    sortedIndex = begin;
                }
            }
            end = sortedIndex;
        }
    }
}

选择排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
package com.yang.sort;

/**
 * @author 默烦
 * @date 2020/8/11
 */
public class SelectionSort extends Sort {

    @Override
    protected void sort() {
        for (int end = array.length - 1; end > 0; end--) {
            int maxIndex = 0;
            for (int begin = 1; begin <= end; begin++) {
//                if (array[maxIndex] < array[begin]) {
                if (cmp(maxIndex,begin) < 0){
                    maxIndex = begin;
                }
            }
            swap(maxIndex, end);
        }
    }
}

4. 堆排序

堆排序（Heap Sort），堆排序可以认为是对选择排序的一种优化。

堆排序的升序排序流程：

1、对序列进行原地建堆（Heapify）

2、重复执行以下操作，直到堆的元素数量为 1 ：

  • 交换堆顶元素与尾元素
  • 堆的元素数量减一
  • 对 0 位置进行一次下滤操作

堆排序操作图示如下：

堆排序图示一

然后重复循环执行，直到堆的数量为1：

堆排序图示二 堆排序图示三

从上述步骤进行分析，如果要编写堆排序需要有以下方法：

  • 原地建堆 / 批量建堆的方法heapify()
  • 下滤方法siftDown()

因为堆元素数量会减少，因此我们还需要一个表示堆长度的成员变量heapSize。

关于方法heapify()和siftDown()我们可以使用我们以前在 数据结构之二叉堆 一文中的代码，最后初步实现的代码如下：

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
package com.yang.sort;

/**
 * @author 默烦
 * @date 2020/8/11
 */
public class HeapSort extends Sort {
    private int heapSize;

    @Override
    protected void sort() {
        // 原地建堆 批量建堆
        heapSize = array.length;
        for (int i = (heapSize >> 1) - 1; i >= 0; i--) {
            siftDown(i);
        }
        while (heapSize > 1) {
            // 交换堆顶和尾部元素
            swap(0, --heapSize);
            // 对0位置元素进行下滤（恢复堆的性质）
            siftDown(0);
        }
    }

    /**
     * 让索引为 index 的元素进行下滤
     *
     * @param index
     */
    private void siftDown(int index) {
        Integer element = array[index];
        int half = heapSize >> 1;
        // 第一个叶子节点的索引 = 非叶子节点的数量
        while (index < half) { // 必须保证index位置是非叶子节点
            /**
             * index 位置的节点的子节点有两种情况
             * 1. 只有左子节点
             * 2. 同时有左子节点、右子节点
             */
            // 默认为左子节点的索引
            int childIndex = (index << 1) + 1;
            Integer child = array[childIndex];

            // 右子节点索引
            int rightIndex = childIndex + 1;
            // 选出最大的子节点
            if (rightIndex < heapSize && cmpElements(array[rightIndex], child) > 0) {
				// childIndex = rightIndex;
                child = array[childIndex = rightIndex];
            }

            if (cmpElements(element, child) >= 0) break;
            // 将子节点存放到index位置
            array[index] = child;
            // 重新设置index
            index = childIndex;
        }
        array[index] = element;
    }
}

性能对比

我们将前文中都涉及到的代码进行一个测试，比较一下它们之间的效率。

测试数据选取 1w 个随机随机数，范围是[1, 20000]。

测试代码如下：

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
public class Main {
    public static void main(String[] args) {
        // 产生1w个随机数 范围[1, 20000]
        Integer[] array = Integers.random(10000, 1, 20000);
        testSorts(array,
                  new BubbleSort1(),
                  new BubbleSort2(),
                  new SelectionSort(),
                  new HeapSort(),
                  new BubbleSort3());
    }

    static void testSorts(Integer[] array, Sort... sorts) {
        for (Sort sort : sorts) {
            // 将原数据拷贝一份
            Integer[] newArray = Integers.copy(array);
            sort.sort(newArray);
            // 验证排序是否正确 结果是否升序
            Asserts.test(Integers.isAscOrder(newArray));
        }
        // 结果排序
        Arrays.sort(sorts);
        // 打印结果
        for (Sort sort : sorts) {
            System.out.println(sort);
        }
    }
}

Integers类提供的工具方法：

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
package com.yang.tools;
import java.util.Arrays;
public class Integers {
    public static Integer[] random(int count, int min, int max) {
		if (count <= 0 || min > max) return null;
		Integer[] array = new Integer[count];
		int delta = max - min + 1;
		for (int i = 0; i < count; i++) {
			array[i] = min + (int)(Math.random() * delta);
		}
		return array;
	}
    
    public static Integer[] copy(Integer[] array) {
		return Arrays.copyOf(array, array.length);
	}
    
    public static boolean isAscOrder(Integer[] array) {
		if (array == null || array.length == 0) return false;
		for (int i = 1; i < array.length; i++) {
			if (array[i - 1] > array[i]) return false;
		}
		return true;
	}
}

Asserts断言工具类的代码如下：

1
2
3
4
5
6
7
8
9
public class Asserts {
   public static void test(boolean value) {
      try {
         if (!value) throw new Exception("测试未通过");
      } catch (Exception e) {
         e.printStackTrace();
      }
   }
}

打印的测试结果如下：

冒泡、插入和堆之间的对比

控制台没有报错，也成功打印出耗时结果，证明我们的排序算法是正确的。🎉

我们发现，堆排序的比较次数是远小于冒泡排序和插入排序的，这正是数据结构堆带来的好处。

我们还发现，堆排序和选择排序的交换次数也是小于冒泡排序的。

根据这个结果，我们可以看出堆排序、选择排序和冒泡排序之间的效率高低是：

堆排序 > 选择排序 > 冒泡排序

PS：由于测试数据是随机数，因此可能会出现优化未用到的情况，因此对于最后三种冒泡排序的耗时不同测试可能会出现不同的耗时顺序。

复杂度

1、Heapify的时间复杂度为 O(n)

2、交换堆顶元素与尾元素的时间复杂度为 O(1)

3、堆的元素数量减一的时间复杂度为 O(1)

4、下滤操作的时间复杂度为O(logn)

因为2、3、4需要进行循环执行，因此循环执行的时间复杂度为O(nlogn)，总的时间复杂度还得加上最开始Heapify的时间复杂度，因此总时间复杂度为O(logn + n) 。

最后得到的堆排序时间复杂度为O(nlogn)。

稳定性

堆排序属于不稳定排序。为什么呢？

假设现有这样一个序列{28a, 28b, 5, 17, 9}，前两个数是都是指数字 28 ，加个字母只是为了便于区分。

我们使用堆排序对这个序列进行排序，最开始时 28a 会在堆顶，然后执行堆排序的步骤后， 28a 会跑到序列尾，此时堆顶变成了 28b，如果再进行堆排序， 28b 会到 28a 前面，很显然两者的位置相比于最开始发生了变化。

因此，堆排序属于不稳定排序。

我们现在编写的三种排序方法暂时只能对整型进行排序，为了让所有类型都能使用，我们应当设置范型，但在本文中我们就不实现了，将在后续的文章中进行实现。