几种常用排序算法的Java实现
小橘子🍊
  2019-05-04 11:01:49 2019-05-04 11:01      

本文中用到的图片来自 如果天空不死

前言

对数据排序是一种很基本的需求，各种编程语言都提供了相应的实现，就 Java 语言本身来说，当然也有着相应的类库可以调用，比如说 java.util.Arrays#sort(int[]) ，网上关于排序算法的讲解也很多，我这里也不想多说，仅仅是对各种算法的思想用最简短的方式进行阐述，并提供相应的实现代码。

正文

各种排序算法的时间复杂度、空间复杂度、以及稳定性是面试时经常问到的点，这里也列出一张表方便查询。

排序方法 平均情况 最好情况 最坏情况 辅助空间 稳定性
冒泡排序 $O(n^2)$ $O(n)$ $O(n^2)$ $O(1)$ 稳定
选择排序 $O(n^2)$ $O(n^2)$ $O(n^2)$ $O(1)$ 不稳定
插入排序 $O(n^2)$ $O(n)$ $O(n^2)$ $O(1)$ 稳定
堆排序 $O(nlogn)$ $O(nlogn)$ $O(nlogn)$ $O(1)$ 不稳定
归并排序 $O(nlogn)$ $O(nlogn)$ $O(nlogn)$ $O(n)$ 稳定
快速排序 $O(nlogn)$ $O(nlogn)$ $O(n^2)$ $O(logn)$ ~ $O(n)$ 不稳定

下边对表中的六种排序算法的基本原理进行说明，并附上源代码，注意如果不做特殊说明，所有的例子都是将数据按照从小到大进行排序。

冒泡排序

冒泡排序是非常简单的排序算法，他的基本思想是依次交换相邻的数据，使得未排序的元素中的最大值排到最后，经过 n - 1 轮排序后，数列将呈现有序态，当然考虑性能，如果在某一轮交换中，没有出现两个元素交换的情况，这时就说明数据已经是排好序的，即可提前退出循环得到排序的结果。下图是冒泡排序的过程：

05-05-01

可以看到第一趟排序后，最大的元素已经在数列最后了，第二趟对剩下的元素进行同样的交换操作，完成后，第二大的元素排在倒数第二位。依次类推，进行 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
public class BubbleSort {
    /*
     * 冒泡排序
     */
    public static void bubbleSort1(int[] a) {
        int len = a.length;
        for (int i = 0; i < len - 1; i++) {
            for (int j = 0; j < len - 1 - i; j++) {
                // 若不满足递增顺序，交换相邻数据
                if (a[j] > a[j + 1]) {
                    int t = a[j + 1];
                    a[j + 1] = a[j];
                    a[j] = t;
                }
            }
        }
    }

    /*
     * 冒泡排序(改进版)
     */
    private static void bubbleSort2(int[] a) {
        int len = a.length; // 标记
        boolean flag = false;
        for (int i = 0; i < len - 1; i++) {
            for (int j = 0; j < len - 1 - i; j++) {
                // 若不满足递增顺序，交换相邻数据
                if (a[j] > a[j + 1]) {
                    int t = a[j + 1];
                    a[j + 1] = a[j];
                    a[j] = t;
                    flag = true;
                }
            }
            if (!flag) break;
            flag = false;
        }
    }

    public static void main(String[] args) {
        int i;
        int[] a = {20, 40, 30, 10, 60, 50};

        System.out.print("before sort:");
        for (i = 0; i < a.length; i++)
            System.out.printf("%d ", a[i]);
        System.out.print("\n");

        bubbleSort2(a);

        System.out.print("after  sort:");
        for (i = 0; i < a.length; i++)
            System.out.printf("%d ", a[i]);
        System.out.print("\n");
    }
}

选择排序

选择排序的思想其实跟冒泡排序有点相似，只是冒泡排序中数据的交换相对频繁，而选择排序只是在确定交换位置后才会进行交换，先看看基本的实现过程：

05-05-02

可以看到整个排序的过程也会进行 n - 1 趟，假设当前是第 i 趟，那么选择排序就是从 i 及之后的所有元素中找到最小的那个元素的位置记为 j，然后将位置 i 和 j 的元素进行交换。这样本趟排序就结束了，接下来进行下一趟的排序操作，执行 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
public class SelectSort {
    /*
     * 选择排序
     */
    private static void selectSort(int[] a) {
        int len = a.length;
        int min = Integer.MAX_VALUE;
        int pos = 0;
        for (int i = 0; i <len - 1; i++) {
            for (int j = i; j < len; j++) {
                if (a[j] < min) {
                    min = a[j];
                    pos = j;
                }
            }
            int t = a[pos];
            a[pos] = a[i];
            a[i] = t;
            min = Integer.MAX_VALUE;
            pos = i;
        }
    }

