js解析常见排序算法

~ 冒泡排序基本思想

相信大家也看过在水中的冒泡现象，从下至上，气泡会越来越大，而所谓冒泡排序，也是建立在这个原理上，即从下至上按照一定的顺序，进行排列。

相邻的元素，依次进行对比，如果第一个元素大于第二个元素，那么交换位置。而经过一轮比较之后，最大的元素就会“冒泡”到队尾，之后对已经排好序的元素不予理会，对未排序的元素继续这个步骤，在第n-1（n为数组元素个数）轮之后，完成排序。

代码实现functionbubbleSort(nums){for(leti=0;i<nums.length-1;i++){for(letj=0;j<nums.length-1-i;j++){if(nums[j]>nums[j+1]){lettemp=nums[j]nums[j]=nums[j+1]nums[j+1]=temp}}}returnnums}

复杂度

冒泡排序是一种稳定的排序方法，其平均时间复杂度为O(n^2),最好情况的时间复杂度为O(n),最坏情况的时间复杂度为O(n^2)，在排序过程当中只需要一个元素的辅助空间，也就是temp，所以空间复杂度为O(1)

例题分析letnums=[3,6,4,2,11,10,5]

第一轮排序：3与6比较之后，不交换，6和4交换位置，之后6再次与2比较，仍然需要进行位置交换，然后继续类似的操作，11就到了末尾，排序之后数组为【3,4,2,6,10,5,11】

第二轮排序：3与4比较不进行位置交换，这个时候我们从上帝视角发现，10为最大元素，那么这个时候10会一直冒泡到11的前一位元素上。结果为【3,2,4,6,5,10,11】

后续操作类似，直到四轮排序结束后，数组变为有序数组

图例如下：

选择排序基本思想

选择排序算法，顾名思义，选择两个字至关重要，首先元素之间进行对比，使用min来记录当前最小元素的下标索引，与首元素交换，也就是排列在数组的起始位置，之后在剩下未排序的数组元素当中又通过这种方式选择出一个最小的元素，在经过n-1轮排序后，数组变为有序数组。

