20张图带你搞懂十大经典排序算法

发表于 3年以前 | 总阅读数：317 次

十大排序算法思路汇总

在面试的过程中经常会遇到手写排序算法，所以本文就简单总结一下。不对算法的细节做介绍，只做一个概括性的描述。

交换类：通过元素之间的两两交换来实现排序

插入类：将数分为2部分，依次将无序的数插入到有序的数列中

选择类：从待排序数列中找到最小值或者最大值元素，放到已拍好序的序列后面

「计数排序和基数排序可以认为是桶排序的一种特殊实现，都不是通过元素之间的比较来实现排序的」

冒泡排序

冒泡排序，从头开始，依次比较数组中相邻的2个元素，如果后面的数比前面的数大，则交换2个数，否则不交换。每进行一轮比较，都会把数组中最大的元素放到最后面。

如下图，一轮比较的过程如下

当数组中有n个元素时，只需要进行n轮比较，则整个数组就是有序的

public static void bubbleSort(int[] a) {
 // 进行i轮比较
    for (int i = 0; i < a.length - 1; i++) {
        for (int j = 0; j < a.length - 1 - i; j++) {
            if (a[j] > a[j + 1]) {
                swap(a, j, j + 1);
            }
        }
    }
}

public static void swap(int[] a, int i, int j) {
    int temp = a[i];
    a[i] = a[j];
    a[j] = temp;
}

快速排序

快速排序的执行流程主要分为如下三步

从数列中取出一个数作为基准数
分区，将比它大的数全放到它的右边，小于或等于它的数全放到它的左边
再对左右区间重复第二步，直到各区间只有一个数

public static void quickSort(int[] a, int left, int right) {
    if (left >= right) {
        return;
    }
    int index = sort(a, left, right);
    quickSort(a, left, index - 1);
    quickSort(a, index + 1, right);
}

public static int sort(int[] a, int left, int right) {
    int key = a[left];
    while (left < right) {
        // 从high所指位置向前搜索找到第一个关键字小于key的记录和key互相交换
        while (left < right && a[right] >= key) {
            right--;
        }
        a[left] = a[right];
        // 从low所指位置向后搜索，找到第一个关键字大于key的记录和key互相交换
        while (left < right && a[left] <= key) {
            left++;
        }
        a[right] = a[left];
    }
    // 放key值，此时left和right相同
    a[left] = key;
    return left;
}

下图演示了一次分区的流程 「经典的Top K面试题一般就可以用快排和堆排序来解决」。我们在下一节手写堆排序来分析吧

插入排序

将数组分为2端，有序数组和无序数组，依次将无序数组中的值插入到无序数组中。

如下图3 6 7为有序数组，4 2为无序数组。依次将4，2插入到无序数组中即可

如图，插入4的过程如下

程序怎么划分有序数组和无序数组呢？可以认为第一个元素为有序数组，后面的值依次插入即可

public static void insertionSort(int[] a) {
    for (int i = 1; i < a.length; i++) {
        for (int j = i; j > 0; j--) {
            while (a[j] < a[j - 1]) {
                swap(a, j, j - 1);
            }
        }
    }
}

public static void swap(int[] a, int i, int j) {
    int temp = a[i];
    a[i] = a[j];
    a[j] = temp;
}

「可以看到有很多无用的交换位置的过程，我们可以先直接定位到要交换的元素，然后进行一次交换即可。改进后的插入排序代码」

public static void insertionSort(int[] a) {
    for (int i = 1; i < a.length; i++) {
        int temp = a[i];
        int j;
        // 查到合适的插入位置，插入即可
        for (j = i - 1; j >= 0 && a[j] > temp; j--) {
            a[j + 1] = a[j];
        }
        a[j + 1] = temp;
    }
}

希尔排序

「希尔排序是基于插入排序改进后的算法。因为当数据移动次数太多时会导致效率低下。所以我们可以先让数组整体有序（刚开始移动的幅度大一点，后面再小一点），这样移动的次数就会降低，进而提高效率」

图片原文地址：博客园《图解排序算法(二)之希尔排序》

