按奇偶排序数组（905）

在本系列中，将为大家讲解排序算法相关内容。同时，由于网上排序相关的教程太多了，我会尽可能的讲解一些不一样的内容。而不是按照 排序讲解 标准Titile，什么“十大排序算法”，“经典排序算法”，“排序算法必知必会” 之类的一个一个来进行讲解。所以，如果内容引起不适，概不负责…

01、排序的重要性

在leetcode中，直接搜索排序标签出现的题目有80余道，这是与排序直接相关的题目，不包括其他一些用到排序思想的题目。

同时，各个公司在面试的过程中，或多或少都直接或间接问到过排序相关的内容（毕竟面试官不知道问什么时，都会用排序算法来救救场。不要问我是怎么知道的…），尤其是 快排、堆排序、全排列 等 Topic，在面试中屡试不爽。

综上，得出结论：为了offer~排序很重要，我们需要进行掌握。

02、从“插入排序”说起

为什么要先讲插入排序的原因，是因为我觉得插入排序是最容易理解的一个，而且插入这个词有一定的神秘感（好吧，反正我不觉得冒泡最容易理解，谁没事一天去观察吐泡泡？）

插入排序：就是炸金花的时候，你接一个同花顺的过程。（标准定义：在要排序的一组数中，假定前n-1个数已经排好序，现在将第n个数插到前面的有序数列中，使得这n个数也是排好顺序的）

代码示例：

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、题目分析

示例：

输入：[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

04、题目图解

这道题，按照插入排序的思想，很容易可以想到题解。我们只需要遍历数组，当我们遇到偶数时，将其插入到数组前最近的一个为奇数的位置， 与该位置的奇数元素交换。为了达成该目的，我们引入一个指针 j，来维持这样一个奇数的位置。

假设我们的数组为：[3,1,2,4]

根据以上分析，得到代码：

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
}

执行结果：