|
前端必知的十大排序算法
周末梳理了十种排序算法当作复习，给大家也一起重温一下，下面将讲解10种应用较多的排序算法，其代码实现使用了JavaScript。
冒泡排序
思路：
循环数组，比较当前元素和下一个元素，若当前元素比下一个大，则向上冒泡，这样一次循环之后最后一个数就是该数组最大的数。
下一次循环继续上面的操作，不循环已经排序好的数。
当一次循环没有发生冒泡，说明已经排序完成，停止循环。
function bubbleSort(array){
for(let i = 0; i < array.length; i++){
let flag = true;
for(let j = 0; j < array.length - 1 - i; j++){
if(array[j] > array[j + 1]){
[array[j],array[j + 1]] = [array[j + 1],arr[j]];
flag = false;
}
}
if(flag){// 没有冒泡，则停止循环
break;
}
}
return array;
}
时间复杂度：O(N2N^2N2)
空间复杂度：O(111)
稳定性：稳定
快速排序
思路：
通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据均比另一部分的小，再按这种方法对这两部分数据继续进行快排，排序过程使用递归进行，使整个数据变得有序。可以看出，快排利用了分治的思想。
选择一个基准元素target（一般选首项）
将比target小的元素移到数组左边，比target大的元素移到数组右边（与target相等的移动到哪边都可以）
继续对左右部分进行快排
/*
* 法一：开辟left和right两个空间来存储
* 每次递归返回left、target、right拼接后的数组
*/
function quickSort(array){
if(array.length < 2) return array;
const target = array[0];
const left = [], right = [];
for(let i = 1; i < array.length; i++){
if(array[i] < target) {
left.push(array[i]);
}else{
right.push(array[i]);
}
}
return quickSort(left).concat([target],quickSort(right));
}
/*
* 法二：双下标法
* 声明l和r分别为首尾两个下标
* 在 l < r 条件下，找到 array[r] < target的值赋给array[l]
* 在 l < r 条件下，找到 array[r] >= target的值赋给array[r]
* 当 l = r 时，左侧的值全部小于 target，右侧的值全部大于target，将target放到此位置
* 相对于上一种方法，节省了空间
*/
function quickSort(arr,start,end){
if(end - start < 1) {
return;
}
const target = array[start];
let l = start, r = end;
while(l < r){
while(l < r && array[r] >= target){
r--;
}
array[l] = array[r];
while(l < r && array[l] < target){
l++;
}
array[r] = array[l];
}
array[l] = target;
quickSort(array, start, l - 1);
quickSort(array, l + 1, end);
return array;
}
时间复杂度：平均O(NlogNNlogNNlogN)，最坏O(N2N^2N2)，一般情况下小于O(NlogN)
空间复杂度：O(logNlogNlogN)，递归调用消耗
稳定性：不稳定
归并排序
思路：
归并排序（MERGE-SORT）是利用归并的思想实现的排序方法，该算法采用分治策略（分治法将问题分成一些小的问题然后递归求解，而治的阶段则将分的阶段得到的各答案“修补”在一起，即分而治之）。
将数组不断的进行一拆二，拆到每个数组中只有一个元素为止
对每个数组两两进行合并，其中每个数组内都是有序的
// 分割数组时直接将数组分割为两个数组，合并时直接合并数组
function mergeSort(array){
if(array.length < 2){
return array;
}
const mid = Math.floor(array.length / 2);
const left = array.slice(0, mid);
const right = array.slice(mid);
return merge(mergeSort(left), mergeSort(right));
}
function merge(left, right) {
const result = [];
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;
}
时间复杂度：O(NlogNNlogNNlogN)
空间复杂度：O(NNN)
稳定性：稳定
选择排序
思路：
每次循环选取一个最小的数字放到前面的有序序列中。
function selectionSort(array, flag = false) { // flag用于选择顺序
for(let i = 0; i < array.length - 1; i++){
let minIndex = i;
for(let j = i + 1; j < array.length; j++){
if(array[j] < array[minIndex]){
minIndex = j;
}
}
[array[minIndex], array[i]] = [array[i], array[minIndex]];
}
return flag ? arr.reverse() : arr;
}
时间复杂度：O(N2N^2N2)
空间复杂度：O(111)
稳定性：不稳定
插入排序
思路：
将左侧序列看成一个有序序列，取出下一个元素，从右往左扫描扫描已排序的序列
如果该元素小于新元素，继续往前扫描，否则将该元素移到下一位
当找到元素小于或等于新元素的位置时，则停止
重复以上步骤至整个循环结束
function insertSort(array){
for(let i = 0; i < array.length; i++){
let preIndex = i - 1, cur = array[i];
while(preIndex >= 0 && array[preIndex] > cur){
array[preIndex + 1] = array[preIndex];
preIndex--;
}
array[preIndex + 1] = cur;
}
return array;
}
时间复杂度：O(N2N^2N2)
空间复杂度：O(111)
稳定性：稳定
堆排序
堆是具有以下性质的完全二叉树：
每个结点的值都大于或等于其左右孩子结点值，称为大顶堆
每个结点的值都小于或等于其左右孩子结点值，称为小顶堆
注意：没有要求结点的左右孩子结点值的大小关系。
大顶堆如下：
下标为i的节点的父节点下标：(i−1)/2(i - 1) / 2(i−1)/2取整
下标为i的节点的左孩子下标：i∗2+1i * 2 + 1i∗2+1
下标为i的节点的右孩子下标：i∗2+2i*2+2i∗2+2
这里我们举例大顶堆的思路：
将待排序序列构造成一个大顶堆，取堆顶数字（也就是最大值）
再将剩下的数字构建一个大顶堆，取堆顶数字（也就是剩下值当中的最大值）
重复以上操作，直到取完堆中的数字，最终得到一个从大到小排列的序列
/*
* 维护堆的性质
* @param arr 存储堆的数组
* @param n 数组长度
* @param i 待维护节点的下标
*/
function heapify(arr,n,i){
let largest = i;
let lson = i * 2 + 1;
let rson = i * 2 + 2;
// 找出父结点、左孩子、右孩子中最大的下标
if(lson < n && arr[largest] < arr[lson]){
largest = lson;
}
if(rson < n && arr[largest] < arr[rson]){
largest = rson;
}
if(largest !== i){
// 将最大的值赋值给父节点
[arr[largest],arr[i]] = [arr[i],arr[largest]];
// 因为一个堆被改变了，会影响到子孩子的堆，所以需要进行递归
heapify(arr, n, largest);
}
}
// 堆排序入口
function heap_sort(arr, n){
let i;
// 建堆 [(n/2)-1] ---> [((n-1)-1)/2]，从后往前建堆
for(i = (n / 2) - 1; i >= 0; i--){
heapify(arr, n, i);
}
// 排序 大顶堆堆顶元素与最后一个元素交换
for(i = n - 1; i >= 0; i--){
[arr[i], arr[0]] = [arr[0], arr[i]];
heapify(arr, i, 0);// 维护堆顶的元素
}
return arr;
}
// let arr = [2,3,8,1,4,9,10,7,16,14];
// let n = 10;
// heap_sort(arr, n);
时间复杂度：O(NlogNNlogNNlogN)，其中建堆复杂度为O(NNN)，heapify复杂度为O(logNlogNlogN)
空间复杂度：O(111)
稳定性：稳定
希尔排序
希尔排序是为了加快速度，改进了插入排序，交换不相邻的元素以对数组的局部进行排序。
思路：
先对整个数组进行分组，通常为总长度的一半（奇偶数均可），这里我们将间隔设置为t。
先让数组中任意间隔为t的元素有序，再不断地将t缩小一半，继续做排序，直到t=1为止，当t=1时，数组已经是有序的了。
function shellSort(arr){
let len = arr.length, gap, temp;
// 缩小增量gap
for(gap = len >> 1; gap >= 1; gap>>=1){
for(let i = gap; i < len; i++){
let preIndex = i - gap;// 插入排序是从后往前的，preIndex代表当前元素的上一个元素
if(arr[i] < arr[preIndex]){
temp = arr[i];
while(preIndex >= 0 && arr[preIndex] > temp){
arr[preIndex + gap] = arr[preIndex];
preIndex -= gap;
}
arr[preIndex + gap] = temp;
}
}
}
return arr;
}
// shellSort([8, 9, 1, 7, 2, 3, 5, 4, 6, 0]);
时间复杂度：最坏是O(N2N^2N2)
空间复杂度：O(111)
稳定性：不稳定
计数排序
该排序适合对一定范围内的整数进行排序，空间取决于最大的数字。
思路：
统计每个整数在序列中出现的次数，进而推导出每个整数在有序序列中的索引
获取待排序数组的最大值，最小值，算出差值，如果最小值为负数
创建数组用于统计元素个数
遍历统计数组，按照统计数组中每个元素的个数和顺序将原数组元素加入结果数组
function countingSort(arr, flag = 0){
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);
}
// 计算差值
let s = max - min;
console.log(s)
// 创建数组用于统计元素个数
let count = new Array(s).fill(0);
for(let i = 0; i < len; i++){
let index = arr[i] - min;// 创建下标
count[index] += 1;
}
console.log(count)
// 遍历统计数组，按照统计数组中每个元素的个数和顺序将原数组元素加入结果数组
let res = [];
for(let i = 0; i < s + 1; i++){
if(count[i] === 0) continue;
res.push(arr[arr.indexOf(i + min)]);
--count[i];
}
return flag ? res.reverse() : res;
}
// let arr = [2, 9, 6, 7, 4, 3, 1, 7, 0, -1, -2]
// console.log(countingSort(arr))
时间复杂度：O(N+kN+kN+k)
空间复杂度：O(N+kN+kN+k)
稳定性：稳定
桶排序
当数组中取值范围过大，或者不是整数时，可以使用桶排序来解决，其类似于计数排序创建的统计数组，桶排序需要创建若干个“桶“来协助排序。
思路：
每一个桶代表一个区间范围，里面可以承载一个或多个元素，首先我们要创建这些桶并明确每个桶的区间范围。区间大小 = （最大值 - 最小值）/ 桶的数量
遍历原始数组，把各元素放入各自的桶中
每个桶内的元素分别排序
遍历所有桶，输出所有元素
function bucketSort(arr, size = 10){
let max = Math.max(...arr),
min = Math.min(...arr),
count = Math.floor((max - min) / size) + 1;// 设置区间大小
let buckets = [];
for(let i = 0; i < count; i++){
// 创建桶
buckets.push([]);
}
for(val of arr){
// 把每个元素归类，num表示桶的序号
let num = Math.floor((val - min) / size);
buckets[num].push(val);
}
let result = [];
for(bucket of buckets){
// 排序用任一排序算法都可以，如果数据量不大可以使用插入排序
result.push(...insertSort(bucket));
}
return result;
}
// 插入排序
function insertSort(arr){
for(let i =1; i < arr.length; i++){
let j = i;
let target = arr[j];
while(j > 0 && arr[j - 1] > target){
arr[j] = arr[j - 1];
j--;
}
arr[j] = target;
}
return arr;
}
// let arr = [3,6,3,2,87,23,673,0]
// bucketSort(arr, 5)
桶数量为N时，
时间复杂度：O(NNN)
空间复杂度：O(NNN)
稳定性：稳定
基数排序
思路：
先以个位数的大小来对数据进行排序，接着以十位数的大小来对数据进行排序，接着以百位数的......
在对某位数进行排序时，是用“桶”来排序的，排到最后，就是一组有序的元素。
设置大小范围为0 - 9的10个桶，然后把具有相同的数值的数放进桶
再把桶里的数按照0到9号桶的顺序取出来，重复个位、十位、百位......
最后排序完成
注意：不够位数的数值在前面补0
function radixSort(arr) {
let maxLen = 0;
// 算出最大值的位数
for(let val of arr){
let len = String(val).length;
if(len > maxLen){
maxLen = len;
}
}
// 遍历各个位数并进行排序
for(let i = 1; i |