js十大经典排序算法

桃扇骨 2023-02-12 06:26 45阅读 0赞

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ1MDQzMTA1_size_16_color_FFFFFF_t_70]  
**名词解释：**  
n: 数据规模  
k:“桶”的个数  
In-place: 占用常数内存，不占用额外内存  
Out-place: 占用额外内存  
稳定性：排序后2个相等键值的顺序和排序之前它们的顺序相同

冒泡排序（Bubble Sort）  
冒泡排序算法的原理如下：  
1.比较相邻的元素。如果第一个比第二个大，就交换他们两个。  
2.对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。  
3.针对所有的元素重复以上的步骤，除了最后一个。  
4.持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

**冒泡排序动图演示：**  
![在这里插入图片描述][20200525094819542.gif]  
**冒泡排序JavaScript代码实现：**

**插入排序（Insertion Sort）**  
插入排序的工作方式像许多人排序一手扑克牌。开始时，我们的左手为空并且桌子上的牌面向下。然后，我们每次从桌子上拿走一张牌并将它插入左手中正确的位置。为了找到一张牌的正确位置，我们从右到左将它与已在手中的每张牌进行比较。拿在左手上的牌总是排序好的，原来这些牌是桌子上牌堆中顶部的牌 。  
插入排序是指在待排序的元素中，假设前面n-1(其中n>=2)个数已经是排好顺序的，现将第n个数插到前面已经排好的序列中，然后找到合适自己的位置，使得插入第n个数的这个序列也是排好顺序的。按照此法对所有元素进行插入，直到整个序列排为有序的过程，称为插入排序

**插入排序动图演示：**  
![在这里插入图片描述][20200525095129539.gif]  
**插入排序JavaScript代码实现：**

**选择排序（Selection Sort）**  
选择排序思想：“n个记录的文件的直接选择排序可经过n-1趟直接选择排序得到有序结果: ①初始状态:无序区为R\[1…n\],有序区为空。 ②第1趟排序 在无序区R\[1…n\]中选出关键字最小的记录R\[k\],将它与无序区的第1个记录R\[1\]交换,使R\[1…1\]和R\[2…n\]分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区。 …… ③第i趟排序 第i趟排序开始时,当前有序区和无序区分别为R\[1…i-1\]和R(i…n)。该趟排序从当前无序区中选出关键字最小的记录 R\[k\],将它与无序区的第1个记录R交换,使R\[1…i\]和R分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区。”  
**选择排序动图演示：**  
![在这里插入图片描述][20200525095253473.gif]  
**选择排序JavaScript代码实现：**

**希尔排序（Shell Sort）**  
希尔排序算法：先取一个小于n的整数d1作为第一个增量，把文件的全部记录分组。所有距离为d1的倍数的记录放在同一个组中。先在各组内进行直接插入排序；然后，取第二个增量d2<d1重复上述的分组和排序，直至所取的增量 =1( < …<d2<d1)，即所有记录放在同一组中进行直接插入排序为止。  
该方法实质上是一种分组插入方法  
比较相隔较远距离（称为增量）的数，使得数移动时能跨过多个元素，则进行一次比较就可能消除多个元素交换。D.L.shell于1959年在以他名字命名的排序算法中实现了这一思想。算法先将要排序的一组数按某个增量d分成若干组，每组中记录的下标相差d.对每组中全部元素进行排序，然后再用一个较小的增量对它进行，在每组中再进行排序。当增量减到1时，整个要排序的数被分成一组，排序完成。  
一般的初次取序列的一半为增量，以后每次减半，直到增量为1。  
给定实例的shell排序的排序过程  
假设待排序文件有10个记录，其关键字分别是：  
49，38，65，97，76，13，27，49，55，04。  
增量序列的取值依次为：  
5，2，1  
![在这里插入图片描述][2020052509544079.jpg]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ1MDQzMTA1_size_16_color_FFFFFF_t_70 1]  
**希尔排序JavaScript代码实现：**

**归并排序（Merge Sort）**  
作为一种典型的分而治之思想的算法应用，归并排序的实现由两种方法：

自上而下的递归（所有递归的方法都可以用迭代重写，所以就有了第2种方法）  
自下而上的迭代  
在《数据结构与算法JavaScript描述》中，作者给出了自下而上的迭代方法。但是对于递归法，作者却认为：

However, it is not possible to do so in JavaScript, as the recursion goes too deep  
for the language to handle.  
然而,在 JavaScript 中这种方式不太可行,因为这个算法的递归深度对它来讲太深了。  
**归并排序动图演示：**  
![在这里插入图片描述][2020052509560681.gif]  
**归并排序JavaScript代码实现：**

**快速排序（Quick Sort）  
快速排序动图演示：**  
![在这里插入图片描述][2020052509580430.gif]  
**快速排序使用分治法来把一个串（list）分为两个子串（sub-lists）。具体算法描述如下：**

**堆排序（Heap Sort）**  
堆排序的基本思想是:将待排序序列构造成一个大顶堆,此时,整个序列的最大值就是堆顶的根节点。将其与末尾元素进行交换,此时末尾就为最大值。然后将剩余n-1个元素重新构造成一个堆,这样会得到n个元素的次小值。如此反复执行,便能得到一个有序序列了  
1.大顶堆：每个节点的值都大于或等于其子节点的值，在堆排序算法中用于升序排列  
2.小顶堆：每个节点的值都小于或等于其子节点的值，在堆排序算法中用于降序排列  
堆排序JavaScript代码实现：  
![在这里插入图片描述][20200525095857866.gif]

**桶排序（Bucket Sort）  
桶排序JavaScript代码实现：**

**基数排序（Radix Sort）**  
基数排序须知：  
基数排序有两种方法：

MSD 从高位开始进行排序  
LSD 从低位开始进行排序  
LSD基数排序动图演示：  
![在这里插入图片描述][20200525100032798.gif]  
**基数排序JavaScript代码实现：**

//LSD Radix Sort
    var counter = [];
    function radixSort(arr, maxDigit) { 
        var mod = 10;
        var dev = 1;
        for (var i = 0; i < maxDigit; i++, dev *= 10, mod *= 10) { 
            for(var j = 0; j < arr.length; j++) { 
                var bucket = parseInt((arr[j] % mod) / dev); if(counter[bucket]==null) { counter[bucket] = []; } counter[bucket].push(arr[j]); } var pos = 0; for(var j = 0; j < counter.length; j++) { var value = null; if(counter[j]!=null) { while ((value = counter[j].shift()) != null) { 
                          arr[pos++] = value;
                    }
              }
            }
        }
        return arr;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ1MDQzMTA1_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200525094707105.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ1MDQzMTA1,size_16,color_FFFFFF,t_70
[20200525094819542.gif]: https://img-blog.csdnimg.cn/20200525094819542.gif
[20200525095129539.gif]: https://img-blog.csdnimg.cn/20200525095129539.gif
[20200525095253473.gif]: https://img-blog.csdnimg.cn/20200525095253473.gif
[2020052509544079.jpg]: https://img-blog.csdnimg.cn/2020052509544079.jpg
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ1MDQzMTA1_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200525095453538.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ1MDQzMTA1,size_16,color_FFFFFF,t_70
[2020052509560681.gif]: https://img-blog.csdnimg.cn/2020052509560681.gif
[2020052509580430.gif]: https://img-blog.csdnimg.cn/2020052509580430.gif
[20200525095857866.gif]: https://img-blog.csdnimg.cn/20200525095857866.gif
[20200525100032798.gif]: https://img-blog.csdnimg.cn/20200525100032798.gif