Java—排序1

本篇将详细讲解插入排序、希尔排序和堆排序三种经典排序算法，包括算法原理、执行过程、易错点分析，并为每种算法提供三道例题及详细解析。

---

一、插入排序（Insertion Sort）

算法原理

插入排序的核心思想是将待排序数组分为已排序和未排序两部分。初始时，已排序部分仅包含第一个元素。随后，从未排序部分取出一个元素，在已排序部分从后向前扫描，找到合适的位置插入该元素(比取出元素大或小时)，直到所有元素有序。

• 时间复杂度：最优O(n)（数组已有序），最差O(n^2)（数组逆序），平均O(n^2)。
• 空间复杂度$O(1)（原地排序）。

执行过程

1. 从第二个元素开始遍历（索引i = 1）。
2. 将当前元素arr[i]暂存为key。
3. 从j = i - 1向前扫描已排序部分：
   • 若arr[j] > key，则将arr[j]后移一位。
   • 否则跳出循环。
4. 将key插入到正确位置。

易错点

1. 边界条件：循环索引从1开始，内层循环终止条件为j >= 0。
2. 元素移动：需用while而非for循环，确保及时终止扫描。
3. 稳定性：遇到相等元素时不移动，保证稳定性。

---

例题1：对整数数组升序排序

public void insertionSort(int[] arr) { for (int i = 1; i < arr.length; i++) { int key = arr[i]; int j = i - 1; while (j >= 0 && arr[j] > key) { // 易错点：需同时检查边界和大小 arr[j + 1] = arr[j]; j--; } arr[j + 1] = key; } }

解析：经典实现，注意内层循环需同时判断j >= 0和arr[j] > key。

例题2：对链表排序（使用插入排序）

public ListNode insertionSortList(ListNode head) { ListNode dummy = new ListNode(0); ListNode cur = head; while (cur != null) { ListNode prev = dummy; while (prev.next != null && prev.next.val < cur.val) { prev = prev.next; } ListNode next = cur.next; cur.next = prev.next; prev.next = cur; cur = next; } return dummy.next; }

解析：链表需使用虚拟头节点dummy简化插入操作，注意断开原节点的链接。

---

例题3：对浮点数数组降序排序

public void insertionSortDesc(double[] arr) { for (int i = 1; i < arr.length; i++) { double key = arr[i]; int j = i - 1; while (j >= 0 && arr[j] < key) { // 降序：将 > 改为 < arr[j + 1] = arr[j]; j--; } arr[j + 1] = key; } }

解析：仅需将内层循环条件改为arr[j] < key即可实现降序。

---

二、希尔排序（Shell Sort）

算法原理

希尔排序是插入排序的改进版，通过分组插入提升效率。设定一个增量序列（如$n/2, n/4, \dots, 1$），对每个增量间隔的分组进行插入排序，最后增量减至1时整体排序。

• 时间复杂度：约O(n^1.3)（依赖增量序列）。
• 空间复杂度：O(1)。

执行过程

1. 选择初始增量gap = n/2。
2. 对每个增量分组执行插入排序。
3. 缩小增量（如gap /= 2），重复步骤2，直到gap = 1。

易错点

1. 增量序列：常用Knuth序列（h = 3h + 1）而非简单折半。
2. 分组方式：每个分组是间隔gap的子序列，而非连续子数组。
3. 终止条件：增量需覆盖到gap = 1。

---

例题1：整数数组升序排序（Knuth增量）

public void shellSort(int[] arr) { int n = arr.length; int gap = 1; while (gap < n / 3) gap = 3 * gap + 1; // Knuth序列：1, 4, 13, ... while (gap >= 1) { for (int i = gap; i < n; i++) { int key = arr[i]; int j = i; while (j >= gap && arr[j - gap] > key) { // 注意索引 j-gap arr[j] = arr[j - gap]; j -= gap; } arr[j] = key; } gap /= 3; // 缩小增量 } }

解析：使用Knuth序列优化效率，内层循环索引需以gap为步长移动。

---

例题2：字符串按长度排序

public void shellSortStrings(String[] arr) { int n = arr.length; int gap = 1; while (gap < n / 3) gap = 3 * gap + 1; while (gap >= 1) { for (int i = gap; i < n; i++) { String key = arr[i]; int j = i; while (j >= gap && arr[j - gap].length() > key.length()) { arr[j] = arr[j - gap]; j -= gap; } arr[j] = key; } gap /= 3; } }

解析：比较条件改为字符串长度，注意稳定性不受影响。

---

例题3：自定义对象按字段排序

class Person { String name; int age; } public void shellSortPersons(Person[] arr) { int n = arr.length; int gap = 1; while (gap < n / 3) gap = 3 * gap + 1; while (gap >= 1) { for (int i = gap; i < n; i++) { Person key = arr[i]; int j = i; while (j >= gap && arr[j - gap].age > key.age) { arr[j] = arr[j - gap]; j -= gap; } arr[j] = key; } gap /= 3; } }

解析：对自定义对象按age字段排序，需确保比较逻辑正确。

---

三、堆排序（Heap Sort）

算法原理

堆排序基于二叉堆数据结构：

1. 建堆：将无序数组构建成最大堆（父节点值 ≥ 子节点）。
2. 排序：交换堆顶（最大值）与末尾元素，缩小堆范围，重新调整堆结构。

• 时间复杂度：建堆O(n)，排序O(n log n)，总O(n \log n)。
• 空间复杂度：O(1)。

执行过程

1. 建堆：从最后一个非叶子节点（索引n/2 - 1）开始，自底向上执行heapify。
2. 排序：
   • 交换堆顶与末尾元素。
   • 堆大小减1，对堆顶执行heapify。
   • 重复直到堆大小为1。

易错点

1. 索引计算：父子节点索引关系为left = 2*i + 1，right = 2*i + 2。
2. 堆调整范围：每次交换后堆大小减1，调整范围需随之缩小。
3. 堆调整方向：heapify需从根节点向下递归调整。

---

例题1：整数数组升序排序

public void heapSort(int[] arr) { int n = arr.length; // 建堆（从最后一个非叶子节点开始） for (int i = n / 2 - 1; i >= 0; i--) { heapify(arr, n, i); } // 排序：交换堆顶与末尾元素 for (int i = n - 1; i > 0; i--) { swap(arr, 0, i); heapify(arr, i, 0); // 调整剩余堆 } } private void heapify(int[] arr, int n, int i) { int largest = i; int left = 2 * i + 1; int right = 2 * i + 2; if (left < n && arr[left] > arr[largest]) largest = left; if (right < n && arr[right] > arr[largest]) largest = right; if (largest != i) { swap(arr, i, largest); heapify(arr, n, largest); // 递归调整子树 } }

解析：注意建堆时需从n/2 - 1开始倒序调整。

---

例题2：数组降序排序（最小堆）

public void heapSortDesc(int[] arr) { int n = arr.length; // 建最小堆：将比较改为 < for (int i = n / 2 - 1; i >= 0; i--) { heapifyMin(arr, n, i); } // 排序逻辑相同 for (int i = n - 1; i > 0; i--) { swap(arr, 0, i); heapifyMin(arr, i, 0); } } private void heapifyMin(int[] arr, int n, int i) { int smallest = i; int left = 2 * i + 1; int right = 2 * i + 2; if (left < n && arr[left] < arr[smallest]) smallest = left; if (right < n && arr[right] < arr[smallest]) smallest = right; if (smallest != i) { swap(arr, i, smallest); heapifyMin(arr, n, smallest); } }

解析：将heapify中的比较改为<即可实现最小堆，从而得到降序序列。

---

例题3：对二维数组按行首元素排序

public void heapSort2D(int[][] matrix) { int n = matrix.length; // 建堆（按每行第一个元素） for (int i = n / 2 - 1; i >= 0; i--) { heapify2D(matrix, n, i); } for (int i = n - 1; i > 0; i--) { swapRows(matrix, 0, i); heapify2D(matrix, i, 0); } } private void heapify2D(int[][] matrix, int n, int i) { int largest = i; int left = 2 * i + 1; int right = 2 * i + 2; if (left < n && matrix[left][0] > matrix[largest][0]) largest = left; if (right < n && matrix[right][0] > matrix[largest][0]) largest = right; if (largest != i) { swapRows(matrix, i, largest); heapify2D(matrix, n, largest); } }

解析：比较逻辑改为matrix[i][0]，交换时需整行交换（swapRows方法需自定义）。

---

总结

1. 插入排序：小规模数据高效，实现简单但$O(n^2)$复杂度。
2. 希尔排序：通过分组插入提升效率，增量序列影响性能。
3. 堆排序：O(n log n)复杂度且原地排序，适合大规模数据。

三种排序各有适用场景，理解其原理及易错点对编写正确代码至关重要。