本文介紹插入排序和希爾排序，插入排序是較為常見的排序算法，希爾排序也是基礎的排序算法，廢話不多說，具體來看一下兩種算法。

山

插入排序

插入排序的基本思想是拿到下一個插入元素，在已經有序的待排數組部分找到自己的位置，然后進行數據的移動，完成該元素的排序，依次類推，直到整個待排數組有序，初始狀態待排數組的有序部分僅有一個元素。代碼如下：

public static void sort(int[] nums) { Arrays.nonBlank(nums); for (int i = 1; i < nums.length; i++) { for (int j = i; j > 0; j--) { if (nums[j] < nums[j - 1]) { int temp = nums[j]; nums[j] = nums[j - 1]; nums[j - 1] = temp; } } }}

上面這種方式兩兩數據交換，換到合適位置，每次交換多了兩次賦值操作，下面是實現的標準模式：

public static void sort2(int[] nums) { Arrays.nonBlank(nums); for (int i = 1; i < nums.length; i++) { int temp = nums[i]; // 記錄插入值 int j; for (j = i; j > 0 && temp < nums[j - 1]; j--) { nums[j] = nums[j - 1];// 尋找位置，能夠減少賦值的次數 } nums[j] = temp;// 找到位置，完畢 }}

以上就是插入排序的兩種實現方式，并沒有改進，其時間復雜度為O(n^2)，妥妥的兩層循環，另外插入排序是穩定排序，存不存在一種改進的插入排序呢？答案是有的，這就是我們下面要介紹的希爾排序；

希爾排序

希爾排序是插入排序的改進版。主要改進思路是減少插入排序中數據的移動次數，設置步長，在初始數組較大時取較大步長，通常初始步長為待排數組長度1/2，此時只有兩個元素比較，交換一次，此時數組為部分有序數組；之后步長依次減半直至步長為1，即為插入排序，此時數組已接近有序，所以插入元素時數據移動次數會相對較少，效率得到提高，實現代碼如下：

public static void sort(int[] nums) { Arrays.nonBlank(nums); int N = 0 + nums.length; for (int gap = N / 2; gap > 0; gap /= 2) { for (int i = gap; i < N; i++) { insert(nums, i, gap); } }}?private static void insert(int[] nums, int i, int gap) { int inserted = nums[i]; int j; for (j = i - gap; j > 0 && nums[j] > inserted; j -= gap) { nums[j + gap] = nums[j]; } nums[j + gap] = inserted;}

既然為改進算法，那么相比較插入排序，希爾排序的到底快了多少呢？為此特意去找了資料，一般書上都說希爾排序的時間復雜度是O(n^3/2)，但是學過算法的都知道有最壞時間復雜度的，希爾排序的時間復雜度其實是和增列序列有關系的，即我們程序實現的步長，{1,2,4,8,...}這種序列就是我們程序中實現的這種，并不是很好的增量序列，使用這個增量序列的時間復雜度(最壞情形)是O(n^2)，Hibbard提出了另一個增量序列{1,3,7，...,2^k-1}(質數增量)，這種序列的時間復雜度(最壞情形)為O(n^1.5)，這個提高就很厲害了，只是修改一個算法的一個參數；Sedgewick提出了幾種增量序列，其最壞情形運行時間為O(n^1.3),其中最好的一個序列是{1,5,19,41,109,...}，最后這個就當是科普小知識吧，因為給你你也不一定能用，請原諒我的直接，當別人說希爾排序的最壞時間復雜度是O(n^2)的時候，你也可以給他們科普一下，希爾排序的最壞時間復雜度是可以做到O(n^1.3)的。

總結

插入排序感覺是最為直觀的排序方式，如果有人沒有學過算法，人們最直接的排序方式就是，一個一個去找數字的位置，確定，然后再去找下一個，所以思想很簡單，但是我們看到即時這樣簡單地排序思想，到了希爾這里，也能玩出花，所以對任何東西，尤其是簡單的事物，都要心懷敬畏啊。

構成我們學習最大障礙的是已知的東西，而不是未知的東西。——貝爾納

總結

以上是生活随笔為你收集整理的希尔排序 最坏时间_排序算法（2）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。