【LeetCode刷题篇零】一些基础算法知识和前置技能（上）

排序算法

O(N^2)的排序算法：冒泡、选择、插入

冒泡排序

冒泡的核心是两两比较，大数下沉，小数上浮，比较的轮数是数组的长度 N，每一轮比较的次数为 N - 当前轮的索引：

• 外层循环控制轮数 round: [1，N]
• 内层循环控制次数 i: [0，N - round)

在每一轮当中，内循环中两两比较相邻的两个数，大数下沉（交换），如果某一轮没有发生交换操作，则可以提前终止。

代码如下：

冒泡排序的特点：

• 时间复杂度是 O(N^2)
• 空间复杂度是 O(1)，是原地排序算法
• 冒泡排序是稳定的排序算法

这里的稳定是因为相等的元素不会做交换操作。

选择排序

选择排序的做法是首先从剩余元素中选择一个最小的数与未排序的第一个元素进行交换：

接着再从剩余元素中选择一个最小的元素进行交换：

• 外层循环 i: [0，N)
• 内层循环 j: [i+1, N)

设当前 i 位置值为最小值，内层循环找到最小的数，记住下标，跟当前 i 位置进行交换。

代码如下：

选择排序的特点：

• 时间复杂度是 O(N^2)
• 空间复杂度是 O(1)，是原地排序算法
• 选择排序是不稳定的排序算法

插入排序

每次从数组的无序区间中取一个元素插入到有序的区间中：

• 外层循环 i: [1，N)
• 内层循环 j: [i，0)

内层循环中将当前元素跟前一个元素比较，如果比前一个小就交换，否则结束内层循环。

代码如下：

这个代码还可以继续优化一下，我们可以先记住待插入的元素，然后让 j 从 i 位置往前寻找到合适的位置再插入。在寻找的过程中直接将前面的元素往后面位置覆盖，因为我们记住了一个元素，相当于留出了一个坑位，因此可以前面的元素依次往后挪一个位置，直到找到可插入位置为止。

外层先记住当前的 i 位置的值 tmp，内层每次看 j - 1 位置的数，如果比tmp大的就直接将 j - 1 位置覆盖到 j 位置，如果比tmp小，就结束内层循环，将tmp覆盖到 j 位置。

优化后的代码如下：

这个代码省略了交换操作，做到了原地交换。

插入排序的特点：

• 时间复杂度是 O(N^2)
• 空间复杂度是 O(1)，是原地排序算法
• 插入排序是稳定的排序算法

O(N^2) 的排序算法性能比较：插入排序 > 选择排序 > 冒泡排序，插入排序性能最好，冒泡排序性能最差。

但是在LeetCode刷题的过程中，很少会用到O(N^2) 的排序算法，因为效率比较低，作为了解即可。

希尔排序

希尔排序的核心思想是先使部分有序，最后让整体有序。

这里递增序列也叫做步长，步长的计算公式有很多种，参见下表：

其中 k=1,2,3,4,5,6…N是数组长度。下面是选择步长公式为 (3^k - 1) / 2 的参考代码：

希尔排序的特点：

• 空间复杂度是 O(1)，是原地排序算法
• 希尔排序是不稳定的排序算法

希尔排序的时间复杂度跟所选择的步长计算公式有关：

选择步长公式为 (3^k - 1) / 2 的时间复杂度是 O(n^3/2)，而选择其他步长公式最差可以是 O(n^2)

在大规模乱序数组情况下，希尔排序优于插入排序。

O(NlogN)的排序算法：快排、 归并

快速排序

快排核心思想：选择数组中任一个数字作为分区点，小的放左边，大的放右边

快排按照分区点的选择方式不同，我整理的有两种版本的代码：

第一种：以最右边的元素作为分区点的分区逻辑（快慢指针）