什么是排序？
- 初识
- 算法图
JavaScript中的排序
- 普通排序
- 复杂排序
- 复杂排序函数封装
- lodash(v4.17.15)排序函数
- 从V8源码看sort()
必会经典排序算法
- 冒泡排序（最大值置尾排序）
- 选择排序（最小值置头排序）
- 插入排序（寻找位置排序）
- 归并排序（二分递归排序）
- 快速排序（基分递归排序）
leetcode 排序 解法题目
- 35.搜索插入位置（easy）
- 88.合并两个有序数组（easy）
- 191.位1的个数（easy）
- 581.最短无序连续子数组（easy）
- 1331.数组序号转换（easy）
- 56.合并区间（medium）
- 215.数组中的第K个最大元素(medium)
- 参考资料
什么是排序？
初识
生活中也有很多排序，比如考试以后按总分进行降序排列：
第一名700分、第二名699分、第三名698分等等等等
值得注意的是，虽然分数是倒序，但是名次却是正序1，2，3···
排序在生活中的例子实在太多了，就不一一赘述了。
- 排序的英文名为sort
- 排序是一个将无序(乱)的一组数据变为有序的过程
- 有序通常分为两种：升序（asc）和降序（desc）
- 排序在软件开发中非常常见：前端数据排序、后端数据库查表升序（asc）、降序（desc）
- 很多算法依赖于排序算法：栈式算法、二分查找法等等
算法图
无序
降序
升序
JavaScript中的排序
在js中，Array.prototype上的sort()函数可以很方便的达到我们对升序和降序的要求。
- sort()可以升序也可以降序
- sort()排序后，数组本身发生变化，不产生新数组
普通排序
假设要给[2,4,3,1,5]进行排序：
const arr = [2,4,3,1,5]// 升序arr.sort((a,b)=>a-b)// 降序arr.sort((a,b)=>b-a)复杂排序
对于复杂情况的话，例如需要对对象数组根据对象中的某个key排序。
// items按照value排序const items = [ { name: 'Edward', value: 21 }, { name: 'Sharpe', value: 37 }, { name: 'And', value: 45 }, { name: 'The', value: -12 }, { name: 'Magnetic', value: 13 }, { name: 'Zeros', value: 37 }];items.sort((a, b) => a.value - b.value);复杂排序函数封装
// key 需要排序的key// 升序还是降序function sortBy(arr, key, type = 'asc'){ if(!arr || !key) return; let callback = (a, b) => a[key]- b[key] : if( type === 'desc'){ callback = (a, b) => b[key]- a[key] ; } arr.sort(callback);}lodash(v4.17.15)排序函数
- _.sortedIndex(array, value)
- _.sortedIndexBy(array, value, [iteratee=_.identity])
- _.sortedIndexOf(array, value)
- _.sortedUniq(array)
- _.sortedUniqBy(array, [iteratee])
_.sortBy(collection, [iteratees=[_.identity]])
插入位置
_.sortedIndex([30, 50], 40); // => 1复杂插入位置
var objects = [{ 'x': 4 }, { 'x': 5 }]; _.sortedIndexBy(objects, { 'x': 4 }, function(o) { return o.x; });// => 0 // The `_.property` iteratee shorthand._.sortedIndexBy(objects, { 'x': 4 }, 'x');// => 0查询第一个索引
_.sortedIndexOf([4, 5, 5, 5, 6], 5); // => 1去重并排序
_.sortedUniq([1, 1, 2]); // => [1, 2]复杂去重并排序
_.sortedUniqBy([1.1, 1.2, 2.3, 2.4], Math.floor);// => [1.1, 2.3]根据某个key排序
var users = [ { 'user': 'fred', 'age': 48 }, { 'user': 'barney', 'age': 36 }, { 'user': 'fred', 'age': 40 }, { 'user': 'barney', 'age': 34 }]; _.sortBy(users, [function(o) { return o.user; }]);// => objects for [['barney', 36], ['barney', 34], ['fred', 48], ['fred', 40]] _.sortBy(users, ['user', 'age']);// => objects for [['barney', 34], ['barney', 36], ['fred', 40], ['fred', 48]]从V8源码看sort()
- V8源码内部的排序函数叫做InnerArraySort
- InnerArraySort排序算法不仅仅是一种经过多种优化的排序算法
InnerArraySort排序算法综合运用到了快速排序和插入排序
- 对于数组长度小于22的数组，运用插入排序
- 对于数组长度大于等于22的数组，运用快速排序
function InnerArraySort(array, length, comparefn) { // In-place QuickSort algorithm. // For short (length <= 22) arrays, insertion sort is used for efficiency. var InsertionSort = function InsertionSort(a, from, to) { for (var i = from + 1; i < to; i++) { var element = a[i]; for (var j = i - 1; j >= from; j--) { var tmp = a[j]; var order = comparefn(tmp, element); if (order > 0) { a[j + 1] = tmp; } else { break; } } a[j + 1] = element; } }; var QuickSort = function QuickSort(a, from, to) { var third_index = 0; while (true) { // Insertion sort is faster for short arrays. if (to - from <= 10) { InsertionSort(a, from, to); return; } if (to - from > 1000) { third_index = GetThirdIndex(a, from, to); } else { third_index = from + ((to - from) >> 1); } // Find a pivot as the median of first, last and middle element. var v0 = a[from]; var v1 = a[to - 1]; var v2 = a[third_index]; var c01 = comparefn(v0, v1); if (c01 > 0) { // v1 < v0, so swap them. var tmp = v0; v0 = v1; v1 = tmp; } // v0 <= v1. var c02 = comparefn(v0, v2); if (c02 >= 0) { // v2 <= v0 <= v1. var tmp = v0; v0 = v2; v2 = v1; v1 = tmp; } else { // v0 <= v1 && v0 < v2 var c12 = comparefn(v1, v2); if (c12 > 0) { // v0 <= v2 < v1 var tmp = v1; v1 = v2; v2 = tmp; } } // v0 <= v1 <= v2 a[from] = v0; a[to - 1] = v2; var pivot = v1; var low_end = from + 1; // Upper bound of elements lower than pivot. var high_start = to - 1; // Lower bound of elements greater than pivot. a[third_index] = a[low_end]; a[low_end] = pivot; // From low_end to i are elements equal to pivot. // From i to high_start are elements that haven't been compared yet. partition: for (var i = low_end + 1; i < high_start; i++) { var element = a[i]; var order = comparefn(element, pivot); if (order < 0) { a[i] = a[low_end]; a[low_end] = element; low_end++; } else if (order > 0) { do { high_start--; if (high_start == i) break partition; var top_elem = a[high_start]; order = comparefn(top_elem, pivot); } while (order > 0); a[i] = a[high_start]; a[high_start] = element; if (order < 0) { element = a[i]; a[i] = a[low_end]; a[low_end] = element; low_end++; } } } if (to - high_start < low_end - from) { QuickSort(a, high_start, to); to = low_end; } else { QuickSort(a, from, low_end); from = high_start; } } }; if (length < 2) return array; QuickSort(array, 0, num_non_undefined); return array;}必会经典排序算法
经典排序算法有十(几)种，由于当前的能力有限，我将先介绍冒泡、选择、插入、归并和快排这五种排序算法。
看了sort()函数的V8源码以后，是不是一筹莫展觉得“哇 好难”，除了心存敬畏，其实明白算法是会经过不断的优化的，sort()函数处理了根据JavaScript语言特性做了很多性能上的优化。
通常来说我们去开心使用这样性能又好使用又便捷的sort()函数即可，但其实有一些经典的排序算法，还是非常值得去探索一下的。
即使数据结构课上学过，但其实时间一久，砖搬得过多，还是容易忘记的，就算没有忘记，工作几年以后再回过头来看算法，可能会对过去的算法做一个优化。
LeetCode的912题是一个很好的oj环境，适合对自己的排序算法做验证，推荐给大家。
题目：https://leetcode-cn.com/probl...
题解：https://github.com/FrankKai/l...
- 冒泡排序（最大值置尾排序）
- 选择排序（最小值置头排序）
- 插入排序（寻找位置排序）
- 归并排序（二分递归排序）
- 快速排序（基分递归排序）
冒泡排序（最大值置尾排序）
/** * 解法：冒泡排序 * 思路：外层每次循环都是不断将最大值置于尾部,最小值像气泡一样向前冒出 * 性能：4704ms 39.4MB * 时间复杂度：O(n^2) */var sortArray = function (nums) { for (let i = 0; i < nums.length; i++) { for (let j = 0; j < nums.length - 1 - i; j++) { if (nums[j] > nums[j + 1]) { const temp = nums[j]; nums[j] = nums[j + 1]; nums[j + 1] = temp; } } } return nums;}选择排序（最小值置头排序）
/** * 解法：选择排序 * 思路：已排序区间和未排序区间。在未排序区间中找到最小数，与未排序区间的第一项（已排序区间的下一项）交换，将已排序区间从[]构造成[...]，最终完成排序。若是降序的话，则找最大的数。 * 性能：2104ms 41.5MB * 时间复杂度：O(n^2) */var sortArray = function (nums) { for (let i = 0; i < nums.length; i++) { let min = nums[i]; let idx = i; for (let j = i + 1; j < nums.length; j++) { if (nums[j] < min) { min = nums[j]; idx = j; } if (j === nums.length - 1) { let temp = nums[i]; nums[i] = nums[idx]; nums[idx] = temp; } } } return nums;}插入排序（寻找位置排序）
/** * 解法：插入排序 * 思路：已排序区间和未排序区间。取出未排序区间的第一项，在已排序区间上找到自己的位置,一般来说是找foo<x<bar，将x插入foo和bar之间，或者是x<bar插入头部。 * 关键点：插入到指定位置后立即停止在已排序数组中查找 * 性能：2008ms 43.9MB * 时间复杂度：O(n^2) * */var sortArray = function (nums) { const sorted = [nums[0]]; for (let i = 1; i < nums.length; i++) { // j = i - 1; 也行 for (let j = sorted.length - 1; j >= 0; j--) { if (nums[i] < sorted[j]) { if (j === 0) { sorted.splice(j, 0, nums[i]); } } else if (nums[i] >= sorted[j]) { sorted.splice(j + 1, 0, nums[i]); j = -1; // 这里很关键，插入到指定位置后立即停止在已排序数组中查找 } } } return sorted;} /** * 优化版：插入排序（不借助辅助数组） * 思路：插入splice(j/j+1, 0), 删除splice(i, 1)[0] * 需要注意的是: splice()返回的是一个数组，例如[1] * 性能：2372ms 42.5MB * 时间复杂度：O(n^2) */var sortArray = function (nums) { for (let i = 1; i < nums.length; i++) { for (let j = i - 1; j >= 0; j--) { if (nums[i] < nums[j]) { if (j === 0) { nums.splice(j, 0, nums.splice(i, 1)[0]); } } else if (nums[i] >= nums[j]) { nums.splice(j + 1, 0, nums.splice(i, 1)[0]); j = -1; } } } return nums;}归并排序（二分递归排序）
/** * 解法：归并排序 * 思路：将长度为n的数组拆为n/2长度的数组，分别对各自进行排序。再将n/2长度的数组使用归并排序，直到最终的排序的数组长度为2，最后将最终排序的数组依次向上合并 * 核心：二分和递归。类似二分排序，自顶向下二分拆解排序，自底向上合并排序结果。 * 注意：终止递归的条件为if (length <= 1) { return nums; } * 性能：260ms 47.9MB * 时间复杂度: O(nlogn) */var sortArray = function (nums) { const merge = (left, right) => { const result = []; while (left.length && right.length) { if (left[0] >= right[0]) { result.push(right.shift()); } else { result.push(left.shift()); } } while (left.length) { result.push(left.shift()); } while (right.length) { result.push(right.shift()); } return result; }; let length = nums.length; if (length <= 1) { return nums; } let middle = Math.floor(length / 2); let left = nums.splice(0, middle); let right = nums; return merge(sortArray(left), sortArray(right));}快速排序（基分递归排序）
/**解法：快速排序 * 思路： * 1.选中一个分割点split * 2.定义左右双指针，一次遍历将分割值小的置于左侧，比分割值大的置于右侧 * 2.1 左右指针不相遇时 swap(left, right) * 2.2 左右指针相遇时，swap(start, left)并且返回left * 3.分治递归式为左右两侧序列*** * 性能：128ms 40.8MB * 时间复杂度：O(nlogn) */var sortArray = function (nums) { quickSort(nums, 0, nums.length - 1); return nums; // 定义一个***函数 function quickSort(arr, left, right) { if (left < right) { let splitIndex = findSplitIndex(nums, left, right); quickSort(nums, left, splitIndex - 1); quickSort(nums, splitIndex + 1, right); } } // 查找分割值索引 function findSplitIndex(arr, left, right) { const start = left; const splitValue = arr[start]; while (left !== right) { while (left < right && arr[right] > splitValue) { right--; } while (left < right && arr[left] <= splitValue) { left++; } if (left < right) { swap(arr, left, right); } } swap(arr, start, left); return left; } // 交换位置：左右交换、分割点与left交换 function swap(arr, i, j) { const temp = arr[j]; arr[j] = arr[i]; arr[i] = temp; }};算法过程图（来自程序员小灰的文章：漫画：什么是快速排序？（完整版））
leetcode 排序 解法题目
- 35.搜索插入位置（easy）
- 88.合并两个有序数组（easy）
- 191.位1的个数（easy）
- 581.最短无序连续子数组（easy）
- 1331.数组序号转换（easy）
- 56.合并区间（medium）
- 215.数组中的第K个最大元素(medium)
35. 搜索插入位置
题目：https://leetcode-cn.com/probl...
题解：https://github.com/FrankKai/l...
var searchInsert = function(nums, target) { /** * 解法2：推入数组重排序法 96ms better than 6.35% */ nums.push(target); var resortedNums = nums.sort((x,y)=>x-y); return resortedNums.indexOf(target);};88.合并两个有序数组（easy）
题目：https://leetcode-cn.com/probl...
题解：https://github.com/FrankKai/l...
var merge = function(nums1, m, nums2, n) { /** * 特别需要注意的点：这道题会检查nums1数组内存空间最后的存储情况 */ // splice截断数组 nums1.splice(m); nums2.splice(n); // 未使用concat的原因：concat返回一个新数组，而题目需要直接在nums1的空间进行存储 nums2.forEach(num2 => { nums1.push(num2); }); // sort排序当前数组 var ascArr = nums1.sort((a, b) => a - b); return ascArr;};191. 位1的个数（easy）
题目：https://leetcode-cn.com/probl...
题解：https://github.com/FrankKai/l...
/** * @param {number} n - a positive integer * @return {number} */var hammingWeight = function (n) { /**解法4：排序优化count * 性能：88ms 35.7MB */ let strArr = n.toString(2).split(""); strArr.sort((a, b) => parseInt(b) - parseInt(a)); let count = 0; for (let i = 0; i < strArr.length; i++) { if (strArr[i] === "1") count++; } return count;};581.最短无序连续子数组（easy）
题目：https://leetcode-cn.com/probl...
题解：https://github.com/FrankKai/l...
/** * @param {number[]} nums * @return {number} */var findUnsortedSubarray = function (nums) { /** * 解法 * - 克隆数组并排序 * - 找起始元素的索引值 * - startIdx 从头到尾 找到第一个发生变化的元素索引 * - endIdx 从尾到头 找到第一个发生变化的元素索引 */ // 使用[...nums]克隆一个新数组，是因为sort改变的是自身，不会返回一个新数组 var sortedNums = [...nums].sort((a, b) => a - b); var startIdx = 0; for (var i = 0; i < nums.length; i++) { if (nums[i] !== sortedNums[i]) { startIdx = i; break; } } var endIdx = 0; for (var j = nums.length - 1; j >= 0; j--) { if (nums[j] !== sortedNums[j]) { endIdx = j; break; } } var length = endIdx - startIdx > 0 ? endIdx - startIdx + 1 : 0; return length;};1331. 数组序号转换（easy）
题目：https://leetcode-cn.com/probl...
题解：https://github.com/FrankKai/l...
/** * @param {number[]} arr * @return {number[]} */var arrayRankTransform = function(arr) { if (arr.length > Math.pow(10, 5)) return; /** * 生成唯一排序Map */ var uniqArr = Array.from(new Set(arr)); var sortArr = uniqArr.sort((a, b) => a - b); // 构造出一个二维数组作为Map构造器入参 var twoDimArr = sortArr.map((num, idx) => [num, idx + 1]); var idxMap = new Map(twoDimArr); /** * Map中查找数字序号 */ var serialNums = []; for (var i = 0; i < arr.length; i++) { serialNums.push(idxMap.get(arr[i])); } return serialNums;};56.合并区间（medium）
题目：https://leetcode-cn.com/probl...
题解：https://github.com/FrankKai/l...
/** * @param {number[][]} intervals * @return {number[][]} */var merge = function (intervals) { /** * 解法1：排序 + 栈 * 性能：88ms 36.3MB * 思路： * 推入区间 空栈 或者 arr[0]大于栈最后一个区间闭 * 覆盖重叠 arr[0]小于栈最后一个区间闭 * */ intervals.sort((a, b) => a[0] - b[0]); let stack = []; for (let i = 0; i < intervals.length; i++) { let currrentInterval = intervals[i]; let stackLastItem = stack[stack.length - 1]; if (stack.length === 0 || currrentInterval[0] > stackLastItem[1]) { stack.push(currrentInterval); } else if (currrentInterval[0] <= stackLastItem[1]) { stackLastItem[1] = Math.max(stackLastItem[1], currrentInterval[1]); } } return stack;};215. 数组中的第K个最大元素(medium)
题目：https://leetcode-cn.com/probl...
题解：https://github.com/FrankKai/l...
var findKthLargest = function (nums, k) { /** * 解法1：倒序排序输出 */ nums.sort((a, b) => b - a); return nums[k - 1];};参考资料
- https://juejin.im/post/57dcd3...
- https://www.zhihu.com/people/...
- https://leetcode-cn.com/probl...
- https://mp.weixin.qq.com/s?__...
- https://github.com/v8/v8/blob...
期待和大家交流，共同进步，欢迎大家加入我创建的与前端开发密切相关的技术讨论小组：
- 微信公众号： 生活在浏览器里的我们 / excellent_developers
- Github博客: 趁你还年轻233的个人博客
- SegmentFault专栏：趁你还年轻，做个优秀的前端工程师
- Leetcode讨论微信群：Z2Fva2FpMjAxMDA4MDE=（加我微信拉你进群）
努力成为优秀前端工程师！