    public static void main(String[] args) {
        int i;
        int[] a = { 20, 40, 30, 10, 60, 50 };

        System.out.print("before sort:");
        for (i = 0; i < a.length; i++)
            System.out.printf("%d ", a[i]);
        System.out.print("\n");

        selectSort(a);

        System.out.print("after  sort:");
        for (i = 0; i < a.length; i++)
            System.out.printf("%d ", a[i]);
        System.out.print("\n");
    }
}

插入排序

插入排序跟选择排序非常相似，他们的区别是：

  • 选择排序 从当前及后续所有的元素中选中最小的那个元素和当前位置的元素进行交换。
  • 插入排序 将当前位置的元素插入到当前位置之前的所有元素中的一个合适位置。

05-05-03

可以看到整个数据分为两个区，当前元素之前的为有序区，后边的为无序区，插入排序就是将当前元素插入到有序区中，如果元素比较多，那么对有序区进行二分查找来确定插入位置，将会极大的提高排序效率。

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
public class InsertSort {
    /*
     * 直接插入排序
     */
    private static void insertSort(int[] a) {
        int len = a.length;
        for (int i = 1; i < len; i++) {
            for (int j = i; j > 0; j--) {
                // 将 a[j] 放到前面的一个合适的位置
                if (a[j] < a[j - 1]) {
                    int t = a[j];
                    a[j] = a[j - 1];
                    a[j - 1] = t;
                } else break;
            }
        }
    }

    public static void main(String[] args) {
        int i;
        int[] a = {20, 40, 30, 10, 60, 50};

        System.out.print("before sort:");
        for (i = 0; i < a.length; i++)
            System.out.printf("%d ", a[i]);
        System.out.print("\n");

        insertSort(a);

        System.out.print("after  sort:");
        for (i = 0; i < a.length; i++)
            System.out.printf("%d ", a[i]);
        System.out.print("\n");
    }
}

堆排序

堆排序是一种比较复杂的排序方式，它利用了一种叫做二叉堆的数据结构（还有其它类型的堆结构，如果想要深入了解，请参看这篇博文），所以在介绍堆排序之前我们需要先简单了解下二叉堆这种数据结构。

二叉堆基本概念及性质

二叉堆是完全二元树或者是近似完全二元树，按照数据的排列方式可以分为两种：最大堆和最小堆。

  • 最大堆：父结点的键值总是大于或等于任何一个子节点的键值；
  • 最小堆：父结点的键值总是小于或等于任何一个子节点的键值。

二叉堆一般都通过”数组”来实现，因为二叉堆是个树结构，所以二叉堆有个根节点，根据根节点位于数组的0索引位置还是1索引位置,当前节点的左子节点、右子节点、父节点分为如下两种情况。

根节点位置 左子节点 右子节点 父节点
根节点位于索引0 $2 * i + 1$ $2 * i + 2$ $floor((i - 1) / 2)$
根节点位于索引1 $2 * i$ $2 * i + 1$ $floor(i\ /\ 2)$

根据上面所述，我们就可以得到一个基本的二叉堆结构。因为最小堆和最大堆（最大堆和最小堆只是二叉堆的两种形式，其中最大堆是父节点大于子节点的二叉堆，反之就是最小堆），仅仅只是父子元素大小的区别，这里拿最大堆进行说明。

05-05-04

根节点位于索引0的最大堆

05-05-05

根节点位于索引1的最大堆

结合图片中的注释，可以很容易理解最大堆的特性。下面说明一下如何构建一个最大堆。

最大堆添加元素

最大堆的添加操作很容易理解，因为最大堆有着它自己的结构特点，所以在添加元素后需要根据结构特点进行调整，以此来维持最大堆的结构。

05-05-06

最大堆添加元素

根据图解，可以看到最大堆添加元素后的调整操作就是将元素尽可能的往上移，因为最大堆的父节点总是大于子节点的。

最大堆删除元素

最大堆的删除操作思想跟插入一样，但是在调整的过程中考虑的情况有两种，这点和添加元素后的调整操作不一样。原因是添加元素后进行上调是直接和邻近父节点进行对比，邻近父节点只有一个，所以对比一次就行，而删除元素后，数组中就会形成一个空缺，所以用数组的最后一个元素进行填补，这样，填补的元素所处节点的子节点可能会比填补元素大，这样就需要分别和两个子节点元素进行大小对比，以下是删除元素后调整的详细过程。

05-05-07

最大堆删除元素

