几种常见的排序算法及JavaScript实现

~ 前言

在学习数据结构和排序算法过程中，会发现原理和思路都十分简洁和清晰，难度在于用如何用代码将过程表达出来，而这就是程序员内功的修炼了。

在学习过程中非常喜欢一句话：“好的算法就是一本好的食谱，只要按照食谱的步骤进行，小白也能做出美味的烹饪，而学习前人的经典算法，即使没有多高的天分，也能帮助你解决很多问题。”

1.选择排序

选择排序是最容易理解的一种排序算法。

1.1算法原理

遍历数据，把数据中的最大值（或者最小值）与起始（或者末尾）数据进行交换。

1.2算法思路

1.从“待排序数据”中找到最小值。

2.把最小值和“待排序数据起止位置的元素”交换。

3.“待排序数据”的起始位置向后移动一位。

4.循环操作1~3，直至“待排序部分”只剩下一个元素。

下图展示了用选择排序算法的过程。

1.3代码实现let?selectSort?=?(array)?=>?{??for?(let?i?=?0;?i?<?array.length-1;?i++)?{????let?min?=?array[i];//先找到起始值????for(let?j?=?i+1;j<?array.length;j++){??????if(min>?array[j]){//再次循环找到最小值????????let?temp?=?min;//使用临时变量交换最小值和起始值????????min?=?array[j];????????array[j]?=?temp;??????}????}????array[i]?=?min//将最小值放到数组最前面????}??return?array;}let?testArray?=?[35,80,21,54,11,45,92,39];console.log(selectSort(testArray));

测试结果：

1.4算法效率

选择排序的简单和直观名副其实，这也造就了它出了名的慢性子，无论是哪种情况，哪怕原数组已排序完成，它也将花费将近n?/2次遍历来确认一遍。唯一值得高兴的是，它并不耗费额外的内存空间。

平均时间复杂度最好情况最坏情况空间复杂度O(n2)O(n2)O(n2)O(1)2.冒泡排序2.1算法原理

比较相邻的两个元素的大小关系，如果大小关系和排序顺序是相反的，则交换这两个元素的位置。

2.2算法思路

1.“待排序数据”的第1个数据和第2个数据相互比较。

2.如果第1个数据>第2个数据，那么交换两个数据的位置。

3.进行比较的数据位置向后移动一位。

4.直到比较到最后2个数据，那么末尾的数据就是最大值。

5.在“待排序数据”里面除去末尾的最大值，在新的“待排序数据”继续上述操作。

下图展示了进行冒泡排序的过程：

2.3代码实现let?bubbleSort?=?(array)?=>?{??for?(let?i?=?0;?i?<array.length-1?;?i++)?{//最后一个数字不用遍历?????for?(let?j?=?0;?j?<?array.length-1-i;?j++)?{//每次比较，都要去除末尾已经排好序的值，所以要-i????????if?(array[j]>array[j+1]){//找到较小值，交换位置??????????let?temp?=?array[j];??????????array[j]?=?array[j+1];??????????array[j+1]?=?temp;????????}????}??}??return?array;}let?testArray?=?[35,80,21,54,11,45,92,39];console.log(bubbleSort(testArray));

测试结果：

2.4算法效率

冒泡排序是稳定的排序算法，最容易实现的排序,最坏的情况是每次都需要交换,共需遍历并交换将近n?/2次,时间复杂度为O(n?).最佳的情况是内循环遍历一次后发现排序是对的,因此退出循环,时间复杂度为O(n).平均来讲,时间复杂度为O(n?).由于冒泡排序中只有缓存的temp变量需要内存空间,因此空间复杂度为常量O(1)平均时间复杂度|最好情况|最坏情况?|空间复杂度||-------|----|-----|-----||O(n2)?|O(n)|O(n2)|O(1)

3.插入排序3.1算法原理

假设一组数据列（D0,D1,D2...,Dn）中的某个数据Di之前的数据列(D0~Di-1)是已经排好序的，那么把Di按照大小关系插入到已经排好序的数据列中，按此方法一直操作到最后一个数据，就可以完成排序。

3.2算法思路

在开始处理之前，可以认为“已排序部分”只包括数组的起始元素，而“待排序部分”包含第二个元素及其以后的所有元素。排序过程如下：

1.第一个元素被认为已经排好序

2.找到下一个元素，与前面已排序的元素进行对比

3.如果已排序的元素大于待排序元素，将已排序元素后移

4.重复步骤3，直到找到已排序元素小于或者等于待排序元素的位置

5.把待排序元素插入到该位置

6.重复步骤2到5直到最后一个元素。

3.3实现代码let??insertSort?=?(array)?=>?{??for?(let?i?=?1;?i?<?array.length;?i++)?{//从第二个元素开始循环????let?temp?=?array[i];//把待排序的元素放在临时变量里，因为后移操作会覆盖掉待排序元素????let?j?=?i-1;//往前找已经排好序的元素????while(j>=0?&&?array[j]?>?temp){//j<0，会导致找不到数组元素??????array[j+1]?=?array[j];//如果排好序的元素存在比待排序的元素大，就后移??????j--;????}????array[j+1]?=?temp;//把待排序的元素值赋值回来??}??return?array;}let?testArray?=?[35,80,21,54,11,45,92,39];console.log(insertSort(testArray));

测试结果：

3.4算法效率

是稳定的排序算法。平均时间复杂度|最好情况|最坏情况?|空间复杂度||-------|----|-----|-----||O(n2)?|O(n)|O(n2)|O(1)

4.归并排序4.1算法原理

所谓归并，指的是把“几个已排序的数据列”合并成“一个已排序的数据列”，即把待排序列分为若干个子序列，每个子序列都是有序的，然后再把子序列合并成整体有序序列。

4.2算法思路

采用递归法：

1.将序列每相邻两个数字进行归并操作，形成floor(n/2)个序列，排序后每个序列包含两个元素

2.将上述序列再次归并，形成floor(n/4)个序列，每个序列包含四个元素

3.重复步骤2，直到所有元素归并完毕

4.进行合并操作，对每个排好的数据列做对比，找到最小值，放到容器中。

5.找到最小值后，原数组的下一个数据就会称为起始值。

下图是对3个数据列进行归并排序的展示，可以看到每次数据列取值之后，下一个数据就会变为起始元素。

4.3代码实现let?merge?=?(a,b)?=>?{//合并函数??if?(a.length?===?0)?return?b??if?(b.length?===?0)?return?a??return?a[0]?>?b[0]??//每次取值，找到数组中的最小值????[b[0]].concat(merge(a,?b.slice(1)))?://取值后，把数组第二个数据设置为起始值????[a[0]].concat(merge(a.slice(1),?b))}let?mergeSort?=?(array)?=>?{??let?n?=?array.length;??if(n?===?1){return?array}??let?left?=?array.slice(0,Math.floor(n/2));//将数组分割，直到长度为1??let?right?=?array.slice(Math.floor(n/2));??return?merge(mergeSort(left),mergeSort(right))}let?testArray?=?[35,80,21,54,11,45,92,39];console.log(mergeSort(testArray));

测试结果：

4.4算法效率

稳定排序算法，从效率上看，归并排序可算是排序算法中的”佼佼者”.假设数组长度为n，那么拆分数组共需logn,又每步都是一个普通的合并子数组的过程，时间复杂度为O(n)，故其综合时间复杂度为O(nlogn)。另一方面，归并排序多次递归过程中拆分的子数组需要保存在内存空间，其空间复杂度为O(n)。和选择排序一样，归并排序的性能不受输入数据的影响，但表现比选择排序好的多，因为始终都是O(nlogn）的时间复杂度。代价是需要额外的内存空间。

平均时间复杂度最好情况最坏情况空间复杂度O(nlogn)O(nlogn)O(nlogn)O(n)5.快速排序5.1算法原理

通过一次排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以达到整个数据变成有序序列。

5.2算法思路

快速排序使用分治策略来把一个序列（list）分为两个子序列（sub-lists）。步骤为：1.从数列中挑出一个元素，称为“基准”(pivot)。

2.重新排序数列，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面（相同数可以到任一边）。在这个分区结束之后，该基准就处于数列的中间位置。

3.递归地（recursively）把小于基准值元素的子数列和大于基准值元素的子数列排序。

下图展示了用初始元素作为基准值进行快速排序：

5.3代码实现let?quickSort?=?(array)?=>?{??if?(array.length?<=1){return?array;}??let?pivotIndex?=?Math.floor(array.length/2);//使用数列中间的元素作为基准??let?pivot?=?array.splice(pivotIndex,1)[0];??let?left?=?[];??let?right?=?[];??for?(let?i?=?0;?i?<?array.length;?i++)?{????if?(array[i]?<?pivot){//比基准值小的放在前面，大的或者等于的放在后面??????left.push(array[i])????}else?{right.push(array[i])}??}??return?quickSort(left).concat([pivot],quickSort(right))//递归子数组}let?testArray?=?[35,80,21,54,11,45,92,39];console.log(quickSort(testArray));

测试结果：

5.4算法效率

快速排序并不稳定，快速排序每次交换的元素都有可能不是相邻的,因此它有可能打破原来值为相同的元素之间的顺序。

平均时间复杂度最好情况最坏情况空间复杂度O(nlogn)O(nlogn)O(n2)O(1)6.希尔排序6.1算法原理

把数据按照一定间隔分割成不同的组，并且对每个组进行插入排序。

6.2算法思路

1.把分组间隔gap初始化为N/2(商的整数部分)

2.当gap当于1的时候，循环执行

3.把数据列以gap为间隔分组

4.对每一组进行插入排序

5.把gap/2代入gap。

下图展示了使用希尔排序的过程

6.3代码实现let?insertSortGap?=?(array,gap)?=>?{//这段代码的解释可以往上看插入排序的注释????for(let?i?=?gap;i<?array.length;i++){??????let?temp?=?array[i];??????let?j?=?i-gap;??????while?(j>=?0?&&?array[j]?>?temp){????????array[j+gap]?=?array[j];????????j?-=?gap??????}??????array[j+gap]?=?temp????}}let?shellSort?=?(array)?=>?{??let?gap?=?Math.floor(array.length/2);??while?(gap>=1){????insertSortGap(array,gap)//分组后调用快速排序????gap?=?Math.floor(gap/2)??}??return?array}let?testArray?=?[35,80,21,54,11,45,92,39];console.log(shellSort(testArray));

测试结果：

6.4算法效率

不稳定排序算法，希尔排序第一个突破O(n2)的排序算法；是简单插入排序的改进版；它与插入排序的不同之处在于，它会优先比较距离较远的元素，直接插入排序是稳定的；而希尔排序是不稳定的，希尔排序的时间复杂度和步长的选择有关平均时间复杂度|最好情况|最坏情况?|空间复杂度||-------|----|-----|-----||O(n1.3)?|O(n)|O(n2)|O(1)

后续

除了以上的6种算法外，常用的还有计数排序和推排序算法，堆排序算法的涉及到二叉树数据结构的知识，后面再慢慢补充把。

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

---

衡东县15635839213： Java的几种常见排序 - ？
仲长滕盐酸： 快速排序法、冒泡法、选择排序法、插入排序法 1.快速排序:import java.util.Arrays; public class Test2{public static void main(String[] args){int[] a={5,4,2,4,9,1};Arrays.sort(a); //进行排序for(int i: a){System.out.print(i);}} } 2.冒泡排序 public ...

衡东县15635839213： JAVA中有哪几种常用的排序方法 - ？
仲长滕盐酸： 1、冒泡排序 冒泡排序是一个比较简单的排序方法.在待排序的数列基本有序的情况下排序速度较快.若要排序的数有n个,则需要n-1轮排序,第j轮排序中,从第一个数开始,相邻两数比较,若不符合所要求的顺序,则交换两者的位置;直到第...

衡东县15635839213： Java 常见的几种排序算法 - ？
仲长滕盐酸： 1、冒泡排序 2、选择排序 3、插入排序 4、归并排序 5、快速排序 6、希尔排序

衡东县15635839213： 几种常见简单排序算法 - ？
仲长滕盐酸： 排序算法一般分为以下几种: (1)非线性时间比较类排序:交换类排序(快速排序和冒泡排序)、插入类排序(简单插入排序和希尔排序)、选择类排序(简单选择排序和堆排序)、归并排序(二路归并排序和多路归并排序);(2)线性时间非比较类排序:计数排序、基数排序和桶排序.

衡东县15635839213： 排序都有哪几种方法?用JAVA实现一个快速排序.？
仲长滕盐酸： 排序的方法有:插入排序(直接插入排序、希尔排序),交换排序(冒泡排序、快速排序),选择排序(直接选择排序、堆排序),归并排序,分配排序(箱排序、基数排序) 快速排序的伪代码. / /使用快速排序方法对a[ 0 :n- 1 ]排序 从a[ 0 :n- 1 ]中选择一个元素作为m i d d l e,该元素为支点 把余下的元素分割为两段left 和r i g h t,使得l e f t中的元素都小于等于支点,而right 中的元素都大于等于支点 递归地使用快速排序方法对left 进行排序 递归地使用快速排序方法对right 进行排序 所得结果为l e f t + m i d d l e + r i g h t

衡东县15635839213： 常见排序算法有哪些 - ？
仲长滕盐酸： 常用的排序算法有:冒泡排序、选择排序、堆排序、SHELL排序、快速排序、归并排序、磁盘排序等等.但是每种排序算法都是各有优缺点.如果需要进一步研究各种算法的性能的话,那么就必须学习计算机算法和复杂性这门课程.

衡东县15635839213： java算法面试题:排序都有哪几种方法 - ？
仲长滕盐酸： 一、冒泡排序 [java] view plain copy package sort.bubble; import java.util.Random;/*** 依次比较相邻的两个数,将小数放在前面,大数放在后面* 冒泡排序,具有稳定性* 时间复杂度为O(n^2)* 不及堆排序,快速排序O(nlogn,底数为2)* @author ...

衡东县15635839213： 有哪些常见排序算法呢? ？
仲长滕盐酸： 中文名排序性质计算机内经常进行的一种操作排序算法快速排序、希尔排序、堆排序等分类稳定排序等1概念描述分类2冒泡排序3选择排序优劣Java代码4插入排序优劣Java代码原理C程序原理Pascal程序Pascal程序9树型排序▪Pascal程序10面试题排序概念描述编辑将杂乱无章的数据元素,通过一定的方法按关键字顺序排列的过程叫做排序 以上是对这个问题的回答,希望对您有帮助.

衡东县15635839213： Java中数组常见的几种排序方法 - ？
仲长滕盐酸： int[] num = {5,4,3,2,1}; for(int i = 0; i < num.length - 1; i++) { for (int j = i + 1; j < num.length; j++) { if (num[i] > num[j]) { int tmp = num[i]; num[i] = num[j]; num[j] = tmp; } } System.out.print(＂排序后:＂ + num[i]); }

衡东县15635839213： 几种常用的排序算法比较 - ？
仲长滕盐酸： 排序,从小大,0坐标的在下面,即排序后小的在下面,大的在上面.1,冒泡Bubble:从第0个开始,一直往上,与相邻的元素比较,如果下面的大,则交换.Analysis:Implementation:void BubbleSort(int *pData, int iNum)2,插入Insertion:与打...