Java数据结构第十九期：解构排序算法的艺术与科学(一)
专栏：Java数据结构秘籍
个人主页：手握风云
目录
一、排序的概念及引用
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次，那么时间复杂度的计算为
，时间复杂度为
，这是最坏情况下。如果数组本身就是有序的，那么时间复杂度为
。空间上，我们没有使用额外的数组，空间复杂度为
。所以插入排序适合应用于数组本身就趋向于有序的情况。
我们再思考一下插入排序的稳定性，上面的代码中，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)); } }希尔排序是不稳定的，不同组交换期间很可能导致元素的相对位置发生改变。空间上，没有申请额外的内存空间，空间复杂度为
。时间复杂度上，我们假设有n个数据，每次除2，都会
……当gap=1时，循环结束，所以外循环的时间复杂度
。希尔排序的时间复杂度的分析至今还非常困难，难度在于弄清比较次数和移动对象与增量选择的关联，并给出完整的数学分析。如果gap非常大的时候，那么j回退的次数就越少，几乎可以认为是常数。当gap非常小的时候，j需要分的组也很小，整体时间复杂度也为1。
