「算法之美系列」排序（JS版）
前言
最近一段时间重（入）拾（门）算法，算法渣渣的我只有做笔记换来一丝丝心里安慰，在这里也记录分享一下，后面将会归纳成一系列吧。比如「递归与回溯」、「深度与广度优先」、「动态规划」、「二分搜索」和「贪婪」等。
冒泡排序（Bubble Sort）
冒泡排序基本思想
给定一个数组，我们把数组里的元素通通倒入到水池中，这些元素将通过相互之间的比较，按照大小顺序一个一个地像气泡一样浮出水面。
冒泡排序实现
每一轮，从杂乱无章的数组头部开始，每两个元素比较大小并进行交换，直到这一轮当中最大或最小的元素被放置在数组的尾部，然后不断地重复这个过程，直到所有元素都排好位置。其中，核心操作就是元素相互比较。
冒泡排序例题分析
给定数组 [2, 1, 7, 9, 5, 8]，要求按照从左到右、从小到大的顺序进行排序。
冒泡排序解题思路
从左到右依次冒泡，把较大的数往右边挪动即可。
文章图片
- 首先指针指向第一个数，比较第一个数和第二个数的大小，由于
2比1大，所以两两交换，[1, 2, 7, 9, 5, 8]。 - 接下来指针往前移动一步，比较
2和7，由于2比7小，两者保持不动，[1, 2, 7, 9, 5, 8]。到目前为止，7是最大的那个数。 - 指针继续往前移动，比较
7和9，由于7比9小，两者保持不动，[1, 2, 7, 9, 5, 8]。现在，9变成了最大的那个数。 - 再往后，比较
9和5，很明显，9比5大，交换它们的位置，[1, 2, 7, 5, 9, 8]。 - 最后，比较
9和8，9比8大，交换它们的位置，[1, 2, 7, 5, 8, 9]。经过第一轮的两两比较，9这个最大的数就像冒泡一样冒到了数组的最后面。 - 接下来进行第二轮的比较，把指针重新指向第一个元素，重复上面的操作，最后，数组变成了：
[1, 2, 5, 7, 8, 9]。 - 在进行新一轮的比较中，判断一下在上一轮比较的过程中有没有发生两两交换，如果一次交换都没有发生，就证明其实数组已经排好序了。
// 冒泡排序算法
const bubbleSort = function (arr) {
const len = arr.length
// 标记每一轮是否发生来交换
let hasChange = true// 如果没有发生交换则已经是排好序的，直接跳出外层遍历
for (let i = 0;
i < len && hasChange;
i++) {
hasChange = false
for (let j = 0;
j < len - 1 - i;
j++) {
if (arr[j] > arr[j + 1]) {
let temp = arr[j]
arr[j] = arr[j + 1]
arr[j + 1] = temp
hasChange = true
}
}
}
}const arr = [2, 1, 7, 9, 5, 8]
bubbleSort(arr)
console.log('arr: ', arr)冒泡排序算法分析
冒泡排序空间复杂度 假设数组的元素个数是
n，由于在整个排序的过程中，我们是直接在给定的数组里面进行元素的两两交换，所以空间复杂度是 O(1)。冒泡排序时间复杂度 给定的数组按照顺序已经排好
- 在这种情况下，我们只需要进行
n?1次的比较，两两交换次数为0，时间复杂度是O(n)。这是最好的情况。 - 给定的数组按照逆序排列。在这种情况下，我们需要进行
n(n-1)/2次比较，时间复杂度是O(n2)。这是最坏的情况。 - 给定的数组杂乱无章。在这种情况下，平均时间复杂度是
O(n2)。
O(n2)。它是一种稳定的排序算法。（稳定是指如果数组里两个相等的数，那么排序前后这两个相等的数的相对位置保持不变。）插入排序（Insertion Sort） 插入排序基本思想
不断地将尚未排好序的数插入到已经排好序的部分。
插入排序特点
在冒泡排序中，经过每一轮的排序处理后，数组后端的数是排好序的；而对于插入排序来说，经过每一轮的排序处理后，数组前端的数都是排好序的。
插入排序例题分析
对数组
[2, 1, 7, 9, 5, 8] 进行插入排序。插入排序解题思路
- 首先将数组分成左右两个部分，左边是已经排好序的部分，右边是还没有排好序的部分，刚开始，左边已排好序的部分只有第一个元素
2。接下来，我们对右边的元素一个一个进行处理，将它们放到左边。
文章图片
- 先来看
1，由于1比2小，需要将1插入到2的前面，做法很简单，两两交换位置即可，[1, 2, 7, 9, 5, 8]。 - 然后，我们要把
7插入到左边的部分，由于7已经比2大了，表明它是目前最大的元素，保持位置不变，[1, 2, 7, 9, 5, 8]。 - 同理，
9也不需要做位置变动，[1, 2, 7, 9, 5, 8]。 - 接下来，如何把
5插入到合适的位置。首先比较5和9，由于5比9小，两两交换，[1, 2, 7, 5, 9, 8]，继续，由于5比7小，两两交换，[1, 2, 5, 7, 9, 8]，最后，由于5比2大，此轮结束。 - 最后一个数是
8，由于8比9小，两两交换，[1, 2, 5, 7, 8, 9]，再比较7和8，发现8比7大，此轮结束。到此，插入排序完毕。
// 插入排序
const insertionSort = function (arr) {
const len = arr.length
for (let i = 1;
i < len;
i++) {
let current = arr[i]
for (let j = i - 1;
j >= 0;
j--) {
// current 小于 j 指向的左侧值，将 j 指向左侧值右移一位
if (current < arr[j]) {
arr[j + 1] = arr[j]
} else {
// 否则将 current 插入到 j 位置，跳出内循环
arr[j] = current
break
}
}
}
}const arr = [2, 1, 7, 9, 5, 8]
insertionSort(arr)
console.log('arr: ', arr)插入排序算法分析
插入排序空间复杂度 【「算法之美系列」排序（JS版）】假设数组的元素个数是
n，由于在整个排序的过程中，是直接在给定的数组里面进行元素的两两交换，空间复杂度是 O(1)。插入排序时间复杂度
- 给定的数组按照顺序已经排好。只需要进行
n-1次的比较，两两交换次数为0，时间复杂度是O(n)。这是最好的情况。 - 给定的数组按照逆序排列。在这种情况下，我们需要进行
n(n-1)/2次比较，时间复杂度是O(n2)。这是最坏的情况。 - 给定的数组杂乱无章。在这种情况下，平均时间复杂度是
O(n2)。
O(n2)，并且它也是一种稳定的排序算法。归并排序（Merge Sort） 归并排序基本思想
核心是分治，就是把一个复杂的问题分成两个或多个相同或相似的子问题，然后把子问题分成更小的子问题，直到子问题可以简单的直接求解，最原问题的解就是子问题解的合并。归并排序将分治的思想体现得淋漓尽致。
归并排序实现
一开始先把数组从中间划分成两个子数组，一直递归地把子数组划分成更小的子数组，直到子数组里面只有一个元素，才开始排序。
排序的方法就是按照大小顺序合并两个元素，接着依次按照递归的返回顺序，不断地合并排好序的子数组，直到最后把整个数组的顺序排好。
归并排序代码示例
// 归并排序
const mergeSort = function (arr, lo, hi) {
if (lo === undefined) {
lo = 0
}
if (hi === undefined) {
hi = arr.length - 1
}// 判断是否剩下最后一个元素
if (lo >= hi) return// 从中间将数组分成两部分
let mid = lo + Math.floor((hi - lo) / 2)
console.log('mid', mid)// 分别递归将左右两边排好序
mergeSort(arr, lo, mid)
mergeSort(arr, mid + 1, hi)// 将排好序的左右两半合并
merge(arr, lo, mid, hi)
}const merge = function (arr, lo, mid, hi) {
// 复制一份原来的数组
const copy = [...arr]// 定义一个 k 指针表示从什么位置开始修改原来的数组，
// i 指针表示左边半的起始位置
// j 指针便是右半边的其实位置
let k = lo
let i = lo
let j = mid + 1while (k <= hi) {
if (i > mid) {
arr[k++] = copy[j++]
} else if (j > hi) {
arr[k++] = copy[i++]
} else if (copy[j] < copy[i]) {
arr[k++] = copy[j++]
} else {
arr[k++] = copy[i++]
}
}
}
const arr = [2, 1, 7, 9, 5, 8]
mergeSort(arr)
console.log('arr: ', arr)其中，
While 语句比较，一共可能会出现四种情况。- 左半边的数都处理完毕，只剩下右半边的数，只需要将右半边的数逐个拷贝过去。
- 右半边的数都处理完毕，只剩下左半边的数，只需要将左半边的数逐个拷贝过去就好。
- 右边的数小于左边的数，将右边的数拷贝到合适的位置，
j指针往前移动一位。 - 左边的数小于右边的数，将左边的数拷贝到合适的位置，
i指针往前移动一位。
利用归并排序算法对数组
[2, 1, 7, 9, 5, 8] 进行排序。归并排序解题思路
文章图片
首先不断地对数组进行切分，直到各个子数组里只包含一个元素。
接下来递归地按照大小顺序合并切分开的子数组，递归的顺序和二叉树里的前向遍历类似。
- 合并
[2]和[1]为[1, 2]。 - 子数组
[1, 2]和[7]合并。 - 右边，合并
[9]和[5]。 - 然后合并
[5, 9]和[8]。 - 最后合并
[1, 2, 7]和[5, 8, 9]成[1, 2, 5, 8, 9]，就可以把整个数组排好序了。
[1, 2, 7] 和 [5, 8, 9] 的操作步骤如下。
文章图片
- 把数组
[1, 2, 7]用L表示，[5, 8, 9]用R表示。 - 合并的时候，开辟分配一个新数组
T保存结果，数组大小应该是两个子数组长度的总和 - 然后下标
i、j、k分别指向每个数组的起始点。 - 接下来，比较下标 i 和 j 所指向的元素
L[i]和R[j]，按照大小顺序放入到下标k指向的地方，1小于5。 - 移动
i和k，继续比较L[i]和R[j]，2比5小。 i和k继续往前移动，5比7小。- 移动
j和k，继续比较L[i]和 R[j]，7比8小。 - 这时候，左边的数组已经处理完毕，直接将右边数组剩余的元素放到结果数组里就好。
归并排序算法分析
归并排序空间复杂度 由于合并 n 个元素需要分配一个大小为
n 的额外数组，合并完成之后，这个数组的空间就会被释放，所以算法的空间复杂度就是 O(n)。归并排序也是稳定的排序算法。归并排序时间复杂度 归并算法是一个不断递归的过程。
举例：数组的元素个数是
n，时间复杂度是 T(n) 的函数。解法：把这个规模为
n 的问题分成两个规模分别为 n/2 的子问题，每个子问题的时间复杂度就是 T(n/2)，那么两个子问题的复杂度就是 2×T(n/2)。当两个子问题都得到了解决，即两个子数组都排好了序，需要将它们合并，一共有 n 个元素，每次都要进行最多 n-1 次的比较，所以合并的复杂度是 O(n)。由此我们得到了递归复杂度公式：T(n) = 2×T(n/2) + O(n)。对于公式求解，不断地把一个规模为
n 的问题分解成规模为 n/2 的问题，一直分解到规模大小为 1。如果 n 等于 2，只需要分一次；如果 n 等于 4，需要分 2 次。这里的次数是按照规模大小的变化分类的。以此类推，对于规模为
n 的问题，一共要进行 log(n) 层的大小切分。在每一层里，我们都要进行合并，所涉及到的元素其实就是数组里的所有元素，因此，每一层的合并复杂度都是 O(n)，所以整体的复杂度就是O(nlogn)。快速排序（Quick Sort） 快速排序基本思想
快速排序也采用了分治的思想。
快速排序实现
把原始的数组筛选成较小和较大的两个子数组，然后递归地排序两个子数组。
举例：把班级里的所有同学按照高矮顺序排成一排。
解法：老师先随机地挑选了同学 A，让所有其他同学和同学 A 比高矮，比 A 矮的都站在 A 的左边，比 A 高的都站在 A 的右边。接下来，老师分别从左边到右边的同学里选择了同学 B 和同学 C，然后不断的筛选和排列下去。
在分成较小和较大的两个子数组过程中，如何选定一个基准值（也就是同学 A、B、C 等）尤为关键。
快速排序实现例题分析
对数组
[2,1,7,9,5,8]进行排序。快速排序解题思路
文章图片
- 按照快速排序的思想，首先把数组筛选成较小和较大的两个子数组。
- 随机从数组里选取一个数作为基准值，比如
7，于是原始的数组就被分成里两个子数组。注意：快速排序是直接在原始数组里进行各种交换操作，所以当子数组被分割出去的时候，原始数组里的排列也被改变了。 - 接下来，在较小的子数组里选
2作为基准值，在较大的子数组里选8作为基准值，继续分割子数组。 - 继续将元素个数大于
1的子数组进行划分，当所有子数组里的元素个数都为1的时候，原始数组也被排好序了。
// 快速排序
const quickSort = function (arr, lo, hi) {
if (lo === undefined) {
lo = 0
}
if (hi === undefined) {
hi = arr.length - 1
}// 判断是否只剩下一个元素，是，则直接返回
if (lo >= hi) return// 利用 partition 函数找到一个随机的基准点
const p = partition(arr, lo, hi)// 递归对基准点左半边和右半边的数进行排序
quickSort(arr, lo, p - 1)
quickSort(arr, p + 1, hi)
}// 交换数组位置
const swap = function (arr, i, j) {
let temp = arr[i]
arr[i] = arr[j]
arr[j] = temp
}// 随机获取位置索引
const randomPos = function (lo, hi) {
return lo + Math.floor(Math.random() * (hi - lo))
}const partition = function (arr, lo, hi) {
const pos = randomPos(lo, hi)
console.log('pos: ', pos)
swap(arr, pos, hi)let i = lo
let j = lo// 从左到右用每个数和基准值比较，若比基准值小，则放在指针 i 指向的位置
// 循环完毕后，i 指针之前的数都比基准值小
while (j < hi) {
if (arr[j] <= arr[hi]) {
swap(arr, i++, j)
}
j++
}
// 末尾的基准值放置到指针 i 的位置， i 指针之后的数都比基准值大
swap(arr, i, j)// 返回指针 i，作为基准点的位置
return i
}const arr = [2, 1, 7, 9, 5, 8]
quickSort(arr)
console.log(arr)快速排序算法分析
快速排序时间复杂度 1、最优情况：被选出来的基准值都是当前子数组的中间数。
这样的分割，能保证对于一个规模大小为
n 的问题，能被均匀分解成两个规模大小为 n/2 子问题（归并排序也采用了相同的划分方法），时间复杂度就是： T(n)=2xT(n/2) + O(n)。把规模大小为
n 的问题分解成 n/2 的两个子问题时，和基准值进行了 n-1 次比较，复杂度就是 O(n)。很显然，在最优情况下，快速排序的复杂度也是 O(nlogn)。2、最坏情况：基准值选择了子数组里的最大后者最小值。
每次都把子数组分成了两个更小的子数组，其中一个的长度为
1，另外一个的长度只比原子数组少 1。举例：对于数组来说，每次挑选的基准值分别是
9、8、7、5、2。解法：划分过程和冒泡排序的过程类似。
算法复杂度为
O(n^2)。提示：可以通过随机地选取基准值来避免出现最坏的情况。
快速排序空间复杂度 和归并排序不同，快速排序在每次递归的过程中，只需要开辟
O(1) 的存储空间来完成交换操作实现直接对数组的修改，又因为递归次数为 logn，所以它的整体空间复杂度完全取决于压堆栈的次数，因此，它的空间复杂度是 O(logn)。推荐阅读
- 画解算法（1.|画解算法：1. 两数之和）
- 八、「料理风云」
- Guava|Guava RateLimiter与限流算法
- 「#1-颜龙武」区块链的价值是什么（）
- 《深度倾听》第5天──「RIA学习力」便签输出第16期
- 一个选择排序算法
- 「按键精灵安卓版」关于全分辨率脚本的一些理解（非游戏app）
- SG平滑轨迹算法的原理和实现
- 《算法》-图[有向图]
- 「我的2017」——2017|「我的2017」——2017,大事件盘点