在本系列中，将为大家讲解排序算法相关内容。同时，由于网上排序相关的教程太多了，我会尽可能的讲解一些不一样的内容。而不是按照 排序讲解 标准Titile，什么“十大排序算法”，“经典排序算法”，“排序算法必知必会” 之类的一个一个来进行讲解。所以，如果内容引起不适，概不负责...
01
排序的重要性
在leetcode中，直接搜索排序标签出现的题目有80余道，这是与排序直接相关的题目，不包括其他一些用到排序思想的题目。
同时，各个公司在面试的过程中，或多或少都直接或间接问到过排序相关的内容（毕竟面试官不知道问什么时，都会用排序算法来救救场。不要问我是怎么知道的...），尤其是 快排、堆排序、全排列 等 Topic，在面试中屡试不爽。
百度：堆排序
滴滴：全排列
综上，得出结论：为了offer~排序很重要，我们需要进行掌握。
02
从“插入排序”说起
为什么要先讲插入排序的原因，是因为我觉得插入排序是最容易理解的一个，而且插入这个词有一定的神秘感（好吧，反正我不觉得冒泡最容易理解，谁没事一天去观察吐泡泡？）
插入排序：就是炸金花的时候，你接一个同花顺的过程。（标准定义：在要排序的一组数中，假定前n-1个数已经排好序，现在将第n个数插到前面的有序数列中，使得这n个数也是排好顺序的）
代码示例：
1//go语言示例
2func main() {
3 arr := []int{5, 4, 3, 2, 1}
4 insert_sort(arr)
5}
6
7func insert_sort(arr []int) {
8 for i := 1; i < len(arr); i++ {
9 for j := i; j > 0; j-- {
10 if arr[j] < arr[j-1] {
11 arr[j], arr[j-1] = arr[j-1], arr[j]
12 }
13 }
14 fmt.Println(arr)
15 }
16}
输出：
讲解完了插入排序，我们根据其思想，完成一道题目：
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]
根据分析，得到代码：
1//go
2func sortArrayByParity(A []int) []int {
3 j := 0
4 for i := range A {
5 if A[i]%2 == 0 {
6 A[j], A[i] = A[i], A[j]
7 j++
8 }
9 }
10 return A
11}
如需进群学习交流~
欢迎加微信：llhaohao
转发是对我最大的支持！
注：本系列所有教程中都不会用到复杂的语言特性，大家不需要担心没有学过语法知识。算法思想最重要，使用各语言纯属本人爱好。同时，本系列所有代码均在leetcode上进行过测试运行，保证其严谨性！
温馨提示
小浩算法~
每天一起学习图解漫画算法。
一起刷题，一起成长！
~长按下方二维码进行关注吧~
进群学习交流~