Java数据结构第十九期：解构排序算法的艺术与科学(一)

专栏：Java数据结构秘籍

个人主页：手握风云

一、排序的概念及引用

1.1. 排序的概念

1.2. 排序的应用

1.3. 常见的算法>排序算法

二、常见算法>排序算法的实现

2.1. 直接插入排序

2.2. 希尔排序

一、排序的概念及引用

1.1. 排序的概念

所谓排序，就是使⼀串记录，按照其中的某个或某些关键字的⼤⼩，递增或递减的排列起来的操作。

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

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

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

1.2. 排序的应用

1.3. 常见的算法>排序算法

二、常见算法>排序算法的实现

2.1. 直接插入排序

类比一下，在玩扑克牌的时候，从牌堆中拿取一张牌进行排序，就用到了插入排序。插入排序的过程：让i从第二个元素为起始位置，j=i-1，当arr[j]>arr[i]，用tmp接收i下标的值，让j下标的元素向前移，然后让j--，如果tmp的值大于j下标的值，就把tmp的插入j的后面；如果tmp一直比j下标的值小，就让j一直--，当j<0时，那么tmp的值就插入第一个位置。上述过程就能保证i下标之前的元素保持是有序的。当i走到最后一个元素时，就完成了这个插入排序

        for (int i = 1; i < array.length; i++) {int tmp = array[i];for (int j = i - 1; j >= 0; j--) {if (array[j] > tmp) {array[j + 1] = array[j];} else {array[j + 1] = tmp;}}}

上述代码我们还可以进行优化，如果数组本身就是有序的，再来一个更大的数，不用再让j向前移动了，直接break就可以了。如果j走到了-1的位置，就说第一个元素已经挪开了，就不会再走for循环了，我们再把tmp的值放回来。

public class Sort {public void InsertSort(int[] array) {for (int i = 1; i < array.length; i++) {int tmp = array[i];int j = i - 1;for (; j >= 0; j--) {if (array[j] > tmp) {array[j + 1] = array[j];} else {break;}}array[j + 1] = tmp;}}
}

import java.util.Arrays;public class Solution {public static void main(String[] args) {int[] array = {87, 5, 32, 55, 43, 26};Sort sort = new Sort();sort.InsertSort(array);System.out.println(Arrays.toString(array));}
}

我们来分析一下时间复杂度：当i为1的时候，j最多回退1次；当i为2的时候，j最多回退2次，那么时间复杂度的计算为 $1+2++(n-1)=1/2(n-1)(n-2)$ ，时间复杂度为 $O(n) = n^{2}$ ，这是最坏情况下。如果数组本身就是有序的，那么时间复杂度为 $O(n)=n$ 。空间上，我们没有使用额外的数组，空间复杂度为 $O(n)=1$ 。所以插入排序适合应用于数组本身就趋向于有序的情况。

我们再思考一下插入排序的稳定性，上面的代码中，array[j] > tmp，才会执行，两个数相等则不会。如果我们改成array[j]>=tmp，就会变得不稳定。所以，如果排序本身就是稳定的，可以调整为不稳定的；如果排序本身就是不稳定的，则是无法变为稳定的。

我们要想更直观的看到运行消耗的时间，我们可以写出一个方法，来计算我们运行的时间：

import java.util.Arrays;
import java.util.Random;/*** @author: gao* @create-date: 2025/3/7 12:47*/public class Solution {public static void Order(int[] array) {for (int i = 0; i < array.length; i++) {array[i] = i;}}public static void ReverseOrder(int[] array) {for (int i = 0; i < array.length; i++) {array[i] = array.length - i;}}public static void DisOrder(int[] array) {Random ran = new Random();for (int i = 0; i < array.length; i++) {array[i] = ran.nextInt(array.length);}}public static void TestInsertSort(int[] array) {long StartTime = System.currentTimeMillis();Sort sort = new Sort();sort.InsertSort(array);long EndTIme = System.currentTimeMillis();System.out.println("直接插入排序耗时：" + (EndTIme - StartTime));}public static void main(String[] args) {int[] array = new int[10_000];ReverseOrder(array);TestInsertSort(array);}
}

2.2. 希尔排序

希尔排序又称“缩小增量排序”，可以看作是直接插入排序的优化。所谓“缩小增量”，就是采用分组的思想，在组内进行插入排序。比如说，我们可以5个一组进行连续地划分（如下图所示），有的人可能会说，进行跳跃式地分组，但这样分组会出现的一种情况，就是尽可能把大的数据往后放，小的数据往前放。很明显第一种分组明显优于第二种。

当gap > 1时都是预排序，⽬的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了，这样就会很快。这样整体而言，可以达到优化的效果。我们实现后可以进⾏性能测试的对比。

上面我们采用的是gap=5，接下来缩小间距，gap=2划分区间。这里不能写成i+=gap，这样会导致有些组没有参与排序。i++才能让每一组进行交互式排序。所以说不管gap为几，本质上还是执行插入排序。

我们接下来思考的问题是为什么要缩小增量。组数越大。组内数据越少；组数越小。组内数据越多，效率就越低。在增量缩小的过程中，数组就趋向于有序。

public class Sort {public void ShellSort(int[] array) {int gap = array.length / 2;while (gap > 0) {Shell(array, gap);gap /= 2;}}public void Shell(int[] array, int gap) {for (int i = gap; i < array.length; i++) {int tmp = array[i];int j = i - gap;for (; j >= 0; j-= gap) {if (array[j] > tmp) {array[j + gap] = array[j];} else {break;}}array[j + gap] = tmp;}}
}

import java.util.Arrays;public class Solution {public static void main(String[] args) {int[] array = {5, 11, 7, 2, 3, 17};Sort sort = new Sort();sort.ShellSort(array);System.out.println(Arrays.toString(array));}
}

希尔排序是不稳定的，不同组交换期间很可能导致元素的相对位置发生改变。空间上，没有申请额外的内存空间，空间复杂度为 $O(n)=1$ 。时间复杂度上，我们假设有n个数据，每次除2，都会 $n/2+n/4+n/8$ ……当gap=1时，循环结束，所以外循环的时间复杂度 $O(n) = logn$ 。希尔排序的时间复杂度的分析至今还非常困难，难度在于弄清比较次数和移动对象与增量选择的关联，并给出完整的数学分析。如果gap非常大的时候，那么j回退的次数就越少，几乎可以认为是常数。当gap非常小的时候，j需要分的组也很小，整体时间复杂度也为1。