漫画：排序算法系列 第一讲（利用插入算法思想解题）

• 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  }