6种排序如下
- 冒泡排序
- 计数排序
- 疾速排序
- 归并排序
- 插入排序
- 抉择排序
工夫复杂度如下图
冒泡排序
这个名字的由来是向泡泡一样浮起来，脑补一下，就是每次比拟相邻的两个元素大小，而后缓缓'沉没'起来，我瞎掰的，看思路吧。
「工夫复杂度O(n^2)」
思路
- 比拟相邻的元素，前者比后者大的话，两者替换地位。
- 对每一对相邻元素做雷同操作，从开始第一对到最初一对，这样子最初的元素就是最大元素。
- 针对n个元素反复以上步骤，每次循环排除以后最初一个。
- 反复步骤1~3，直到排序实现。
动画
冒泡排序
代码实现
// 最外层循环管制的内容是循环次数// 每一次比拟的内容都是相邻两者之间的大小关系let BubbleSort = function (arr) { let len = arr.length for (let i = 0; i < len - 1; i++) { for (let j = 0; j < len - 1 - i; j++) { if (arr[j] > arr[j + 1]) { // 从大到小 [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]] } } } return arr}let arr = [2, 9, 6, 7, 4, 3, 1, 7]console.log(BubbleSort(arr))计数排序
从名称上就晓得，它的思维：就是把数组元素作为数组的下标，而后用一个长期数组统计该元素呈现的次数。
数组的数据必须是整数，而且最大最小值相差的值不要过大，对于「数据是正数的话，我实现的计划对此有优化」。
「工夫复杂度：O(n+k)」
思路
1.计算出差值d,最小值小于0,加上自身add
2.创立统计数组并统计对应元素个数
3.统计数组做变形，前面的元素等于后面的元素之和,也就是排名数组
4.遍历原始数组,从统计数组中找到正确地位,输入到后果数组
动画
计数排序
代码实现
// 计数排序let countingSort = function(arr) { let min = arr[0], max = arr[0], len = arr.length; // 求最大最小值 for(let i = 0; i < len; i++) { max = Math.max(arr[i], max) min = Math.min(arr[i], min) } // 1.计算出差值d,最小值小于0,加上自身add let d = max - min, add = min < 0 ? -min : 0; //2.创立统计数组并统计对应元素个数 let countArray = new Array(d+1+add).fill(0) for(let i = 0; i < len; i++){ let demp = arr[i]- min + add countArray[ demp ] += 1 } //3.统计数组做变形，前面的元素等于后面的元素之和,也就是排名数组 let sum = 0; // 这里须要遍历的是countArray数组长度 for(let i = 0; i < d+1+add; i++){ sum += countArray[i] countArray[i] = sum; } let res = new Array(len) // 4.遍历原始数组,从统计数组中找到正确地位,输入到后果数组 for(let i = 0; i < len; i++){ let demp = arr[i] -min + add res[ countArray[demp] -1 ] = arr[i] countArray[demp] --; } return res}let arr = [2, 9, 6, 7, 4, 3, 1, 7,0,-1,-2]console.log(countingSort(arr))疾速排序
根本思维：通过一趟排序将待排记录分隔成独立的两局部，其中一部分记录的关键字均比另一部分的关键字小，则可别离对这两局部记录持续进行排序，以达到整个序列有序。
「工夫复杂度：O(nlogn)」
思路
- 抉择数组两头数作为基数，并从数组中取出此基数
- 筹备两个数组容器，遍历数组，一一与基数比对，较小的放右边容器，较大的放左边容器；
- 递归解决两个容器的元素，并将解决后的数据与基数按大小合并成一个数组，返回。
优化：三数取中、替换宰割
三数取中：
在快排的过程中，每一次咱们要取一个元素作为枢纽值，以这个数字来将序列划分为两局部。在此咱们采纳三数取中法，也就是取左端、两头、右端三个数，而后进行排序，将两头数作为枢纽值。
依据枢纽值进行宰割：
https://juejin.cn/post/6844903657616441352
动画
疾速排序
代码实现
let quickSort = function (arr) { // 递归进口就是数组长度为1 if (arr.length <= 1) return arr //获取两头值的索引，应用Math.floor向下取整； let index = Math.floor(arr.length / 2) // 应用splice截取两头值，第一个参数为截取的索引，第二个参数为截取的长度； // 如果此处应用pivot=arr[index]; 那么将会呈现有限递归的谬误； // splice影响原数组，splice影响原数组,该当被删除 let pivot = arr.splice(index, 1)[0], left = [], right = []; for (let i = 0; i < arr.length; i++) { if (pivot > arr[i]) { left.push(arr[i]) } else { right.push(arr[i]) } } return quickSort(left).concat([pivot], quickSort(right));}//let arr = [2, 9, 6, 7, 4, 3, 1, 7]// console.log(quickSort(arr))归并排序
将两个有序数列合并成一个有序数列，咱们称之为“归并”
根本思维与过程：先递归的合成数列，再合并数列（分治思维的典型利用）
「工夫复杂度: O(nlog(n))」
思路
- 将一个数组拆成A、B两个小组，两个小组持续拆，直到每个小组只有一个元素为止。
- 依照拆分过程逐渐合并小组，因为各小组初始只有一个元素，能够看做小组外部是有序的，合并小组能够被看做是合并两个有序数组的过程。
- 对左右两个小数列反复第二步，直至各区间只有1个数。
动画
归并排序
代码实现
const merge = (left, right) => { // 合并数组 let result = [] // 应用shift()办法偷个懒,删除第一个元素,并且返回该值 while (left.length && right.length) { if (left[0] <= right[0]) { result.push(left.shift()) } else { result.push(right.shift()) } } while (left.length) { result.push(left.shift()) } while (right.length) { result.push(right.shift()) } return result}let mergeSort = function (arr) { if (arr.length <= 1) return arr let mid = Math.floor(arr.length / 2) // 拆分数组 let left = arr.slice(0, mid), right = arr.slice(mid); let mergeLeftArray = mergeSort(left), mergeRightArray = mergeSort(right) return merge(mergeLeftArray, mergeRightArray)}let arr = [2, 9, 6, 7, 4, 3, 1, 7, 0, -1, -2]console.log(mergeSort(arr))插入排序
顾名思义：通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应地位并插入。
「工夫复杂度: O(n^2)」
思路
- 从第一个元素开始，该元素能够认为曾经被排序；
- 取出下一个元素，在曾经排序的元素序列中从后向前扫描；
- 如果该元素（已排序）大于新元素，将该元素移到下一地位；
- 反复步骤3，直到找到已排序的元素小于或者等于新元素的地位；
- 反复步骤2~5。
动画
代码实现
let insertionSort = function (arr) { let len = arr.length // 双指针，以后和前一个 for (let i = 0; i < len; i++) { let preIndex = i - 1, cur = arr[i]; // 第一个元素无前一个元素，能够间接赋值 while (preIndex >= 0 && arr[preIndex] > cur) { arr[preIndex + 1] = arr[preIndex] preIndex--; } arr[preIndex + 1] = cur } return arr}let arr = [2, 9, 6, 7, 4, 3, 1, 7, 0, -1, -2]console.log(insertionSort(arr))抉择排序
思路：每一次从待排序的数组元素中抉择最大(最小)的一个元素作为首元素,直到排完为止
「工夫复杂度O(n^2)」
思路
- 有n个数,须要排序n-1次
- 第一次抉择最小值,放在第一位
- 第二次抉择最小值,放在第二位
- …..反复该过程
- 第n-1次抉择最小值,放在第n-1位
动画
代码实现
let selectSort = function (arr) { let len = arr.length, temp = 0; // 一共须要排序len-1次 for (let i = 0; i < len - 1; i++) { // 设定替换指标，从数组的第一个开始 temp = i; for (let j = i + 1; j < len; j++) { if (arr[j] < arr[temp]) temp = j; } // 每一趟保障第i位为最小值 if (temp !== i) { [arr[i], arr[temp]] = [arr[temp], arr[i]] } } return arr}let arr = [2, 9, 6, 7, 4, 3, 1, 7, 0, -1, -2]console.log(selectSort(arr))