代码实现functionselectionSort(nums){for(leti=0;i<nums.length-1;i++){letmin=ifor(letj=i+1;j<nums.length;j++){if(nums[j]<nums[min])min=j//保存最小值的下标索引}lettemp=nums[i]nums[i]=nums[min]nums[min]=temp}returnnums}

复杂度

选择排序是一种不稳定的排序方法，其平均时间复杂度为O(n^2),最好最坏的情况时间复杂度都为O(n^2)，在排序过程当中只需要一个元素的辅助空间，所以空间复杂度为O(1)

例题分析letnums=[7,4,5,9,8,2,1]

第一轮排序：第一个元素与其余元素进行比较，找出最小值的下标索引，保存第一个元素的下标为min，之后分别与各个元素进行比较，此时1为最小值，保存min，然后与元素7进行交换，排序完之后为【1,4,5,9,8,2,7】

第二轮排序：元素4与其余未排序元素进行比较，最后与2交换位置，排序之后，数组为【1,2,5,9,8,4,7】

之后依次按照这个方法寻找未排序的最小元素，4轮之后最终变为有序数组

插入排序基本思想

在插入第i个记录时候，R0至R1是有序的，那么将nums[i]与这些元素进行比较，找到应该插入的位置，在插入的位置之后的元素都需要依次向后移动

默认第一个元素是存在顺序的，那么从第二个元素开始，需要依次进行比较，将该元素从后往前开始比较，如果比当前元素大，那么将该元素后移，直到找到一个比该元素更小的元素，然后将该元素放在当前元素后面。如此反复，即可排序成功

代码实现functioninsertionSort(nums){for(leti=1;i<nums.length;i++){for(letj=i;j>0;j--){if(nums[j]<nums[j-1]){lettemp=nums[j];nums[j]=nums[j-1];nums[j-1]=nums;}}}returnnums;}

这么一瞅，是不是有点像冒泡排序

还有第二种，但是第二层循环我用了var关键字来声明，因为let块级作用域的原因，nums[j+1]=temp这一行代码会访问不到变量j，所以我用var来声明，但是无伤大雅，这里也可以用while循环来做的，网友们可自行琢磨

functioncharu(nums){for(leti=1;i<nums.length;i++){if(nums[i]<nums[i-1]){lettemp=nums[i]//保存nums[i]nums[i]=nums[i-1]for(varj=i-1;j>=0&&nums[j]>temp;j--)nums[j+1]=nums[j]nums[j+1]=temp}}returnnums;}

复杂度

插入排序是一种稳定的排序方法，其平均时间复杂度为O(n^2),最好情况的时间复杂度为O(n),最坏情况的时间复杂度为O(n^2)，在排序过程当中只需要一个元素的辅助空间，所以空间复杂度为O(1)

例题分析letnums=[5,7,4,6,3,1,2,9,8]

默认第一个元素5是有序的，那么从第二个元素开始，5会先与7比较，此时按兵不动，而后比较4会插入5的前面，依次类推，就可以得到有序数组

希尔排序基本思想

希尔排序又被称为“缩小增量排序”，这是对插入排序算法的改进

首先将整个待排序序列分为若干子序列，然后分别进行直接插入排序，待整个序列中的记录基本有序时，再对全体序列进行一次插入排序

先取一个小于n的整数d1作为第一个增量，将数组分为d1个组，即所有距离为d1倍数序号的记录放在同一个组当中，在各组当中进行插入排序。

然后取d2(d2<d1)重复上述分组和排序工作

直到所取的增量为di=1，所有记录都在同一组然后进行插入序列为止一般取的都是d1=n/2?d2=2/d1,依次类推

代码实现functionshellSort(nums){lethalf=parseInt(nums.length/2);//设置增量为原数组长度的一半for(letgap=half;gap>=1;gap=parseInt(gap/2)){for(leti=gap;i<nums.length;i++){for(letj=i-gap;j>=0;j=j-gap){if(nums[j]>nums[j+gap]){lettemp=nums[j];nums[j]=nums[j+gap];nums[j+gap]=temp;}}}}returnnums}

复杂度

希尔排序也是一种不稳定的排序方法，其平均时间复杂度约为O(nlogn^2),约为O(n^1.3),最好情况的时间复杂度为O(n),最坏情况的时间复杂度为O(n^2),在排序过程当中只需要一个元素的辅助空间，所以空间复杂度为O(1)

例题分析

因为这里数量太少不利于讲解，我换个例子

letnums=[9,1,2,5,7,4,8,6,3,5]

我们就取d1=5(n/2)、d2=3(d1/2)、d3=2(d2/2),d4=1来作为排序的增量,依据情况而定上下取整

第一轮排序：按照d1=5，进行分组，那么9和4为一组，1和28，2和6，5和3，7和5两两配对，那么此时就需要比较元素之间的大小，各组之间进行插入排序，那么第一轮排序后，数组为【4,1,2,3,5,9,8,6,5,7】

第二轮排序：按照d2=3,进行分组，那么4、3、8、7为一组，1、5、6以及2、9、5各成一组，插入排序后，数组为【3,1,2,4,5,5,7,6,9,8】

第三轮排序：按照d3=2,j进行分组，也就是相邻元素不为一组，3,2,5,7,9为一组，1,4,5,6,8为一组，那么两组内部进行插入排序后，数组为【2,1,3,4,5,5,7,6,9,8】

第四轮排序：直接取d4=1，全部序列进行插入排序，得到最后的结果【1,2,3,4,5,5,6,7,8,9】

其实实际当中不用四轮，三轮即可，只要向下取整就好。

快速排序基本思想

通过一趟排序将待排序的元素划分为独立的两个部分，称为前半区和后半区，其中前半区的元素都不大于后半区元素，然后再分别对这两部分进行快速排序，从而使整个序列有序

附设两个指针变量i和j，分别指向序列第一个元素和最后一个元素，设第一个关键字为pivot，从j的位置向前检索找到第一个小于pivot的元素，将该元素向前移动到i指示的位置，从i所指的位置向后搜索，找到第一个大于pivot的元素将该元素移动到j所指的位置，重复过程直到i、j相遇

代码实现functionPartition(nums,low,high){vari=low,j=high,pivot=nums[i];while(i<j){//从右往左找while(i<j&&nums[j]>pivot)j--;if(i<j){swap(i++,j,nums);}//从左往右找while(i<j&&nums[i]<=pivot)i++;if(i<j){swap(i,j--,nums);}}returni;//返回基准元素位置}functionswap(a,b,nums){console.log(a,b,nums[a],nums[b])vartemp=nums[a];nums[a]=nums[b];nums[b]=temp;}functionQuickSort(nums,low,high){varmid;if(low<high){mid=Partition(nums,low,high);//返回基准元素位置QuickSort(nums,low,mid-1);//左边快速排序QuickSort(nums,mid+1,high);//右边快速排序}}QuickSort(nums,0,nums.length-1);

复杂度

快速排序是一种不稳定的排序方法，其平均时间复杂度为O(nlog2n),最好情况的时间复杂度为O(nlog2n),最坏情况的时间复杂度为O(n^2)，空间复杂度为O(nlog2n)

例题分析

我从网上找了个例子，相信大家更容易看懂，哈哈哈

重点就是对双指针解法的理解程度，需要在j指针找到比i指针更小的元素，进行替换

归并排序基本思想

归并其实利用的是一个递归的思想，将长度为n的整个数组看成是n个长度为1的多个数组，对这些数组进行两两归并，得到n/2个长度为2或者1的有序数组，之后再两两归并，重复这个步骤，直到所有的元素都形成长度为n的数组。

大致步骤如下：

把n个记录看成n个长度为l的有序子表

进行两两归并使记录关键字有序，得到n/2个长度为2的有序子表

重复第2步直到所有记录归并成一个长度为n的有序表为止。

具体操作为不断切割数组，类似于对半切，不断的在中间元素切割，使得各个数组一分为二，最终变为n个长度为1的数组，之后再两两合并这些元素，形成一个有序链表。

代码实现letnums=[3,6,4,2,11,10,5]0

复杂度

归并排序是一种稳定的排序方法，其平均时间复杂度为O(n^2),最好情况的时间复杂度为O(nlog2n),最坏情况的时间复杂度为O(nlog2n)，在排序过程当中只需要n个元素的辅助空间，所以空间复杂度为O(nlogn)

例题分析

大致步骤如下：

堆排序基本思想

若将序列对应的一维数组看成是一个完全二叉数?，完全二叉树中所有非终端节点的值均不小于（或者不大于）其左右孩子节点的值，因此在一个堆中，堆顶元素，即完全二叉树的根节点必然为序列中的最大元素或者是最小元素，并且堆中的任一一棵子树也都是堆，若堆顶为最小元素，则称为小根堆落；堆顶为最大元素，则称为大根堆。

对一组待排序记录的元素首先按堆的定义排成一个序列，即建立初始堆，从而可以输出堆顶的最大元素(对于大根堆而言),?然后将剩余的元素再调整成新堆,便得到次大的元素，如此反复，直到全部元素排成有序序列为止?

写代码前，需要知道这些基本知识

Parent(i)=floor((i-1)/2)，i的父节点下标

Left(i)=2i+1，i的左子节点下标

Right(i)=2(i+1)，i的右子节点下标

代码实现letnums=[3,6,4,2,11,10,5]1

复杂度

堆排序是一种不稳定的排序方法，其平均时间复杂度为O(nlog2n),最好情况的时间复杂度为O(nlog2n),最坏情况的时间复杂度为O(nlog2n)，在排序过程当中只需要一个元素的辅助空间，所以空间复杂度为O(1)

例题分析

这里我也是偷个懒，我感觉说的可能不明白，让读者们看图说话吧！

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

---

js解析常见排序算法视频