随时记|几种常见的排序方法_JavaScript

常见的排序算法有：冒泡排序、选择排序、插入排序、归并排序、快速排序、希尔排序、堆排序、计数排序、桶排序、基数排序

冒泡排序

冒泡排序：遍历要排序的数组，一次比较两个元素，如果这两个元素的顺序错误就把他们交换过来，直到没有再需要交换为止
算法思路：

1. 比较相邻元素，如果顺序错误，就交换
2. 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数
3. 针对所有的元素重复以上的步骤，除了最后一个
4. 重复1-3步，最终排序完成 代码实现：

let arr =[1,3,4,5,7,8];functionbubbleSort(arr){let temp;for(let i =0; i < arr.length -1; i++){// 外层for循环用于确定对比的轮数，并且保证不会重复对比，因为每一轮下来，最后一个元素都是最大的for(let j=0; j < arr.length -1-i; j++){// 内层for循环用于确定两两对比的组数，每一次循环都要不断缩小目标if(arr[j]> arr[j+1]){// 以8 和 1为例// temp = arr[j];    // 把8存起来// arr[j] = arr[j+1];  // 把1放到原来8的位置// arr[j+1] = temp;  // 把8放到原来1的位置[arr[j], arr[j+1]]=[[arr[j+1],arr[j]]}}};return arr;};

console.log(bubbleSort(arr));// [ 1, 3, 4, 5, 7, 8 ]

选择排序

选择排序：类似于冒泡排序的改进
算法思路：

1. 在未排序的数组中找到最小（大）元素，存放到排序序列的起始位置
2. 在剩余未排序元素中继续寻找最小（大）元素，然后放到已知排序序列的末尾
3. 重复步骤2，直到所有元素均排序完毕

代码实现：

let arr =[3,5,8,1,4,7];functionselectSort(arr){for(let i =0; i < arr.length; i++){let minIndex = i;for(let j=i+1; j < arr.length; j++){if(arr[minIndex]> arr[j]){
                minIndex = j;};};[arr[i], arr[minIndex]]=[arr[minIndex], arr[i]];};return arr;}

console.log(selectSort(arr))// [ 1, 3, 4, 5, 7, 8 ]

插入排序

通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入
算法思路：

1. 把数组分为已排序和未排序两部分，初始的时候把第一个元素认为是已排好序的
2. 从第二个元素开始，在已排好序的子数组中寻找到该元素适合的位置并插入该位置
3. 重复上述步骤

let arr =[3,5,8,1,4,7];functioninsertSort(arr){for(let i =1; i < arr.length; i++){let temp = arr[i];let j=i-1;while(j>=0&& temp < arr[j]){
            arr[j+1]= arr[j];
            j--;};
        arr[j+1]= temp;};return arr;}

console.log(insertSort(arr))// [ 1, 3, 4, 5, 7, 8 ]

归并排序

建立在归并操作上的一种有效的排序算法。该算法是采用分治法的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并

假设有这样一个数组：【33， 27， 56， 88， 67， 43， 20， 45】
第一步：拆分数组，一共需要拆分3次（logN）

• 第一次拆分：【33，27，56，88】 【67，43，20，45】
• 第二次拆分：【33，27】【56，88】【67，43】【20，45】
• 第三次拆分：【33】【27】【56】【88】【67】【43】【20】【45】

第二步：逐步归并数组，采用合并两个有序数组的方法，每一步其算法复杂度基本接近于O(N)

• 第一次归并：【27，33】【56，88】【43，67】【20，45】
• 第二次归并：【27，33，56，88】【20，43，45，67】
• 第三次归并：【20，27，33，43，45，56，67，88】

算法思路：

• 递归法（Top-down）

1. 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
2. 设定两个指针，最初位置分别为两个已经排序序列的起始位置
3. 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
4. 重复步骤3直到某一指针到达序列尾
5. 将另一序列剩下的所有元素直接复制到合并序列尾

• 迭代法（Bottom-up） 原理如下（假设序列共有n个元素）： 将序列每相邻两个数字进行归并操作，形成ceil(n/2)个序列，排序后每个序列包含两/一个元素 若此时序列数不是1个则将上述序列再次归并，形成ceil(n/4)个序列，每个序列包含四/三个元素 重复步骤2，直到所有元素排序完毕，即序列数为1

let arr =[3,5,8,1,4,7];functionmergeSort(arr){const n = arr.length;if(n<=1)return arr;const midIndex = Math.floor(n/2);const left =mergeSort(arr.slice(0,midIndex));const right =mergeSort(arr.slice(midIndex, n));returnmerge(left, right);}functionmerge(a, b){const n1 = a.length, n2 = b.length;let l=0, r=0, res =[];while(l<n1 && r<n2){
        res.push(a[l]< b[r]? a[l++]: b[r++]);};return[...res,...(l===n1? b.slice(r): a.slice(l))]}

console.log(mergeSort(arr))// [ 1, 3, 4, 5, 7, 8 ]

快速排序

算法描述

1. 从数列中挑出一个元素，称为"基准"（pivot）【一般找中间项】
2. 把"基准"从原来数组中移除，并返回这一项的结果
3. 依次遍历数组中剩余的元素，和"基准"进行比较，小的放左边，大的放右边
4. 这时，我们得到了左边【比1中基准小的】和右边【比1中基准大的】
5. 重复上述操作
6. 最终返回结果为：左+基准+右

let arr =[3,5,8,1,4,7];functionquickSort(arr){if(arr.length <=1)return arr;const mid = Math.floor(arr.length/2);let midValue = arr.splice(mid,1)[0];let left =[];let right =[];for(let i=0; i<arr.length;i++){let item = arr[i];
        item < midValue ? left.push(item): right.push(item);};returnquickSort(left).concat(midValue,quickSort(right));}

console.log(quickSort(arr))// [ 1, 3, 4, 5, 7, 8 ]

参考：[算法总结] 十大排序算法