# 排序：十大经典排序算法有哪些应用

请添加图片描述

# 十大排序算法思路汇总

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

请添加图片描述

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

插入类：将数分为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 void quickSort(int[] a, int left, int right) {
    if (left >= right) {
        return;
    }
    int x = left, y = right, z = a[left];
    while (x < y) {
        while (x < y && a[y] > z) {
            y--;
        }
        if (x < y) {
            a[x++] = a[y];
        }
        while (x < y && a[x] < z) {
            x++;
        }
        if (x < y) {
            a[y--] = a[x];
        }
    }
    a[x] = z;
    quickSort(a, left, x - 1);
    quickSort(a, x + 1, right);
}

在这里插入图片描述 经典的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，则不用调整了

# 归并排序

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

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]--;
        }
    }
}

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

# 基数排序

面试过程中快拍和归并排序问的比较多，应用场景也比较多，基数排序基本没被问到，不做解释了。

# 桶排序

前面我们提到的计数排序和基数排序可以说是桶排序思想的一种特殊体现，就是不需要进行数组元素之间的比较。基本没被问到，不做解释了

# 练习排序

题目地址：LeetCode 912 在这里插入图片描述可以使用 LeetCode 912 练习各种排序算法

# 稳定排序和非稳定排序

排序以后相同值的相对顺序是否改变

# 各种算法的效率

在这里插入图片描述

← 复杂度分析：如何进行时间复杂度和空间复杂度分析？堆：求解 TopK →