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))