決勝經典算法之插入排序

2019 年 10 月 3 日
筆記

習題答案

題目回顧

在上一篇文章中，我們以數列從小到大排列為例，講了選擇排序。結尾處的思考題如下：

如果要實現從大到小排列，上述代碼該做如何修改呢？

同樣，要解答這個問題也很簡單，下面放上答案。

答案

我們知道，從小到大排序時，選擇排序就是選出最小的數，並將其放在最開始的位置。同理，從大到小排序時，只需要選出最大的數，將其放在最開始的位置就可以了。參考如下代碼：

public static void selectSort(int[] arr) {      for (int i = 0; i < arr.length; i++) {          int min = i;          for (int j = i; j < arr.length; j++) {              if (arr[j] > arr[min]) {                  min = j;              }          }            if (min != i) {              int temp = arr[i];              arr[i] = arr[min];              arr[min] = temp;          }      }  }

怎麼樣，你答對了嗎？

本篇文章的內容是講第三種排序方法——插入排序。
還是之前的問題：

問題挑戰

現有如下數字：
3，44，38，5，47，15，36，26，27，2，46，4，19，50，48
一共15個數字，請將其從小到大依次排列。

算法解析

所謂「插入排序」，重點在「插入」。具體說來，就是評估數列裏面的每一個元素。這種評估依次進行，數列中，如果它前面的數值比它小（從小到大排序時），則把它放在比它小的數值後，直到最後一個元素評估完成。
整個過程理解起來並不難，結合下面的動圖演示將會更加清晰直接。

詳細步驟

下面讓我們來分步驟拆解整個插入排序：

從第一個元素開始，該元素可以認為已經被排序；
取出下一個元素，在已經排序的元素序列中從後向前掃描；
如果該元素（已排序）大於新元素，將該元素移到下一位置；
重複步驟3，直到找到已排序的元素小於或者等於新元素的位置；
將新元素插入到該位置後；重複步驟2~5，直到最後一個元素完成。

整個流程如下圖所示：

偽代碼

接下來，我們使用偽代碼實現上述過程

InsertSort (input ele[],input length)  for i <-- 1 to n-1      for j <-- i-1 to 0      if a[i] > a[j] break  if j!=i-1  temp <-- a[i]  for k <-- i to j+2      a[k] <-- a[k-1]  a[j+1] <-- temp  end

Java代碼實現

接下來，我們使用Java編程語言實現上述算法。

public static void insertSort(int[] arr) {      int temp;      int j;      for (int i = 1; i < arr.length; i++) {          for (j = i - 1; j >= 0; j--) {              if (arr[i] > arr[j])              break;          }          if (j != i - 1) {              temp = arr[i];              for (int k = i; k > j + 1; k--) {                  arr[k] = arr[k - 1];              }              arr[j + 1] = temp;          }      }  }

思考題

1. 如果要實現從大到小排列，上述代碼該做如何修改呢？

思考題答案依舊會在下篇連載中公布，大家加油哦！