数据结构之八大排序（上）

找往期文章包括但不限于本期文章中不懂的知识点：

个人主页：我要学编程(ಥ_ಥ)-CSDN博客

所属专栏：数据结构（Java版）

排序的相关介绍

直接插入排序

希尔排序（缩小增量排序）

选择排序

堆排序

冒泡排序

排序的相关介绍

排序的概念：所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。

稳定性：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的。

内部排序：数据元素全部放在内存中的排序。

外部排序：数据元素太多不能同时放在内存中，根据排序的要求在内外存之间移动数据的排序。

两个5的相对位置发生了变化，就是不稳定的排序。

注意：稳定的排序，也可以变成是不稳定的排序；而不稳定的排序无法变成稳定的排序。

排序运用：我们日常生活中，在网上买东西时，根据价钱来筛选，这就用到了排序。

常见的排序算法有八种，根据对数据的处理方式分类：

下面我们就来详细学习：

直接插入排序

思路：把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列。实际中我们玩扑克牌时，就用了插入排序的思想。

思路：

代码实现：

    public static void insertSort(int[] array) {for (int i = 1; i < array.length; i++) {int j = i-1;int tmp = array[i];while (j >= 0) {if (array[j] > tmp) {// 大于，就让其往后走array[j+1] = array[j];j--;} else {// 有序就直接判断后面的break;}}// 让tmp中的值回到数组中array[j+1] = tmp;}}

时间复杂度：O(N^2)：最坏情况就是数据全部是逆序的。例如：我们是要排成从小到大的顺序，数据给的是 5 4 3 2 1。然而，当数据本身就是有序的情况下，也就只会进行判断，因此这时的时间复杂度就是O(N)。这里就可以得出一个结论：数据越有序，效率越高。

空间复杂度：O(1) ：只申请了常数个空间

稳定性：稳定的排序。本身是一个稳定的排序，可以实现为不稳定的。

希尔排序（缩小增量排序）

希尔排序法又称缩小增量法。希尔排序法的基本思想是：先选定一个整数，把待排序文件中所有记录分成多个组，所有距离为的记录分在同一组内，并对每一组内的记录进行排序。然后，取重复上述分组和排序的工作。当到达分组 =1时，所有记录在统一组内排好序。如下图所示：

这个gap的求值有很多种最常见的就是：总数据 / 2 和总数据 / 3 + 1。

代码实现：

    public static void shellSort(int[] array) {// 先分组int gap = array.length;while (gap > 1) {gap /= 2;// 根据分组来排序shell(array, gap);}}// 分组排序private static void shell(int[] array, int gap) {// i 是组内要排序的第二个数据for (int i = gap; i < array.length; i++) {// j 是组内要排序的第一个数据int j = i-gap;int tmp = array[i];while (j >= 0) {if (array[j] > tmp) {array[j+gap] = array[j];j -= gap;} else {break;}}array[j+gap] = tmp;}}

注意：

1、希尔排序是对直接插入排序的优化。

2、i 在加时，虽然 i += gap ，最终的排序结果是对的（因为gap 最终还是会等于1，就相当于直接进行直接插入排序了），但是并不符合逻辑要求。

3、当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了，这样就会很快。这样整体而言，可以达到优化的效果。

4、希尔排序的时间复杂度不好计算，因为gap的取值方法很多，导致很难去计算。

时间复杂度：O(n^1.3 - n^1.5)：很多著名的书籍上面的估算结果。

空间复杂度：O(1)：申请了常数个空间。

稳定性：不稳定。

选择排序

基本思想：每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。

代码实现：

    public static void selectSort(int[] array) {for (int i = 0; i < array.length; i++) {int minIndex = i;for (int j = i+1; j < array.length; j++) {// 更新最小值下标if (array[j] < array[minIndex]) {minIndex = j;}}// 交换if (minIndex != i) {swap(array, i, minIndex);}}}private static void swap(int[] array, int i, int j) {int tmp = array[i];array[i] = array[j];array[j] = tmp;}

注意：

1. 直接选择排序思考非常好理解，但是效率不是很好。实际中很少使用。

2. 时间复杂度：O(N^2)：无论是最好情况还是最坏情况，时间复杂度都是一样的。也就是说和数据的顺序无关。

3. 空间复杂度：O(1)：申请了常数个空间。

4. 稳定性：不稳定。

情况二属于第一个元素是重复的元素且不是最小的。

优化：既然是找最小值，那么我们直接既找最小值又找最大值，然后两头交换即可，这样效率就提升了不少。

代码实现：

    public static void selectSort(int[] array) {int left = 0;int right = array.length-1;while (left < right) {int minIndex = left;int maxIndex = left;for (int i = left+1; i <= right; i++) {if (array[minIndex] > array[i]) {minIndex = i;}if (array[maxIndex] < array[i]) {maxIndex = i;}}// 开始交换swap(array, minIndex, left);// 如果left位置是最大值，那么第一次交换时，就会把最大值换走，换成最小值// 那么我们在第二次交换时，只会把最小值交换走，无法拿到最大值if (maxIndex == left) {maxIndex = minIndex;}swap(array, maxIndex, right);left++;right--;}}

堆排序

堆排序(Heapsort)是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。它是通过堆来进行选择数据。需要注意的是：从小到大排序得建大根堆；从大到小排序得建小根堆。想要了解更多的知识，可以去看这篇博客：数据结构之探索“堆”的奥秘-CSDN博客

思路：首先，就是要建一个大根堆，然后根据删除的思路来交换数据，再进行向下调整来重新使其变成大根堆。一直重复该步骤，直至遍历完成数组。

代码实现：

    public static void heapSort(int[] array) {// 从小到大排序建大根堆createHeap(array);// 开始排序heap_sort(array);}private static void createHeap(int[] array) {// 向下调整建堆（时间复杂度比较小：O(N)）// 从最后一棵子树的位置开始向下调整建堆for (int parent = (array.length-1-1)/2 ; parent >= 0; parent--) {siftDown(array, parent, array.length);}}private static void siftDown(int[] array, int parent, int end) {int child = parent*2+1;// 大根堆while (child < end) {// 先找到左右孩子的最大值if (child+1 < end && array[child] < array[child+1]) {child++;}// 判断孩子节点的值和父亲节点的值满不满足大根堆的要求if (array[child] > array[parent]) {swap(array, parent, child);parent = child;child = parent*2+1;} else {break;}}}private static void heap_sort(int[] array) {// 模拟删除的思想int end = array.length-1;int start = 0;while (end > 0) {swap(array, end, start);siftDown(array, start, end);end--;}}

如果这个代码有疑惑的话，可以去看上面的链接博客，那里有画图更加的清晰明了。

注意：

1. 堆排序使用堆来选数，效率就高了很多。

2. 时间复杂度：O(N*logN)：向下建堆的时间复杂度为O(N) + 排序的时间复杂度为O(N*logN).

3. 空间复杂度：O(1)：只申请了常数个空间。

4. 稳定性：不稳定。

冒泡排序

冒泡排序是属于交换排序的一种。

交换排序，基本思想：所谓交换，就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置，交换排序的特点是：将键值较大的记录向序列的尾部移动，键值较小的记录向序列的前部移动（从小到大排序）。

其实这里已经告诉我们思路了，而且冒泡排序我们在C语言阶段，JavaSE阶段就进行了学习，因此下面就直接给出代码了。

代码实现：

    public static void bubbleSort(int[] array) {// 冒泡排序的特点和堆排序一样，是后面的数据先有序for (int i = 0; i < array.length-1; i++) { // 趟数boolean flag = true; // 假设数据已经有序了for (int j = 0; j < array.length-1-i; j++) { // 每一趟比较的内容if (array[j] > array[j+1]) {swap(array, j, j+1);flag = false; // 交换了，就说明数据还不是有序的}}// 如果没有交换，就说明有序，则不在交换if (flag) {break;}}}

注意：

1. 冒泡排序是一种非常容易理解的排序。

2. 时间复杂度：O(N^2)：在时间复杂度那篇博客中有详细介绍，有兴趣的小伙伴可以看一看。