public static void shellSort(int[] a) {
    for (int step = a.length / 2; step > 0; step /= 2) {
        for (int i = step; i < a.length; i++) {
            int temp = a[i];
            int j;
            for (j = i - step; j >= 0 && a[j] > temp ; j -= step) {
                a[j + step] = a[j];
            }
            a[j + step] = temp;
        }
    }
}

选择排序

第一次迭代，将最小的放在数组第0个位置第二次迭代，将次小的放在数组第1个位置

public static void selectionSort(int[] a) {
    for (int i = 0; i < a.length; i++) {
        int index = i;
        for (int j = i + 1; j < a.length; j++) {
            if (a[index] > a[j]) {
                index = j;
            }
        }
        if (index != i) {
            swap(a, index, i);
        }
    }
}

public static void swap(int[] a, int i, int j) {
    int temp = a[i];
    a[i] = a[j];
    a[j] = temp;
}

堆排序

我们来手写一下堆排序，首先我们解释一下什么是堆？

堆是一种数据结构，需要满足如下几个特性

堆是一颗完全二叉树（生成节点的顺序是从左往右，从上往下依次进行）
堆中某个节点值总是不大于或者不小于其父节点的值

「将根结点最大的堆叫做最大堆或大根堆，根结点最小的堆叫做最小堆或小根堆」

大根堆和小根堆如下图所示

假设有如下一个完全二叉树，如何将它调整为一个堆呢？

可以看到10及其子节点符合条件，3及其子节点符合条件，4这个节点不符合条件。

「所以要对4这个节点进行调整，调整的过程称为heapify」

从4这个节点的左右节点找一个大的节点（即10这个节点）和4这个节点进行交换
交换完有可能交换后的节点不符合条件，所以还需要进行调整（调整过程和1类似）
最终4节点和5节点进行交换。二叉树变为堆

在实际开发的过程中，我们并不会用树这种结构来表示堆，而是用数组。通过下标的特点，可以总结出如下规律

假如一个节点在数组中的节点下标为i，则

父节点下标为：parent = (i - 1) / 2 左节点下标为：c1 = 2 * i + 1 右节点下标为：c2 = 2 * i + 2

所以上图中的堆，用数组表示为[10, 5, 3, 4, 1, 2, 0]

知道了如何用数组表示堆，我们写一下对如下4这个节点heapify的过程

/**
 * @param a 数组
 * @param n 数组长度
 * @param i 要进行heapify的节点
 */
public static void heapify(int[] a, int n, int i) {
    // 递归出口
    if (i >= n) {
        return;
    }
    // 左节点下标
    int c1 = 2 * i + 1;
    // 右节点下标
    int c2 = 2 * i + 2;
    int max = i;
    if (c1 < n && a[c1] > a[max]) {
        max = c1;
    }
    if (c2 < n && a[c2] > a[max]) {
        max = c2;
    }
    // 将左节点，右节点中的最大值和父节点交换
    if (max != i) {
        swap(a, max ,i);
        heapify(a, n, max);
    }
}

@Test
public void heapify() {
    int[] array = new int[]{4, 10, 3, 5, 1, 2};
    // 调整后为 10， 5， 3， 4， 1， 2
    HeapSort.heapify(array, array.length,0);
}

「我们如何把一个完全二叉树变为堆呢？」

「只要对非叶子节点从左边往右，从下到上依次进行heapify即可。」 如下图只需要依次对10，3，4进行heapify即可

public static void buildTree(int[] a) {
    // 找到最后一个非叶子节点
    int lastNode = a.length - 1;
    int parent = (lastNode - 1) / 2;
    for (int i = parent; i >= 0; i--) {
        heapify(a, a.length, i);
    }
}

我们来测试一下

@Test
public void buildTree() {
    int[] array = new int[]{3, 5, 7, 2, 4, 9, 6};
    // 9 5 7 2 4 3 6
    HeapSort.buildTree(array);
}

知道了堆是如何生成以及如何调整的过程，我们再分析堆排序的过程就非常简单了！

以大顶堆为例，最大值一定是根节点。

将根节点和最后一个叶子节点交换，然后将这个叶子节点移出堆
此时根节点是不符合要求的，所以对根节点进行heapify后，又变成了一个堆了
重复1，2步，就能找出剩余节点中的最大值

