漫畫：排序算法系列 第一講（利用插入算法思想解題）

• 2020 年 3 月 30 日
• 筆記

01 排序的重要性

在leetcode中，直接搜索排序標籤出現的題目有80餘道，這是與排序直接相關的題目，不包括其他一些用到排序思想的題目。

同時，各個公司在面試的過程中，或多或少都直接或間接問到過排序相關的內容（畢竟面試官不知道問什麼時，都會用排序算法來救救場。不要問我是怎麼知道的…），尤其是 快排、堆排序、全排列 等 Topic，在面試中屢試不爽。

百度：堆排序

滴滴：全排列

綜上，得出結論：為了offer~排序很重要，我們需要進行掌握。

02 從「插入排序」說起

為什麼要先講插入排序的原因，是因為我覺得插入排序是最容易理解的一個，而且插入這個詞有一定的神秘感（好吧，反正我不覺得冒泡最容易理解，誰沒事一天去觀察吐泡泡？）

插入排序：就是炸金花的時候，你接一個同花順的過程。（標準定義：在要排序的一組數中，假定前n-1個數已經排好序，現在將第n個數插到前面的有序數列中，使得這n個數也是排好順序的）

代碼示例：

//go語言示例  func main() {      arr := []int{5, 4, 3, 2, 1}      insert_sort(arr)  }    func insert_sort(arr []int) {      for i := 1; i < len(arr); i++ {          for j := i; j > 0; j-- {              if arr[j] < arr[j-1] {                  arr[j], arr[j-1] = arr[j-1], arr[j]              }          }          fmt.Println(arr)      }  }  

輸出：

講解完了插入排序，我們根據其思想，完成一道題目：

03

905. 按奇偶排序數組

第905題：給定一個非負整數數組 A，返回一個數組，在該數組中， A 的所有偶數元素之後跟着所有奇數元素。你可以返回滿足此條件的任何數組作為答案。

示例：

輸入：[3,1,2,4]

輸出：[2,4,3,1]

輸出 [4,2,3,1]，[2,4,1,3] 和 [4,2,1,3] 也會被接受。

提示：

1 <= A.length <= 5000

0 <= A[i] <= 5000

這道題，按照插入排序的思想，很容易可以想到題解。我們只需要遍曆數組，當我們遇到偶數時，將其插入到數組前最近的一個為奇數的位置，與該位置的奇數元素交換。為了達成該目的，我們引入一個指針 j，來維持這樣一個奇數的位置。

假設我們的數組為：[3,1,2,4]

根據分析，得到代碼：

//go  func sortArrayByParity(A []int) []int {      j := 0      for i := range A {          if A[i]%2 == 0 {              A[j], A[i] = A[i], A[j]              j++          }      }      return A  }