漫画:排序算法系列 第一讲(利用插入算法思想解题)

  • 2020 年 3 月 30 日
  • 笔记

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

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  }