【算法-希尔】

定义

希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。但希尔排序黑白稳定排序算法。
希尔排序是基于插入排序的以下两点性子而提出改进方法的：

• 插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率；
  
• 但插入排序一样平常来说是低效的，由于插入排序每次只能将数据移动一位；
  

希尔排序的基本思想是：先将整个待排序的记载序列分割成为若干子序列分别举行直接插入排序，待整个序列中的记载“基本有序”时，再对全体记载举行依次直接插入排序。
特点

• 时间复杂度: 平均为 O(n log n)，详细取决于所选择的隔断序列。
  
• 空间复杂度: O(1)，是原地排序。
  
• 稳定性: 不稳定排序。
  

算法步调

• 将元素分为n列，并对每枚举行插入排序。
  
• 将n列元素按行举行合并。
  
• 重复步调1-2，此中元素的列数为前次的一半。
  

代码

1. public class ShellSort {
2.     public static void shellSort(int[] arr) {
3.         int n = arr.length;
5.         // 初始gap为数组长度的一半，逐步缩小gap
6.         for (int gap = n / 2; gap > 0; gap /= 2) {
8.             // 对每个子序列进行插入排序
9.             for (int i = gap; i < n; i++) {
10.                 int temp = arr[i];
11.                 int j;
13.                 // 在子序列中进行插入排序
14.                 for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) {
15.                     arr[j] = arr[j - gap];
16.                 }
17.                 // 将temp放在正确的位置
18.                 arr[j] = temp;
19.             }
20.         }
21.     }
22.     public static void main(String[] args) {
23.         int[] arr = {12, 34, 54, 2, 3,1,6,40};
24.         shellSort(arr);
25.         System.out.println("排序后的数组:");
26.         for (int num : arr) {
27.             System.out.print(num + " ");
28.         }
29.     }
30. }

复制代码

• 外层循环控制 gap（隔断），初始值为数组长度的一半，每次迭代后将 gap 减半，直到 gap 为 1。
  
• 内层循环从 gap 位置开始，对每个元素举行插入排序。对于每个 i 位置的元素，在它之前 gap 个位置范围内探求插入位置，并举行元素的移动。
  
• 最后将 temp 插入到正确的位置。
  

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。