因为每次找出的最大值，都是在数组的最后一位，所以我们不需要真正的进行移除堆这个操作，只是进行heapify的时候，数组长度逐渐递减即可。最终的数组就是升序的

public static void heapSort(int[] a) {
    // 先构建一个堆
    buildTree(a);
    // 每次将堆的根节点和最后一个节点进行交换，然后进行heapify
    for (int i = a.length - 1; i >= 0; i--) {
        swap(a, i, 0);
        heapify(a, i, 0);
    }
}

所以最终一个堆排序的代码如下


public class HeapSort {

    public static void heapSort(int[] a) {
        buildTree(a);
        for (int i = a.length - 1; i >= 0; i--) {
            swap(a, i, 0);
            heapify(a, i, 0);
        }
    }

    public static void buildTree(int[] a) {
        // 找到最后一个非叶子节点
        int lastNode = a.length - 1;
        int parent = (lastNode - 1) / 2;
        for (int i = parent; i >= 0; i--) {
            heapify(a, a.length, i);
        }
    }

    /**
     * @param a 数组
     * @param n 数组长度
     * @param i 要进行heapify的节点
     */
    public static void heapify(int[] a, int n, int i) {
        if (i >= n) {
            return;
        }
        int c1 = 2 * i + 1;
        int c2 = 2 * i + 2;
        int max = i;
        if (c1 < n && a[c1] > a[max]) {
            max = c1;
        }
        if (c2 < n && a[c2] > a[max]) {
            max = c2;
        }
        if (max != i) {
            swap(a, max ,i);
            heapify(a, n, max);
        }
    }

    public static void swap(int[] a, int i, int j) {
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
}

我们这里只演示了一下如何构建一个堆，以及堆排序的流程是怎样的？

「要实现一个完整的堆，我们还需要提供一个插入节点和删除根节点的方法」。我就不写实现了，用图演示一下流程，有兴趣的可以写一下，「大部分语言都会内置堆的实现，即优先级队列（Java中为PriorityQueue），所以当我们有用到堆的场景时，直接用PriorityQueue即可」

堆插入节点

当堆插入节点时，插入的位置是完全二叉树的最后一个位置。比如我们插入一个新节点，值是8

我们让8和它的父节点比较，8>5，则让新节点上浮，和父节点交换位置

交换完后继续和父节点比较，8<9，则不用调整了

堆删除节点

堆删除节点时，删除的是堆顶的节点。比如我们删除大顶堆的9节点

为了维持堆的结构，我们把堆的最后一个节点6补到堆顶的位置

接着我们让堆顶的节点和它的左右孩子节点进行比较，如果左右孩子中最大的一个比节点6大，那么则让节点6下沉

接着和左右节点进行比较，3<6，则不用调整了

前 K 个高频元素

题目地址：剑指 Offer 40. 最小的k个数

输入整数数组 arr ，找出其中最小的 k 个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。

输入：arr = [3,2,1], k = 2
输出：[1,2] 或者 [2,1]

限制：

0 <= k <= arr.length <= 10000 0 <= arr[i] <= 10000

「堆」

维护一个大顶堆当堆中的元素不够k时，一直往堆中放元素即可当堆中的元素大于等于k时，将堆顶的元素和新添加的元素进行比较。如果新添的元素比堆顶的元素小，则应该把堆顶的元素删除，将新填的元素放入堆，这样就能保证堆中的元素一直是最小的k个

public int[] getLeastNumbers(int[] arr, int k) {
    if (arr.length == 0 || k == 0) {
        return new int[0];
    }
    PriorityQueue<Integer> queue = new PriorityQueue<>((num1, num2) -> num2 - num1);
    for (int num : arr) {
        if (queue.size() < k) {
            queue.add(num);
        } else if (num < queue.peek()) {
            queue.poll();
            queue.add(num);
        }
    }
    int[] result = new int[k];
    for (int i = 0; i < k; i++) {
        result[i] = queue.poll();
    }
    return result;
}

「快速排序」

把快速排序的过程简单改一下就行了，我们根据基准值和k的的位置决定对左段还是右段进行排序即可，而不是对整个数组进行排序

class Solution {

