本文为历史博客迁移
常见排序
- 冒泡
- 插入
- 选择
- 快排
冒泡排序
原理解析
首先解释一下为什么叫冒泡排序，因为排序过程是将相邻元素依次比较，按照某个规则（取大或者取小）把符合条件的元素筛选出来。
比如排序结果要从小到大，那么每次相邻元素比较，更大的那个元素就会被放到两个元素中后一个元素的位置，用作下一次比较。这样每次遍历结束，本次遍历中的最大元素就会像水中的泡泡一样冒出来放到数组尾部，当依次将剩余元素遍历结束，则得到从小到大的有序数组。
代码实现
function bubble(arr) {
for (var i = 0; i < arr.length - 1; i++) {
for (var j = 0; j < arr.length - 1 - i; j++) {
if (arr[j] > arr[j + 1]) [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
}
}
}
代码解读
关键部分为j < arr.length - 1 - i，核心比较发生在内层循环，由于核心操作是比较相邻元素，所以内层循环每次都是从数组头部开始依次比较相邻元素。
但是外层循环每进 1，就意味着数组尾部冒出一个泡泡（最大值或最小值），所以内层循环的比较可以排除已经冒出的泡泡元素，所以用数组元素数减去外层循环进行到的索引数。
另外，内层循环是拿当前元素和其相邻的下一个元素进行比较，所以遍历元素止于整个数组的倒数第二个元素即可，因为每轮的最后一次比较都会取到最后一个元素。
总结
第一轮遍历会得到整个数组的最值放到数组尾部，第二轮会得到次最值放到数组倒数第二位，以此类推。
选择排序
算法解读
选择排序很容易和冒泡排序弄混，冒泡是永远在比较相邻元素，而选择排序重在选择，意在选择一个元素作为标杆，在本轮遍历中依次将其他元素和它比较，这样一轮比较结束后，就可以得出一个极值（最大或最小）
代码分析
如下代码，第一轮遍历，就是拿数组的第一个元素，依次和后面的所有元素依次比较。
如果比较下来，第一个元素都是更小的那个，那第一个元素就是整个数组的最小元素；如果第一个元素在比较过程中发现有比它小的，则会发生位置交换，然后再继续比较后面的元素。
这样每一轮的结果是都会把这一轮的极值放到该轮遍历开始的位置，也就是选择该轮遍历开始的位置作为标杆，故名选择排序。
总结
外层循环是在依次选择当前元素作为标杆，内层循环是在拿标杆和其余元素依次比较，每当内层循环结束触发外层循环进 1 时，都会拿到一个当前极值。
具体来说，第一次内层循环结束时，数组第一个元素一定是最小（或最大）值，第二次内层循环结束时，数组第二个元素一定是第二小（或大）值，以此类推。
优化
如果每次比较当前元素和标杆发现当前元素比标杆更小（或大）时就进行位置交换，性能会比较差，在得到当前轮极值前的交换都是没必要进行的。所以可以暂存每次比较的极值，把一轮的所有比较完成后再发生位置交换。
比如拿到一个[9,7,8,6,4,5,3,1,2]这样的数组，第一轮以 9 为标杆，当比较 9 和 7 后就交换位置，得到的 7 并不是最小值，后面 7 和 6 比较时又需要交换位置。其实完全可以先假定一个最小值，初始化为元素第一个值，然后依次比较其他元素，将最后得到的最小值和第一个元素交换一次位置即可。（即内层循环只做比较和重新给标杆赋值，不发生元素交换）
优化后代码：
function select(arr) {
for (var i = 0; i < arr.length - 1; i++) {
var flag = i;
for (var j = i + 1; j < arr.length; j++) {
if (arr[j] < arr[flag]) {
flag = j;
}
}
[arr[i], arr[flag]] = [arr[flag], arr[i]];
}
}
插入排序
关键词：扑克整牌
解析
想象打扑克抓牌的场景，当抓完所有牌后，开始从小到大（或从大到小）整理排面。
从第二张牌开始，如果第二张牌比第一张牌小，则插入到第一张牌前，否则不动，此轮结束后第一张牌是目前看来最小的牌。
然后拿第三张牌，依次和它前面的牌比较（先第二张，再第一张），如果小于第二张则继续和第一张比较，当发现第三张牌介于两张牌的大小中间，则进行插入。
如果比前面的牌都大则不动，如果比前面的牌都小则插入到牌头部。
代码实现
function insert(arr) {
var temp;
var pre;
for (var i = 1; i < arr.length; i++) {
pre = i - 1;
// 拿出的元素
temp = arr[i];
// 当未比较到第一个元素并且拿出的元素小于前面的某个元素
while (pre >= 0 && temp < arr[pre]) {
// 如果拿出的元素比前一个元素小，则前一个元素后移
arr[pre + 1] = arr[pre];
pre--;
}
// 比到某一个位置，拿出的元素介于两元素大小之间，则插入
arr[pre + 1] = temp;
}
}
代码分析
拿出的元素发生插入的时机一共有三种：
- 比前面的元素都大，则放回到原位
- 比前面的元素都小，则插入到头部
- 大小位于前面某两个元素中间，则插入两元素中间
由于拿出每次要进行比较的元素最终要插入到一个新的位置，在插入前，会有前面的元素占据这个元素的位置，所以需要先暂存当前元素，最终插入到腾出的空位。
具体的插入其实体现在当目标元素前面存在比目标元素大的元素，则会向后移动，占据目标元素原本的位置，所以此时目标元素拿出后需要暂存在一个临时地方。
特点
当发生插入操作时，意味着不仅仅是位置交换，而是被插入位置后面的元素依次都后移了。
快排
核心思想
快排之所以复杂是因为用到了分治+递归，但这也是其效率高的原因。
首先在全局寻找一个元素作为基准，将小于基准的元素都放到左边，大于基准的元素都放到右边，以此粗略将所有元素分为两派；再分别在两个派别中重复此操作。
代码实现
function quick(arr) {
if (arr.length <= 1) return arr;
var flag = Math.floor(arr.length / 2);
var element = arr.splice(flag, 1)[0];
var l = [];
var r = [];
for (var i = 0; i < arr.length; i++) {
arr[i] < element ? l.push(arr[i]) : r.push(arr[i]);
}
return quick(l).concat([element], quick(r));
}
代码分析
递归返回的条件是数组不存在元素或数组只有一个元素，这样返回的数组可直接作为元素用于数组拼接。
每次选当前数组的中间值作为基准，其实可以为任意值。然后将中间值取出，将剩余值按照大于或小于基准值进行分开。
代码仓库见: https://github.com/barnett617/codehub/blob/main/front-end/src/6-sort-algorithm/index.md