4、排序算法（一）

【数据结构与算法基础】代码仓库：https://github.com/jinrunheng/datastructure-and-algorithm

一：排序算法概述

本章节，我们将正式进入到排序算法的学习。

在计算机科学与数学中，一个排序算法（sorting algorithm）是一种能将一串数据依照特定排序方式进行排列的一种算法。最常用到的排序方式是数值顺序以及字典顺序。

排序算法的输出必须遵循以下两个原则：

1. 输出结果为递增序列（递增是针对所需的排序顺序而言）
2. 输出结果是原输入的一种排列，或是重组

排序算法的稳定性

排序算法可以按照排序的稳定性分为稳定排序算法和非稳定排序算法。稳定排序算法会让原本有相等键值的记录维持相对次序，也就是说，如果一个排序算法是稳定的，当有两个相等键值的记录 R 和 S，且在原本的列表中，R 在 S 之前，那么排序过后的列表中，R 也将会在 S 之前。不稳定排序算法可能会在相等的键值中改变记录的相对次序。

在后面的文章中，我们将重点介绍冒泡排序，选择排序，插入排序，归并排序，快速排序，堆排序，计数排序，桶排序，基数排序，希尔排序这几种算法，并分析它们的时间复杂度，空间复杂度以及排序稳定性。

为了让大家更直观地感受排序算法的原理，所以，我的示例代码摒弃了泛型，而在链接提供的代码中会使用泛型，望大家理解。示例中，排序算法的输入为一个 int 型数组，且所有的代码的排序规则为，从小到大顺序排序。

二：选择排序

代码链接🔗

选择排序（Selection sort）是最简单的排序算法之一，它的原理是每一次将待排序的数组中，最小的元素取出放置到相应的位置上。方法就是使用一个索引来标记最小元素的位置，然后遍历整个待排序的部分后，让最小元素与待排好序的位置的元素进行交换，整个过程模拟如下：

• 第一次将 [0…n-1] 最小的元素放置到 arr[0] 上，arr[0] 这个位置就是排好序的了；
• 第二次将 [1…n-1] 最小的元素放置到 arr[1] 上，arr[1] 这个位置就是排好序的了；
• 第三次将 [2…n-1] 最小的元素放置到 arr[2] 上，arr[2] 这个位置就是排好序的了;
• … …
• 最后将 [n-2…n-1] 最小的元素放置到 arr[n-2] 上，数组全部都排好序。

选择排序的代码如下：

public class SelectionSort {
    public static void sort(int[] arr) {
        if (arr == null || arr.length < 2)
            return;
        int minIndex;
        for (int i = 0; i < arr.length; i++) {
            minIndex = i;
            for (int j = i + 1; j < arr.length; j++)
                minIndex = arr[minIndex] > arr[j] ? j : minIndex;
            SwapUtils.swap(arr, minIndex, i);
        }
    }
}

选择排序的复杂度与稳定性分析：

选择排序算法中有两层循环嵌套，所以，我们可以直接看出，选择排序的时间复杂度为 O(n2)，空间复杂度为 O(1)。

选择排序并不是一种稳定排序算法，举个最简单的例子，将 (A,80)，(B,80)，(C,70) 这三个卷子按照分数从小到大排序，选择排序的第一步就会将 C 和 A 做交换，排序的结果为 C，B，A；但是稳定排序的结果应该是 C，A，B。所以，选择排序不是一个稳定排序算法。

三：冒泡排序

代码链接🔗

在讲解什么是冒泡排序之前，同大家分享一个在 StackOverflow 上有趣的提问 Why bubble sort is called bubble sort?

回答在这里：

The bubble sort gets its name because elements tend to move up into the correct order like bubbles rising to the surface.

冒泡排序（Bubble sort），顾名思义，其模拟过程如下：

• 数组范围 [0…n-1]， 从索引 0 开始，逐个向后比较，如果 arr[i] > arr[i + 1] 则交换这两个元素的位置，依次遍历，直至遍历结束，arr[n-1] 位置的元素被排出

• 数组范围 [0…n-2]， 从索引 0 开始，逐个向后比较，如果 arr[i] > arr[i + 1] 则交换这两个元素的位置，依次遍历，直至遍历结束，arr[n-2] 位置的元素被排出

• … …

• 数组范围[0…1]，比较 arr[0] 与 arr[1] 的大小，如果 arr[0] > arr[1] 则交换这两个元素的位置，整个数组排序完成。

冒泡排序的代码如下：

public class BubbleSort {
    public static void sort(int[] arr) {
        if(arr == null || arr.length < 2)
            return;
        for(int i = 0; i < arr.length - 1; i++)
            for(int j = 0; j < arr.length - 1 - i; j++)
                if(arr[j] > arr[j + 1])
                    SwapUtils.swap(arr, j, j + 1);
    }
}

冒泡排序的复杂度与稳定性分析：

冒泡排序的时间复杂度为 O(n2)，空间复杂度为 O(1)。

并且，冒泡是一种稳定排序算法，将大的元素逐个向后调整。比较过程中，如果相邻的两个元素相等，那么就不需要交换，这也就保证了相同元素的次序一致，所以冒泡排序是一种稳定排序算法。

四：插入排序

代码链接🔗

插入排序（Insertion sort）也叫做扑克牌排序（Poker sort），因为插入排序和我们玩扑克牌时抓牌码牌的过程非常类似。

其模拟过程如下图所示：

插入排序的代码如下：

public class InsertionSort {
    public static void sort(int[] arr) {
        if (arr == null || arr.length < 2)
            return;
        for (int i = 1; i < arr.length; i++)
            for (int j = i; j > 0 && arr[j] < arr[j - 1]; j--)
                SwapUtils.swap(arr, j, j - 1);
    }
}

插入排序的复杂度与稳定性分析：

和选择排序与冒泡排序不同，选择排序与冒泡排序的时间复杂度为 O(n2)，他们与数据的状况是无关的，也就是说，如果我给定的数组是已经排好序的数组，冒泡排序与选择排序还是会依次执行内部的算法流程，仍然会进入到两层循环嵌套中，逐个进行比对，他们的时间复杂度仍然为 O(n2)。

但是插入排序则不同，如果我给定一个已序数组作为待排序的数组，那么，插入排序算法每“插入”一个元素，都只执行“往后看”这个操作，并不会执行“向前找”这个操作，所以，此时的插入排序算法是一个 O(n) 级别的算法，请大家细心体会。

所以，插入排序有最好时间复杂度，插入排序的最好时间复杂度为 O(n)，平均时间复杂度为 O(n2)；插入排序的空间复杂度为 O(1)。

插入排序是一个稳定的排序算法，还是举这个例子：将 (A,80)，(B,80)，(C,70) 这三个卷子按照分数从小到大排序，插入排序的结果为 C，A，B。这个过程大家可以自己模拟一遍，我们可以轻易地得出，插入排序是一种稳定排序算法。