演算法 - 插入排序和希爾排序

今天來講一下演算法中的插入排序。

1. 數組的插入排序
2. 鏈表的插入排序
3. 希爾排序

一、最簡單的插入排序

9->3->4->2->6->7->5->1

先將9視為有序，然後把它的後一個元素插入有序序列中，有序序列長度加一。

3->9->4->2->6->7->5->1

繼而將4插入，

3->4->9->2->6->7->5->1

然後將2插入，以此類推。

代碼實現如下：

public int[] 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--,所以應當插入j + 1的位置 } return arr;}

插入排序的幾個注意點，

1. 從i = 1開始
2. 進入循環前，拷貝帶插入元素
3. 循環體結束後，j-- 已經執行了，所以應當插入到下標為 j+1 的位置。

二、單鏈表的插入排序

Question : sort a linked list using insertion sort.

鏈表插入排序的難點在於，我們無法通過下標獲取到有序序列的長度，更無法找到插入節點的上一個節點倒著進行大小比較，但是鏈表的優點在於插入方便。

所以您可以先不看答案，想一下怎樣解決單鏈表的插入排序。

Answer:

class ListNode{ ListNode next; int val; ListNode(int val){this.val = val;}}public ListNode insertionSort(ListNode head){ ListNode newHead = new ListNode(0); ListNode cur = head; ListNode pre = newHead; ListNode next; while(cur != null){ next = cur.next; //找到正確的插入位置 while(pre.next!=null && pre.next.val < cur.val){ pre = pre.next; } //把cur插入到pre和pre.next之間 cur.next = pre.next; pre.next = cur; //重置pre pre = newHead; //cur前進，為下一輪循環做準備 cur = next; } return newHead.next;}

list status before sorting:

Unordered list : 9->3->4->2->6->7->5->1->null

Ordered list : newHead->null

We think 9 is ordered , so：

Unordered list : 3->4->2->6->7->5->1->null

Ordered list : newHead->9->null

and then:

Unordered list : 4->2->6->7->5->1->null

Ordered list : newHead->3->9->null

We look like get a new linked list, thanks for the help of newHead!

我們通過一個新的鏈表來儲存已排序的元素，未排序的元素放在原先的鏈表中，通過這種方式，我們實現了鏈表的插入排序。

以上兩種插入排序，最好的情況時間複雜度是O（n）；最差的情況時間複雜度是O(n^2)；平均時間複雜度也是O（n^2）；空間複雜度都是O（1）。

三、希爾排序

這次我們把數組分組，對每組單獨進行插入排序，每排序一次之後，適當擴大分組大小，最後直到整個數組被分成一組。

這就是希爾排序。

請注意，分組是根據某個增量（間隔），從第一個元素開始分組。這裡我們第一次分組時取增量為數組長度的一半，每次排序後，增量減為原來的一半。

第一次分組：

9->3->4->2->6->7->5->1

增量為4，分為 9 6，3 7，4 5，2 1 四組。

排序後：

6->3->4->1->9->7->5->2

第二次分組，增量為2：

分為6495，3172兩組

排序後：

4->1->5->2->6->3->9->7

最後一次分組，增量為1，分為一組，進行插入排序後，排序完成。

public void shellSort(Integer[] sortList) { int i, j, step; int len = sortList.length; // 步長除以2 for (step = len / 2; step > 0; step /= 2) { //分別對每個分組進行直接插入排序 for (i = 0; i < step; i++) { for (j = i + step; j < len; j += step) if (sortList[j] < sortList[j - step]) { int temp = sortList[j]; int k = j - step; while (k >= 0 && sortList[k] > temp) { sortList[k + step] = sortList[k]; k -= step; } sortList[k + step] = temp; } } } }

希爾排序為什麼好呢？

我們可以定性的思考一下：設想這樣一種情況，1到100，這100個數隨機的散落在數組中，而元素5在靠近末尾的位置，經過幾次分組排序後，5將有很大可能放進靠近開頭的位置，除非一個分組中，異常巧合的包含了1，2，3，4，5。

所以希爾排序克服了插入排序的一大缺點：一次只能給元素移動一個位置，即使我們可以」預測「到這個元素將處於較為靠前或靠後的位置，我們也只能慢慢移動。

希爾排序的過程，提供了一個」宏觀有序「的狀態，為最後的插入排序打下了基礎。

希爾排序一定好么？

答案是不一定，設想一個有序序列：1，2，3，4。

插入排序進行了3次比較（1>2? 2>3? 3>4?）

而希爾排序進行了5次比較（1>3? 2>4?加上普通插入的3次）

但是大部分情況下，希爾排序要比直接插入排序好得多。

對於希爾排序，最好的情況，時間複雜度是O（n^1.3)；最壞的情況，時間複雜度是O（n^2）；空間複雜度是O（1）。