JavaScript实现十大排序算法（图文详解）

Answer 1

冒泡排序排序的效果图

解法

当前解法为升序

冒泡排序的特点，是一个个数进行处理。第i个数，需要与后续的len-i-1个数进行逐个比较。

为什么是`len-i-1`个数？

因为数组末尾的i个数，已经是排好序的，确认位置不变的了。

为什么确认位置不变，因为它们固定下来之前，已经和前面的数字都一一比较过了。

functionbubbleSort(arr){constlen=arr.length;for(leti=0;i<len-1;i++){for(letj=0;j<len-i-1;j++){if(arr[j]>arr[j+1]){consttmp=arr[j+1];arr[j+1]=arr[j];arr[j]=tmp;}}}returnarr;}

快速排序概要

快速排序，使用的是分治法的思想。通过选定一个数字作为比较值，将要排序其他数字，分为>比较值和<比较值，两个部分。并不断重复这个步骤，直到只剩要排序的数字只有本身，则排序完成。

效果图

解法functionquickSort(arr){sort(arr,0,arr.length-1);returnarr;functionsort(arr,low,high){if(low>=high){return;}leti=low;letj=high;constx=arr[i];//取出比较值x，当前位置i空出，等待填入while(i<j){//从数组尾部，找出比x小的数字while(arr[j]>=x&&i<j){j--;}//将空出的位置，填入当前值，下标j位置空出//ps：比较值已经缓存在变量x中if(i<j){arr[i]=arr[j]i++;}//从数组头部，找出比x大的数字while(arr[i]<=x&&i<j){i++;}//将数字填入下标j中，下标i位置突出if(i<j){arr[j]=arr[i]j--;}//一直循环到左右指针i、j相遇，//相遇时，i==j,所以下标i位置是空出的}arr[i]=x;//将空出的位置，填入缓存的数字x，一轮排序完成//分别对剩下的两个区间进行递归排序sort(arr,low,i-1);sort(arr,i+1,high);}}

希尔排序概要

希尔排序是一种插入排序的算法，它是对简单的插入排序进行改进后，更高效的版本。由希尔（DonaldShell）于1959年提出。特点是利用增量，将数组分成一组组子序列，然后对子序列进行插入排序。由于增量是从大到小，逐次递减，所以也称为缩小增量排序。

效果图

解法

注意点插入排序时，并不是一个分组内的数字一次性用插入排序完成，而是每个分组交叉进行。

执行插入时，使用交换法functionshellSort(arr){//分组规则gap/2递减for(letgap=Math.floor(arr.length/2);gap>0;gap=Math.floor(gap/2)){for(leti=gap;i<arr.length;i++){letj=i;//分组内数字，执行插入排序，//当下标大的数字，小于下标小的数字，进行交互//这里注意，分组内的数字，并不是一次性比较完，需要i逐步递增，囊括下个分组内数字while(j-gap>=0&&arr[j]<arr[j-gap]){swap(j,j-gap);j=j-gap;}}}returnarr;functionswap(a,b){consttmp=arr[a];arr[a]=arr[b];arr[b]=tmp;}}

执行插入时，使用移动法functionshellSort(arr){for(letgap=Math.floor(arr.length/2);gap>0;gap=Math.floor(gap/2)){for(leti=gap;i<arr.length;i++){letj=i;constx=arr[j];//缓存数字，空出位置while(j-gap>=0&&x<arr[j-gap]){arr[j]=arr[j-gap];//将符合条件的数字，填入空出的位置j=j-gap;}arr[j]=x;//最后，将缓存的数字，填入空出的位置}}returnarr;}

选择排序排序的效果图

解法

当前解法为升序

functionselectionSort(arr){constlen=arr.length;for(leti=0;i<len-1;i++){letminIndex=i;for(letj=i+1;j<len;j++){if(arr[j]<arr[minIndex]){minIndex=j;//保存最小数的下标}}consttmp=arr[i];arr[i]=arr[minIndex];arr[minIndex]=tmp;}returnarr;}

归并排序概要

归并排序，利用分治思想，将大的数组，分解为小数组，直至单个元素。然后，使用选择排序的方式，对分拆的小数组，进行回溯，并有序合并，直至合并为一个大的数组。

效果图

小数组合并的过程

解法functionmergeSort(arr){returnsort(arr,0,arr.length-1);//注意右区间是arr.length-1//sort方法，进行递归functionsort(arr,left,right){//当left!==right时，证明还没分拆到最小元素if(left<right){//取中间值，分拆为两个小的数组constmid=Math.floor((left+right)/2);constleftArr=sort(arr,left,mid);constrightArr=sort(arr,mid+1,right);//递归合并returnmerge(leftArr,rightArr)}//left==right,已经是最小元素，直接返回即可returnleft>=0?[arr[left]]:[];}//合并两个有序数组functionmerge(leftArr,rightArr){letleft=0;letright=0;consttmp=[];//使用双指针，对两个数组进行扫描while(left<leftArr.length&&right<rightArr.length){if(leftArr[left]<=rightArr[right]){tmp.push(leftArr[left++]);}else{tmp.push(rightArr[right++]);}}//合并剩下的内容if(left<leftArr.length){while(left<leftArr.length){tmp.push(leftArr[left++]);}}if(right<rightArr.length){while(right<rightArr.length){tmp.push(rightArr[right++]);}}returntmp;}}

插入排序排序的效果图

解法

当前解法为升序

functioninsertionSort(arr){constlen=arr.length;//注意，i从1开始for(leti=1;i<len;i++){letpreIndex=i-1;letcurrent=arr[i];//位置i之前，是已排好序的数字，while的作用是找到一个坑位，给当前数字current插入while(preIndex>=0&&arr[preIndex]>current){arr[preIndex+1]=arr[preIndex];//对大于current的值，往后移一位，给current的插入腾出位置preIndex--;}arr[preIndex+1]=current;}returnarr;}

堆排序概要

堆的表示形式

逻辑结构的表示如下：

在物理数据层的表示如下：

堆排序，是选择排序的优化版本，利用数据结构——树，对数据进行管理。

以大顶堆为例:

通过构建大顶堆

将堆顶的最大数拿出，与堆底的叶子节点进行交换

接着，树剪掉最大数的叶子

再对堆进行调整，重新变成大顶堆

返回步骤2，以此循环，直至取出所有数

效果图

在实现代码时，构建大顶堆时，先保证左右子树的有序，再逐步扩大到整棵树。

构建大顶堆

从第一个非叶子节点开始，调整它所在的子树

调整下标1节点的子树后，向上继续调整它的父节点（下标0）所在的子树

最后，完成整个树的调整，构建好大顶堆。

逐个抽出堆顶最大值

堆顶数字与最末尾的叶子数字交换，抽出堆顶数字9。

此时，数字9位置固定下来，树剪掉9所在的叶子。然后，重新构建大顶堆。

大顶堆构建好后，继续抽出堆顶数字8，然后再次重新构建大顶堆。

最后，所有节点抽出完成，代表排序已完成。

解法

以大顶堆为例，对数组进行升序排序

注意点树的最后一个非叶子节点：(arr.length/2)-1非叶子节点i的左叶子节点：i*2+1非叶子节点i的右叶子节点：i*2+2???

functionheapSort(arr){//初次构建大顶堆for(leti=Math.floor(arr.length/2)-1;i>=0;i--){//开始的第一个节点是树的最后一个非叶子节点//从构建子树开始，逐步调整buildHeap(arr,i,arr.length);}//逐个抽出堆顶最大值for(letj=arr.length-1;j>0;j--){swap(arr,0,j);//抽出堆顶（下标0）的值，与最后的叶子节点进行交换//重新构建大顶堆//由于上一步的堆顶最大值已经交换到数组的末尾，所以，它的位置固定下来//剩下要比较的数组，长度是j,所以这里的值length==jbuildHeap(arr,0,j);}returnarr;//构建大顶堆functionbuildHeap(arr,i,length){lettmp=arr[i];for(letk=2*i+1;k<length;k=2*k+1){//先判断左右叶子节点，哪个比较大if(k+1<length&&arr[k+1]>arr[k]){k++;}//将最大的叶子节点，与当前的值进行比较if(arr[k]>tmp){//k节点大于i节点的值，需要交换arr[i]=arr[k];//将k节点的值与i节点的值交换i=k;//注意：交换后，当前值tmp的下标是k，所以需要更新}else{//如果tmp大于左右子节点，则它们的子树也不用判断，都是小于当前值break;}}//i是交换后的下标，更新为tmparr[i]=tmp;}//交换值functionswap(arr,i,j){consttmp=arr[i];arr[i]=arr[j];arr[j]=tmp;}}

计数排序概要

计数排序的要点，是开辟一块连续格子组成的空间，给数据进行存储。将数组中的数字，依次读取，存入其值对应的下标中。储存完成后，再按照空间的顺序，依次读取每个格子的数据，输出即可。

所以，计数排序要求排序的数据，必须是有范围的整数。

效果图

解法functioncountingSort(arr){letmaxValue=Number.MIN_VALUE;letminValue=Number.MAX_VALUE;letoffset=0;//位移，用于处理负数constresult=[];//取出数组的最大值,最小值arr.forEach(num=>{maxValue=num>maxValue?num:maxValue;minValue=num>minValue?minValue:num;});if(minValue<0){offset=-minValue;}constbucket=newArray(maxValue+offset+1).fill(0);//初始化连续的格子//将数组中的每个数字，根据值放入对应的下标中，//`bucket[num]==n`格子的意义：存在n个数字，值为numarr.forEach(num=>{bucket[num+offset]++;});//读取格子中的数bucket.forEach((store,index)=>{while(store--){result.push(index-offset);}});returnresult;}

桶排序概要

桶排序是计数排序的优化版，原理都是一样的：分治法+空间换时间。将数组进行分组，减少排序的数量，再对子数组进行排序，最后合并即可得到结果。

效果图

解法

对桶内数字的排序，本文采用的是桶排序递归。其实它的本质是退化到计数排序。

functionbucketSort(arr,bucketSize=10){//bucketSize每个桶可以存放的数字区间(0,9]if(arr.length<=1){returnarr;}letmaxValue=arr[0];letminValue=arr[0];letresult=[];//取出数组的最大值,最小值arr.forEach(num=>{maxValue=num>maxValue?num:maxValue;minValue=num>minValue?minValue:num;});//初始化桶的数量constbucketCount=Math.floor((maxValue-minValue)/bucketSize)+1;//桶的数量//初始化桶的容器//注意这里的js语法，不能直接fill([])，因为生成的二维下标数组，是同一个地址constbuckets=newArray(bucketCount).fill(0).map(()=>[]);//将数字按照映射的规则，放入桶中arr.forEach(num=>{constbucketIndex=Math.floor((num-minValue)/bucketSize);buckets[bucketIndex].push(num);});//遍历每个桶内存储的数字buckets.forEach(store=>{//桶内只有1个数字或者空桶，或者都是重复数字，则直接合并到结果中if(store.length<=1||bucketSize==1){result=result.concat(store);return;}//递归，将桶内的数字，再进行一次划分到不同的桶中constsubSize=Math.floor(bucketSize/2);//减少桶内的数字区间，但必须是最少为1consttmp=bucketSort(store,subSize<=1?1:subSize);result=result.concat(tmp);});returnresult;}

基数排序概述

基数排序，一般是从右到左，对进制位上的数字进行比较，存入[0,9]的10个桶中，进行排序。从低位开始比较，逐位进行比较，让每个进制位（个、十、百、千、万）上的数字，都能放入对应的桶中，形成局部有序。

为什么10个桶？

因为十进制数，是由0-9数字组成，对应的进制位上的数字，都会落在这个区间内，所以是10个桶。

基数排序有两种方式：

MSD从高位开始进行排序

LSD从低位开始进行排序

效果图

解法

当前解法，只适用正整数的场景。负数场景，需要加上偏移量解决。可参考计数排序的解法。

functionquickSort(arr){sort(arr,0,arr.length-1);returnarr;functionsort(arr,low,high){if(low>=high){return;}leti=low;letj=high;constx=arr[i];//取出比较值x，当前位置i空出，等待填入while(i<j){//从数组尾部，找出比x小的数字while(arr[j]>=x&&i<j){j--;}//将空出的位置，填入当前值，下标j位置空出//ps：比较值已经缓存在变量x中if(i<j){arr[i]=arr[j]i++;}//从数组头部，找出比x大的数字while(arr[i]<=x&&i<j){i++;}//将数字填入下标j中，下标i位置突出if(i<j){arr[j]=arr[i]j--;}//一直循环到左右指针i、j相遇，//相遇时，i==j,所以下标i位置是空出的}arr[i]=x;//将空出的位置，填入缓存的数字x，一轮排序完成//分别对剩下的两个区间进行递归排序sort(arr,low,i-1);sort(arr,i+1,high);}}0

算法复杂度

扩展阅读

笔者整理的面试笔试题

参考

JAVA十大排序算法之桶排序详解

JAVA十大排序算法之基数排序详解

图解排序算法(三)之堆排序

图解排序算法(四)之归并排序

快速排序QuickSort

图解排序算法(二)之希尔排序

最近笔者在整理第一本电子书书稿《前端面试手册》，有兴趣的同学可以关注下～

喜欢我文章的朋友，可以通过以下方式关注我：

「star」或「watch」我的GitHubblog

RSS订阅我的个人博客：王先生的基地

原文：https://juejin.cn/post/7099436855388536869