    public int[] getLeastNumbers(int[] arr, int k) {
        if (arr.length == 0 || k == 0) {
            return new int[0];
        }
        return quickSort(arr, 0, arr.length - 1, k - 1);
    }

    public int[] quickSort(int[] nums, int left, int right, int k) {
        int index = sort(nums, left, right);
        if (index == k) {
            return Arrays.copyOf(nums, k + 1);
        }
        // 根据 index 和 k 的位置决定切左段还是右段
        return index > k ? quickSort(nums, left, index - 1, k) : quickSort(nums, index + 1, right, k);
    }

    public int sort(int[] a, int left, int right) {
        int key = a[left];
        while (left < right) {
            while (left < right && a[right] >= key) {
                right--;
            }
            a[left] = a[right];
            while (left < right && a[left] <= key) {
                left++;
            }
            a[right] = a[left];
        }
        a[left] = key;
        return left;
    }
}

「计数排序」

因为题目中有这样一个条件0 <= arr[i] <= 10000，说明数组中的元素比较集中，我们就可以用计数排序来解决这个问题，因为arr[i]的最大值10000为，所以我每次直接开一个10001大的数组

public int[] getLeastNumbers(int[] arr, int k) {
    if (arr.length == 0 || k == 0) {
        return new int[0];
    }
    int[] countArray = new int[10001];
    for (int num : arr) {
        countArray[num]++;
    }
    int[] result = new int[k];
    int index = 0;
    for (int i = 0; i < countArray.length && index < k; i++) {
        while (countArray[i] > 0 && index < k) {
            countArray[i]--;
            result[index++] = i;
        }
    }
    return result;
}

归并排序

先把数组拆分为只有一个元素，然后对拆分的数组进行合并，主要合并的时候要保证合并后的数组有序，当合并完成时，整个数组有序

public static void mergeSort(int[] a, int left, int right) {
    // 将数组分段成只有一个元素
    if (left == right) {
        return;
    }
    int mid = (left + right) / 2;
    mergeSort(a, left, mid);
    mergeSort(a, mid + 1, right);
    merge(a, left, mid, right);
}

public static void merge(int[] a, int left, int mid, int right) {
    int[] temp = new int[right - left + 1];
    int i = left;
    int j = mid + 1;
    int k = 0;
    while (i <= mid && j <= right) {
        if (a[i] < a[j]) {
            temp[k++] = a[i++];
        } else {
            temp[k++] = a[j++];
        }
    }
    // 复制左边数组剩余的值
    while (i <= mid) {
        temp[k++] = a[i++];
    }
    // 复制右边数组剩余的值
    while (j <= right) {
        temp[k++] = a[j++];
    }
    int index = 0;
    while (left <= right) {
        a[left++] = temp[index++];
    }
}

计数排序

新开辟一个数组，num[i]的含义为原数组中值为i的数有num[i]个。所以算法的局限性比较大，只适合数组元素跨度区间不大的场景。

public static void countingSort(int[] a) {
    int max = Integer.MIN_VALUE;
    for (int num : a) {
        max = Integer.max(max, num);
    }
    int[] count = new int[max + 1];
    for (int num : a) {
        count[num]++;
    }
    int index = 0;
    for (int i = 0; i < count.length; i++) {
        while (count[i] > 0) {
            a[index++] = i;
            count[i]--;
        }
    }
}

上面的算法其实还有个缺陷，但数组中的元素为10000，10001，10002时，我们就得开辟一个10003大小的数组，不现实。所以我们可以改一下映射关系 num[i]的含义为原数组中值为i+min的个数为num[i]

进阶版

public static void countingSort(int[] a) {
    int max = Integer.MIN_VALUE;
    int min = Integer.MAX_VALUE;
    for (int num : a) {
        max = Integer.max(max, num);
        min = Integer.min(min, num);
    }
    int[] count = new int[max - min + 1];
    for (int num : a) {
        count[num - min]++;
    }
    int index = 0;
    for (int i = 0; i < count.length; i++) {
        while (count[i] > 0) {
            a[index++] = i + min;
            count[i]--;
        }
    }
}

「面试过程中经常会遇到求一个数组中的众数时，就可以用计数排序的思想来解决」