当从最大堆中删除数据时：先删除该数据，然后用最大堆中最后一个的元素插入这个空位；接着，把这个“空位”尽量往上挪，直到剩余的数据变成一个最大堆。

利用最大堆进行排序

说完了最大堆的性质和添加删除元素操作，接下来就是利用最大堆进行堆排序，核心就是两点：

  1. 将所有的元素构建成最大堆。
  2. 将根节点的元素和数组最后的一个元素进行交换，然后对最后一个元素之前的所有元素进行最大堆的重构（类似于删除元素后的调整过程，只是边界条件在变化）。

05-05-08

利用最大堆排序数据的过程

因为这个排序过程的右边界一直在变，所以调整的条件较为苛刻，具体的细节请看下边代码中的注释。

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
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
public class HeapSort {
    private static int[] heapSort(int[] a) {
        int[] maxHeap = arrToMaxHeap(a);
        return sortHeap(maxHeap);
    }

    /**
     * 根据最大堆，对数据进行排序
     *
     * @param maxHeap 最大堆
     * @return 排序结果
     */
    private static int[] sortHeap(int[] maxHeap) {
        int len = maxHeap.length;
        for (int i = 0; i < len - 1; i++) {
            int tail = len - 1 - i;
            // 将未排序序列的首尾元素进行对调
            int t = maxHeap[0];
            maxHeap[0] = maxHeap[tail];
            maxHeap[tail] = t;
            // 重构最大堆
            int p = 0;
            int s;
            // 调整首节点，因为上述对调操作后，0 - tail 区间中的数据已经不满足最大堆性质了，需要进行调换来重构最大堆
            // 首先需要判断当前节点是否有孩子节点，上界为 ceil，ceil 及以后的序列是已经排好序的。
            // 如果当前节点的两个孩子节点其中之一大于当前节点，则进行其中较大的那个节点进行交换，然后将当前节点设置为目标叶子节点。
            // 重复上述过程
            while ((s = 2 * p + 1) < tail && (maxHeap[p] < maxHeap[s] || maxHeap[p] < maxHeap[s + 1])) {
                // 如果右节点大于左节点，并且右节点没有超过上界 tail 则当前节点和右节点交换
                if (maxHeap[s] < maxHeap[s + 1] && s + 1 < tail) {
                    t = maxHeap[p];
                    maxHeap[p] = maxHeap[s + 1];
                    maxHeap[s + 1] = t;
                    p = s + 1;
                    continue;
                }
                // 到这里说明不能跟右孩子交换，则判断是否左孩子满足交换条件
                else if (maxHeap[p] < maxHeap[s]) {
                    t = maxHeap[p];
                    maxHeap[p] = maxHeap[s];
                    maxHeap[s] = t;
                    p = s;
                    continue;
                }
                break;
            }
        }
        return maxHeap;
    }

    /**
     * 将数组转换为最大堆
     *
     * @param a 原数组
     * @return 得到的最大堆
     */
    private static int[] arrToMaxHeap(int[] a) {
        int len = a.length;
        int[] maxHeap = new int[len];
        for (int i = 0; i < len; i++) {
            maxHeap[i] = a[i];
            int s = i;
            int p;
            // 对加入的数据按规则进行调整
            while ((p = (int) Math.floor((s - 1) * 1.0 / 2)) >= 0 && maxHeap[s] > maxHeap[p]) {
                int t = maxHeap[s];
                maxHeap[s] = maxHeap[p];
                maxHeap[p] = t;
                s = p;
            }

        }
        return maxHeap;
    }

    public static void main(String[] args) {
        int i;
        int[] a = {30, 40, 60, 10, 20, 50, 70, 25, 33, 12, 90, 100, 87, 59, 39, 101};

        System.out.print("before sort:");
        for (i = 0; i < a.length; i++)
            System.out.printf("%d ", a[i]);
        System.out.print("\n");

        a = heapSort(a);

        System.out.print("after  sort:");
        for (i = 0; i < a.length; i++)
            System.out.printf("%d ", a[i]);
        System.out.print("\n");
    }
}

归并排序

归并排序的核心是将两个有序数列合并为一个有序数列，其基本思路是将所有的元素看成独立的部分，然后两两合并得到一个较大元素，然后再将较大的元素两两合并得到一个更大的部分，依次类推，直到最后只有一个元素，这就是最终排序好的结果，理解这个该过程后，就可以很容易想到利用用递归的思想进行编程。

05-05-09

归并排序基本过程

这里的元素是偶数个，如果元素是基数个，过程也基本类似，只需要记得，递归的终止条件就是两个：

  1. 待合并的元素个数为 1，那么就直接返回这个元素。
  2. 待合并的元素个数为 2，那么就将这两个元素排序后直接返回。

