本系列文章【数据结构与算法】所有完整代码已上传 github，想要完整代码的小伙伴可以直接去那获取，可以的话欢迎点个Star哦~下面放上跳转链接
- https://github.com/Lpyexplore/structureAndAlgorithm-JS
之前的文章，我已经把前端需要了解的数据结构都给说了一边，并且我们也都对其进行了封装。现在我们要开始对排序算法部分进行讲解，排序算法顾名思义，就是对一堆杂乱无章的数据按照一定的规则将它们有序地排列在一起。
在讲解排序算法时，大致分成两大类，如下图
本文先介绍三种简单排序的实现思路以及代码的实现
公众号：Lpyexplore的编程小屋
关注我，不定时更新前端面试题
关注还有更多电子书、面试题、数据结构与算法代码等你来拿
排序算法——简单排序
- 一、大O表示法
- 二、冒泡排序
- 三、选择排序
- 四、插入排序
- 六、结束语
一、大O表示法
大O表示法是一种大致表示算法时间复杂度的表示方法，其中，算法的时间复杂度表示的是算法执行过程中代码所需要的基本运算次数。
问： 假设现在有5个人，分别为 A、B、C、D 、E，它们的身高分别为 165、178、150、180、200，请你找出最高的那个人，并记录比较次数。
我们来说一个特别简单易懂的算法，来了解大O表示法
答： 我们先用 A 跟 B 比较，得 B 比 A 高 ； 那我们就用 B 跟 C 比较，得 C 比 B 矮 ；继续用 B 与 D 比较，得 D 比 B 高 ；最后用 D 跟 E 比较，得 E 比 D 高。因此，最终得出 E 是这五个人里最高得，同时我们记下得比较次数为 4 次。
那么同样用这种方法，人数现在设定为 n，那么我们最多需要比较得次数就为 n - 1 次，此时我们可以将这种算法的时间复杂度就为 O(n)
为什么是 O(n) 呢？因为在用这种表示方法时，其实是一种模糊的统计方法，我们要遵循以下几个原则：
- 代码运行次数只取最高次项
- 所有加法项的常数都用1代替
- 最高次项的常数用1代替
因此当比较次数为 n - 1 时，我们要只取最高次项，并且将最高次项的常数项变为 1，因此用大O表示法就为 O(n)
其它常见的几种大O表示法还有下面几种：
| 符号 | 名称 |
|---|---|
| O(1) | 常数 |
| O(log(n)) | 对数 |
| O(n) | 线性 |
| O(nlog(n)) | 线性和对数乘积 |
| O(n²) | 平方 |
| O( 2 n 2^n 2n) | 指数 |
在之后每种排序算法中，我们都会简单来判断一下它们的时间复杂度，并用大O表示法来表示
二、冒泡排序
冒泡排序是一种最简单粗暴的排序算法，它的排序方式跟它的名字一样，一个个数据往上冒出来。
我们来看一下具体的实现过程（该排序过程为从小到大排序），直接来看个动图
主要的思路其实就是从最左边开始，依次比较相邻两个元素的大小，若左边的数大于右边的数就进行交换，这样把所有的相邻元素都比较一遍以后，最右边的数就是其中最大的数了。
紧接着又继续从最左边开始，依次比较各个相邻元素，并判断是否需要交换位置，但与第一遍不同的是，最右边的数不需要进行比较，因为它已经是最大的了。因此第二遍比较完后从右往左数第二个数是其中第二大的数。
以此类推，就能将数据按从小到大的顺序排好了
我们来看一下如何封装冒泡排序的函数吧
function bubbleSort(arr) {
// 封装一个交换函数,便于之后调用
function exchange(v1, v2) {
let temp = arr[v1]
arr[v1] = arr[v2]
arr[v2] = temp
}
// 获取传入数组的长度
let length = arr.length
// 1. 设置每次遍历的长度,每遍历一次，长度 - 1
for(let i = length - 1; i >= 0; i --) {
// 2. 从最左边的数开始，依次比较相邻元素
for(let j = 0; j < i; j ++) {
// 3. 如果左边的数大于右边的数，则交换一下两个元素
if(arr[j] > arr[j + 1]) {
exchange(j, j + 1)
}
}
}
// 返回排序后的数组
return arr
}
我们来简单测试一下该方法是否正确
let arr = [45, 66, 1, 19, 34, 80, 2]
console.log(bubbleSort(arr));
// 打印结果：[1, 2, 19, 34, 45, 66, 80]
接下来，讨论一下冒泡排序的 比较次数 和 交换次数 如何用大O表示法来表示。
假设一个数组一共有4个数，我们第一次遍历需要比较3次，此时找到一个最大值；第二次遍历只需要将其中3个数进行比较，只需要比较2次，此时找到第二大的值；第三次遍历只需要将剩余的两个数进行比较，只需要比较1次，此时数组排序完毕。如果不明白，可以看一下上面的动图
该种情况的比较次数一共是 3 + 2 + 1 = 6 次。那么延伸到普通情况中，一个数组有 n 个元素，那么所需要的比较次数一共是 (n-1) + (n-2) + …… + 2 + 1 = n*(n-1)/2 ，按照大O表示法的规则，我们找到最高次项为 n²/2，将其常数项设为1，为 n²，因此冒泡排序的比较次数用大O表示法为 O(n²)
我们再来看看冒泡排序的交换次数如何用大O表示法来表示。很明显，我们也不清楚到底要交换几次，所以我们就假设每两次比较就要交换一次的话，其总的交换次数为 n*(n-1)/4，根据大O表示法的规则，我们可以知道交换次数用大O表示法也为 O(n²)
总结：
- 冒泡排序的比较次数：O(n²)
- 冒泡排序的交换次数：O(n²)
三、选择排序
选择排序跟冒泡排序非常类似，唯一的区别就是选择排序每次遍历时，将各个元素比较，将最大值或最小值的索引存放在一个变量中，全部比较完了以后，再将该索引上的元素进行就交换。简单来说就是选择排序是每次遍历交换一次，而冒泡排序每次遍历需要交换多次，因此选择排序一般来说是要比冒泡排序效率高一点的。
同样的，我们来看一下选择排序（从小到大排序）的动图展示：
我们来看一下选择排序的代码封装
function selectionSort(arr) {
// 封装交换元素的函数，方便后面调用
function exchange(v1, v2) {
let temp = arr[v1]
arr[v1] = arr[v2]
arr[v2] = temp
}
// 获取传入数组的长度
let length = arr.length
// 1. 设定遍历的范围
for(let i = 0; i < length - 1; i ++) {
// 2. 先将遍历的起始索引设为最小值的索引
let min = i
// 3. 从索引为min的后一个值开始遍历全部元素
for(let j = min; j < length; j ++) {
// 3.1 将每个遍历到的元素与arr[min]比较
if(arr[min] > arr[j]) {
min = j
}
}
// 4. 将得到的最小值的索引min上的元素与我们初始遍历的位置上的元素交换
exchange(min, i)
}
// 返回排序后的数组
return arr
}
我们来测试一下该方法是否正确
let arr = [45, 66, 1, 19, 34, 80, 2]
console.log(selectionSort(arr));
// 打印结果：[1, 2, 19, 34, 45, 66, 80]
在了解了选择排序与冒泡排序的区别后，我们应该能清楚得知道，选择排序的比较次数跟冒泡排序一样，因此选择排序的比较次数用大O表示法表示为 O(n²)
选择排序每遍历一次数组，就只需要交换一次数据，因此其交换次数用大O表示法表示为 O(n)
总结：
- 选择排序的比较次数：O(n²)
- 选择排序的交换次数：O(n)
四、插入排序
插入排序是一种将指定元素与某个有序区域元素比较并交换位置的排序算法。
我们先简单举个例子，假设现在有这样一个无序数组
首先，我们把索引为0的元素看作区域，该区域是有序的，因为就只有一个元素，怎样排序都是它一个元素，所以就认为它是有序的。
然后我们取出有序区域右边的第一个元素，即索引为1的元素 67，存到变量 temp 中。然后从有序区域的最右边开始，将元素依次与变量 temp 中的元素 67 比较，若大于67，则将位置向右移动一格；若小于67，则不需要继续遍历了，因为该区域是有序的。
第一次遍历的动图：
此时的有序区域为 索引0 ~ 索引1 这部分，所以我们将索引为2的元素取出，跟有序区域的元素比较
第二次遍历的动图：
此时的有序区域为 索引0 ~ 索引2 这部分，所以我们将索引为3的元素取出，跟有序区域的元素比较
第三次遍历的动图：
此时的有序区域为 索引0 ~ 索引3 这部分，所以我们将索引为4的元素取出，跟有序区域的元素比较
第四次遍历的动图：
此时整个数组都是有序区域了，这就是一个完整的插入排序
接下来我们来封装一个插入排序的函数
function insertionSort(arr) {
// 获取传入数组的长度
let length = arr.length
// 1. 从索引为1的元素开始向后遍历数组
for(let i = 1; i < length; i ++) {
// 2. 取出有序区域右边第一个元素
let temp = arr[i]
let j = i
// 3. 从右往左将有序区域内的元素与temp比较
while(arr[j - 1] > temp && j > 0) {
arr[j] = arr[j - 1]
j --
}
// 4. 将temp插入到合适的位置
arr[j] = temp
}
// 返回排序后的数组
return arr
}
我们来测试一下该函数是否正确
let arr = [45, 66, 1, 19, 34, 80, 2]
console.log(insertionSort(arr));
// 打印结果：[1, 2, 19, 34, 45, 66, 80]
插入排序每次遍历时，比较次数和元素的移动次数都是不确定，那我们就按最坏的情况来考虑。
第一次遍历：比较次数为1，元素移动次数为1；
第二次遍历：比较次数为2，元素移动次数为2；
……
第N次遍历：比较次数为N，元素移动次数为N；
所以，插入排序的比较次数为 1 + 2 + …… + n，元素的移动次数也和比较次数一样，那么我们对其取个平均值，也就是 (n² - n)/4，用大O表示法表示为 O(n²)
总结：
- 插入排序的比较次数：O(n²)
- 插入排序的元素移动次数：O(n²)
六、结束语
排序算法中的简单排序就已经讲完啦，下一篇文章将讲解三种高级排序算法：希尔排序、归并排序、快速排序。
大家可以关注我，之后我还会一直更新别的数据结构与算法的文章来供大家学习，并且我会把这些文章放到【数据结构与算法】这个专栏里，供大家学习使用。
然后大家可以关注一下我的微信公众号：Lpyexplore的编程小屋，等这个专栏的文章完结以后，我会把每种数据结构和算法的笔记放到公众号上，大家可以去那获取。
或者也可以去我的github上获取完整代码，欢迎大家点个Star
- https://github.com/Lpyexplore/structureAndAlgorithm-JS
我是Lpyexplore，创作不易，喜欢的加个关注，点个收藏，给个赞~