关于这两点，请看代码实现。

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
public class MergeSort {
    /**
     * 递归调用归并排序函数
     * @param a 原数组
     * @param l 左边界
     * @param r 右边界
     * @return l 到 r 区间归并排序的结果，返回的是一个新数组
     */
    private static int[] mergeSort(int[] a, int l, int r) {
        int len = r - l + 1;
        // 终止条件
        if (len == 1) return new int[]{a[l]};
        if (len == 2) return a[l] > a[r] ? new int[]{a[r], a[l]} : new int[]{a[l], a[r]};
        // 否则递归调用归并函数
        int[] pre = mergeSort(a, l, l + len / 2 - 1);
        int[] post = mergeSort(a, l + len / 2, r);
        // 合并排序的结果
        return merge(pre, post);
    }

    // 两个排序数组的合并
    private static int[] merge(int[] pre, int[] post) {
        int prl = pre.length, pol = post.length;
        int poi = 0, pri = 0;
        int[] res = new int[prl + pol];
        for (int i = 0; i < prl + pol; i++) {
//            此处限制条件比较多
//            1. 保证 pre 数组的下标 pri 不会越界
//            2. post 数组的值已经全部进入 res 数组
//            3. pre 数组当前值小于 post 数组的当前值
            if (pri != prl && (poi == pol || pre[pri] < post[poi])) res[i] = pre[pri++];
            else res[i] = post[poi++];
        }
        return res;
    }

    public static void main(String[] args) {
        int i;
        int[] a = {30, 40, 60, 10, 20, 50, 70, 25, 33, 12, 90, 100, 87, 59, 39, 101};

        System.out.print("before sort:");
        for (i = 0; i < a.length; i++)
            System.out.printf("%d ", a[i]);
        System.out.print("\n");

//        mergeSortUp2Down(a, 0, a.length - 1);        // 归并排序(从上往下)
        a = mergeSort(a, 0, a.length - 1);                    // 归并排序(从下往上)

        System.out.print("after  sort:");
        for (i = 0; i < a.length; i++)
            System.out.printf("%d ", a[i]);
        System.out.print("\n");
    }
}

快速排序

快速排序采用的是分治的策略，大致就是先让数据做到宏观有序，然后缩小范围，在小的范围内再让数据做到宏观有序，这样逐级逼近，直到最后全部有序。基本的流程如下：

  1. 从区间范围内的数据中任意取一个数作为参考点。
  2. 将区间内的剩余数据和参考点进行比对，大于参考点的数据往前挪，小于参考点的数据往后移，然后用参考点将前挪和后移的这两部分数据用参考点隔开。
  3. 递归的对前挪和后移的这两部分数据进行上述操作

详细的过程参考下图：

05-05-10

快速排序的基本过程

这里的过程很清晰了，唯一要注意的就是队规的结束条件是区间长度小于 2，详细的请看下边代码实现。

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
public class FastSort {
    /*
     * 快速排序
     */
    private static void quickSort(int[] a, int l, int r) {
        int ll = l;
        int rr = r;
        // 参考点
        int mid = a[l];
        // 将整个数组分成大于和小于 mid 的两个部分，其中 mid 可以任取 l 到 r 区间中的一个值
        while (l < r) {
            while (a[r] >= mid && r > l) r--;
            if (r > l) a[l] = a[r];
            while (a[l] <= mid && r > l) l++;
            if (r > l) a[r] = a[l];
        }
        a[l] = mid;
        // 终止条件判断
        if (ll < l - 1) quickSort(a,ll,l - 1);
        if (l + 1 < rr) quickSort(a,l + 1,rr);
    }

    public static void main(String[] args) {
        int i;
        int[] a = {30, 40, 60, 10, 20, 50, 70, 25, 33, 12, 90, 100, 87, 59, 39, 101};

        System.out.print("before sort:");
        for (i = 0; i < a.length; i++)
            System.out.printf("%d ", a[i]);
        System.out.print("\n");

        quickSort(a, 0, a.length - 1);

        System.out.print("after  sort:");
        for (i = 0; i < a.length; i++)
            System.out.printf("%d ", a[i]);
        System.out.print("\n");
    }
}

结语

本文介绍了六种常用的排序算法的思想，并给出了相应的代码实现，因为写这个文章的主要目的是方便自己以后进行回顾，所以内容省略了很多细节的部分，这是建立在我已经了解过那些细节的基础之上，如果你是一名初学者，可能在看这篇文章时会有些模糊不清，那么建议你还是看看本文开头引用中所提到的那位大神的博客，这里也十分感谢大佬的配图。