经典九大排序

淩亂°似流年 2023-05-31 06:35 39阅读 0赞

九大排序排序是数据结构体系中最重要的内容之一，这一块必须要非常熟练的掌握，应该做到可以立马写出每个排序的代码，有多种实现方法的必须多种都能很快写出来，当然对各个排序的性能的了解也是基础且重要的。我们先对排序这一块进行一个整体的把握。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMDQzODU5_size_16_color_FFFFFF_t_70]

*  内排序：在对待排序数据存放在内存中进行的排序过程。
 *  外排序：待排数据量太大，无法一次性将所有待排序数据放入内存中，在排序过程中需要对磁盘等外部储存器进行访问。
 *  比较排序：排序过程中需要对数据关键字进行比较。
 *  非比较排序：排序过程中不需要对数据关键字进行比较。
 *  排序算法的稳定性：在每一次单趟排序后，相同关键字的相对顺序不变。

**插入排序：**  
***直接插入排序：***  
插入排序的工作原理就是将未排序数据，对已排序数据序列从后向前扫描，找到对应的位置并插入。插入排序通常采用占位的形式，空间复杂度为O(1),因此，在从后向前扫描的过程中，需要反复的把已排序的元素逐步向后挪位，为新插入元素提供插入的位置。

1）从第一个元素开始，该元素可以被认为已经被排序  
2）取出下一个元素，在已经排好序的序列中从后往前扫描  
3）直到找到小于或者等于该元素的位置  
4）将该位置后面的所有已排序的元素从后往前依次移一位  
5)将该元素插入到该位置  
6)重复步骤2~5

算法分析：

*  平均时间复杂度:o(N^2)这是显然的，标准的内外两层循环；
 *  最好时间复杂度：o(N),如果有序，那么每个元素都已经在在它的待排子序列的合适位置，不用找合适位置；
 *  最坏时间复杂度:o(N^2)；
 *  空间复杂度：o(1),因为需要存储个临时变量；
 *  稳定性：稳定的。

***二分插入排序：***  
二分插入排序时一种直接在插入排序上进行小改动的算法，与直接插排最大的区别在于查找插入位置时使用的是二分查找的方式。

1）从第一个元素开始，认为该元素已排序。  
2）取出下一个元素，在已排序序列中二分查找到第一个比它大的数的位置  
3）将元素插入到该位置后  
4）重复上述两步

由于只是改进了插入位置查找方法，所以空间复杂度仍然是O(1)，插入每个记录需要查找logi次，最多移动i+1次，因此，最佳情况时间复杂度是O(nlogn),最差和平均情况是O(n^2)。

**希尔排序:**  
有必要先谈谈这个排序是怎么来的（主要基于以下两点）

*  在直接插入排序里，对于一组已经有序的关键字序列进行排序时间复杂度是o(n)，因为每个元素的合适位置的查找都只需一次就能找到，因为左边的有序子序列的最后一个就小于等于该元素，那么就不需要挪动任何元素，每一趟都只用比较一次就结束了单趟排序。
 *  放宽第一点的情况，我们不要求有序，其实只要待排序列的有序度越高，也就是逆序对越少，直接插入排序的时间复杂度肯定是越低的（这句话是希尔排序的核心）。

希尔排序本质上是一种插入排序，但是对数列进行了等间隔分组处理，在每一组中做插入排序，这一优化使得原本 O(n^2) 的时间复杂度一下降为 O(nlogn)。

基本思想：  
希尔排序是按一定的间隔对数列进行分组，然后在每一个分组中做插入排序；随后逐次缩小间隔，在每一个分组中做插入排序…直到间隔等于1，做一次插入排序后结束。

那么问题来了，间隔应该取多大，怎么缩小？通常我们去取初始间隔为数列长度的一半：gap = length/2，以 gap = gap/2 的方式缩小，下面详细图解整个过程。

原始数组数组如下：  
![在这里插入图片描述][20191023095111320.png]  
首先取间隔为 gap = length/2 = 4，将数组分为如下的4组，对每一组实施插入排序：  
![在这里插入图片描述][20191023095134831.png]  
第一次排序，每一组较小的元素都移到了相对靠前的位置（这个状态可以叫 n-sorted，即以n为gap分组有序），可以想象相对有序的数组可能更有利于后面的排序。接着继续分组，gap = gap/2 = 2，对每一组实施插入排序：  
![在这里插入图片描述][20191023095201520.png]  
继续对数组分组，gap = gap/2 = 1，即所有元素组成一组，做插入排序完成算法：  
![在这里插入图片描述][20191023095251283.png]  
![在这里插入图片描述][20191023095312455.png]  
内层循环使用的插入排序与普通的插入排序基本一致，只是每次移动的步长变为 gap 而不是 1：

// shellSort
    function shellSort(arr) {
        
      for(let gap = Math.floor(arr.length/2); gap > 0; gap = Math.floor(gap/2)) {
        
        // 内层循环与插入排序的写法基本一致，只是每次移动的步长变为 gap
        for(let i = gap; i < arr.length; i++) {
        
          let j = i;
          let temp = arr[j];
          for(; j> 0; j -= gap) {
        
            if(temp >= arr[j-gap]) {
        
              break;
            }
            arr[j] = arr[j-gap];
          }
          arr[j] = temp;
        }
      }
      return arr;
    }
    
    // example
    let arr = [2,5,10,7,10,32,90,9,11,1,0,10];
    alert(shellSort(arr));

希尔排序的时间复杂度相当不好分析，因为其时间复杂度很大程度上取决于增量序列d\_i，而d\_i的选取至今也没有人找出怎样的一个增量序列是对所有情况的数据分布都有非常不错的效率，我们在代码中选取gap/3+1是一种较为常用、对于大部分数据分布的平均时间复杂度都较为不错的增量序列。

*  平均时间复杂度：o(N1.3)，大量数据研究表明在o(N1.3)附近，事实上也不是严格论证的结果;
 *  最好时间复杂度：仍然和增量序列的选取有关;
 *  最坏时间复杂度：o(N^2);
 *  空间复杂度：o(1);
 *  稳定性：不稳定，例如待排序列（3，2，2，1），取d=2时，显然就能看出是不稳定的。

**选择排序：**  
选择排序是一个简单直观的排序方法，它的工作原理很简单，首先从未排序序列中找到最大的元素，放到已排序序列的末尾，重复上述步骤，直到所有元素排序完毕。

1）假设未排序序列的第一个是最大值，记下该元素的位置，从前往后比较  
2）若某个元素比该元素大，覆盖之前的位置  
3）重复第二个步骤，直到找到未排序的末尾  
4）将未排序元素的第一个元素和最大元素交换位置  
5）重复前面几个步骤，直到所有元素都已经排序。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMDQzODU5_size_16_color_FFFFFF_t_70 1]

//选择排序
    function selsetSort(arr){
        
    	var len = arr.length;
    	var index;
    	for(var i=0;i<len-1;i++){
        
    		index=i;
    		for(var j=i+1;j<len;j++){
        
    			if(arr[index]>arr[j]){
        //寻找最小值
    				index=j;//保存最小值的索引
    			}
    		}
    		if(index!=i){
        
    		var temp =arr[i];
    		arr[i]=arr[index];
    		arr[index]=temp;
    	}
    	}
    	return arr;
    }

算法分析：

*  平均时间复杂度：o(N^2),嵌套双循环；
 *  最好时间复杂度：o(N^2),每次要找最大最小肯定是要遍历一遍的；
 *  最坏时间复杂度：o(N^2)；
 *  空间复杂度：o(1)；
 *  稳定性：稳定的。

**冒泡排序：**  
冒泡排序的思想就是每一趟排序都把大的元素往上浮，具体是这样：从当前待排序列第一个开始遍历，指针从第一个开始，如果当前元素大于下一个，那么二者交换，指针往后走，当走到待排序列末尾时，最大的一定被放到了最后（像冒泡泡一样上去了），然后缩小待排子序列（把最后一个从当前待排序序列删去），如此循环直到当前待排子序列只有一个元素。

算法分析：

*  平均时间复杂度：o(N^2),嵌套双循环；
 *  最好时间复杂度：o(N),若已经有序，那么第一趟就排好了；
 *  最坏时间复杂度：o(N^2)；
 *  空间复杂度：o(1)；
 *  稳定性：稳定的。

**堆排序：**  
堆：  
一种数据结构，可视为完全二叉树。如下图  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMDQzODU5_size_16_color_FFFFFF_t_70 2]  
一个父节点最多分二叉，圆圈上面数字是节点序号，可以看到一层层由左向右排列。圆圈里面数字是该节点存的值。其中序号1为整个树的根节点，2、3为其子节点。另外，序号2也是子树（将2、4、5视为一个子树）的根节点。6~10为叶节点，叶节点没有子节点。

二叉堆分为最大堆和最小堆。最大堆指堆中最大元素放在父节点，最小堆指堆中最小元素放在父节点。堆排序中用最大堆。

另外还需要知道堆的几个结论：

*  设某节点序号为i,则其父节点为⌊i/2⌋，2*i为左子节点序号，2*i+1为右子节点序号。其中，⌊⌋为向下取整符号。
 *  当存储了n个元素时，⌊n/2⌋+1、⌊n/2⌋+1、···、n为叶节点。

堆的预备知识：

*  堆是一个完全二叉树。
 *  完全二叉树： 二叉树除开最后一层，其他层结点数都达到最大，最后一层的所有结点都集中在左边（左边结点排列满的情况下，右边才能缺失结点）。
 *  大顶堆：根结点为最大值，每个结点的值大于或等于其孩子结点的值。
 *  小顶堆：根结点为最小值，每个结点的值小于或等于其孩子结点的值。
 *  堆的存储： 堆由数组来实现，相当于对二叉树做层序遍历。如下图：  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMDQzODU5_size_16_color_FFFFFF_t_70 3]  
    ![在这里插入图片描述][20191023102845631.png]  
    堆排序算法  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMDQzODU5_size_16_color_FFFFFF_t_70 4]  
    现在需要对如上二叉树做升序排序，总共分为三步：

（1）将初始二叉树转化为大顶堆（heapify）（实质是从第一个非叶子结点开始，从下至上，从右至左，对每一个非叶子结点做shiftDown操作），此时根结点为最大值，将其与最后一个结点交换。  
（2）除开最后一个结点，将其余节点组成的新堆转化为大顶堆（实质上是对根节点做shiftDown操作），此时根结点为次最大值，将其与最后一个结点交换。  
（3）重复步骤2，直到堆中元素个数为1（或其对应数组的长度为1），排序完成。  
下面详细图解这个过程：  
步骤1：  
初始化大顶堆，首先选取最后一个非叶子结点(我们只需要调整父节点和孩子节点之间的大小关系，叶子结点之间的大小关系无需调整)。设数组为arr，则第一个非叶子结点的下标为：i = Math.floor(arr.length/2 - 1) = 1，也就是数字4，如图中虚线框，找到三个数字的最大值，与父节点交换。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMDQzODU5_size_16_color_FFFFFF_t_70 5]  
然后，下标 i 依次减1（即从第一个非叶子结点开始，从右至左，从下至上遍历所有非叶子节点）。后面的每一次调整都是如此：找到父子结点中的最大值，做交换。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMDQzODU5_size_16_color_FFFFFF_t_70 6]  
这一步中数字6、1交换后，数字\[1,5,4\]组成的堆顺序不对，需要执行一步调整。因此需要注意，每一次对一个非叶子结点做调整后，都要观察是否会影响子堆顺序！  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMDQzODU5_size_16_color_FFFFFF_t_70 7]  
这次调整后，根节点为最大值，形成了一个大顶堆，将根节点与最后一个结点交换。  
步骤2：  
除开当前最后一个结点6(即最大值)，将其余结点\[4,5,3,1\]组成新堆转化为大顶堆(注意观察，此时根节点以外的其他结点，都满足大顶堆的特征，所以可以从根节点4开始调整，即找到4应该处于的位置即可)。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMDQzODU5_size_16_color_FFFFFF_t_70 8]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMDQzODU5_size_16_color_FFFFFF_t_70 9]  
步骤3：  
接下来反复执行步骤2，直到堆中元素个数为1：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMDQzODU5_size_16_color_FFFFFF_t_70 10]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMDQzODU5_size_16_color_FFFFFF_t_70 11]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMDQzODU5_size_16_color_FFFFFF_t_70 12]

// 交换两个节点
    function swap(A, i, j) {
        
      let temp = A[i];
      A[i] = A[j];
      A[j] = temp; 
    }
    
    // 将 i 结点以下的堆整理为大顶堆，注意这一步实现的基础实际上是：
    // 假设 结点 i 以下的子堆已经是一个大顶堆，shiftDown函数实现的
    // 功能是实际上是：找到 结点 i 在包括结点 i 的堆中的正确位置。后面
    // 将写一个 for 循环，从第一个非叶子结点开始，对每一个非叶子结点
    // 都执行 shiftDown操作，所以就满足了结点 i 以下的子堆已经是一大
    //顶堆
    function shiftDown(A, i, length) {
        
      let temp = A[i]; // 当前父节点
    // j<length 的目的是对结点 i 以下的结点全部做顺序调整
      for(let j = 2*i+1; j<length; j = 2*j+1) {
        
        temp = A[i];  // 将 A[i] 取出，整个过程相当于找到 A[i] 应处于的位置
        if(j+1 < length && A[j] < A[j+1]) {
         
          j++;   // 找到两个孩子中较大的一个，再与父节点比较
        }
        if(temp < A[j]) {
        
          swap(A, i, j) // 如果父节点小于子节点:交换；否则跳出
          i = j;  // 交换后，temp 的下标变为 j
        } else {
        
          break;
        }
      }
    }
    
    // 堆排序
    function heapSort(A) {
        
      // 初始化大顶堆，从第一个非叶子结点开始
      for(let i = Math.floor(A.length/2-1); i>=0; i--) {
        
        shiftDown(A, i, A.length);
      }
      // 排序，每一次for循环找出一个当前最大值，数组长度减一
      for(let i = Math.floor(A.length-1); i>0; i--) {
        
        swap(A, 0, i); // 根节点与最后一个节点交换
        shiftDown(A, 0, i); // 从根节点开始调整，并且最后一个结点已经为当
                             // 前最大值，不需要再参与比较，所以第三个参数
                             // 为 i，即比较到最后一个结点前一个即可
      }
    }
    
    let Arr = [4, 6, 8, 5, 9, 1, 2, 5, 3, 2];
    heapSort(Arr);
    alert(Arr);

**快速排序：**  
快速排序算法的思想类似于二分法，每次都是在数组中选择一个基数（可以是任意一个位置的数，不过一般选择中间的数字或者最左边的数字），每一轮结束后，比该基数小的数都位于该基数的左边，比该基数大的数都位于该基数的右边。然后再分别对基数左边和右边的数组进行相同的操作，直到数组中只有一个元素时，返回该数组。不说了，具体上代码(我取数组最左边的元素作为基数)：

阮一峰版 内存占用较多

上面简单版本的缺点是，它需要Ω(n)的额外存储空间，也就跟归并排序一样不好。额外需要的存储器空间配置，在实际上的实现，也会极度影响速度和高速缓存的性能。

真正的快排  
（1）确定基准数  
我们把数组的第一个元素作为基准数。  
（2）确定哨兵  
用两个变量i和j，分别指向序列最左边和最右边。我们为这两个变量起个好听的名字“哨兵i”和“哨兵j”。刚开始的时候让哨兵i指向序列的最左边，让哨兵j指向序列的最右边。  
首先哨兵j开始出动。哨兵j一步一步地向左挪动（即j–），直到找到一个小于6的数停下来。接下来哨兵i再一步一步向右挪动（即i++），直到找到一个数大于6的数停下来。最后哨兵j停在了数字5面前，哨兵i停在了数字7面前。  
接下来开始哨兵j继续向左挪动。他发现了4（比基准数6要小，满足要求）之后停了下来。哨兵i也继续向右挪动的，他发现了9（比基准数6要大，满足要求）之后停了下来。此时再次进行交换。  
![在这里插入图片描述][20191107160122696.png]  
![在这里插入图片描述][20191107160134667.png]  
第二次交换结束，“探测”继续。哨兵j继续向左挪动，他发现了3（比基准数6要小，满足要求）之后又停了下来。哨兵i继续向右移动，糟啦！此时哨兵i和哨兵j相遇了，哨兵i和哨兵j都走到3面前。说明此时“探测”结束。我们将基准数6和3进行交换。交换之后的序列如下：  
![在这里插入图片描述][20191107160154997.png]  
![在这里插入图片描述][20191107160205566.png]  
![在这里插入图片描述][20191107160214510.png]  
到此第一轮“探测”真正结束。此时以基准数6为分界点，6左边的数都小于等于6，6右边的数都大于等于6。然后对6两边的数组做递归处理即可。

有的书上是以中间的数作为基准数的，要实现这个方便非常方便，直接将中间的数和第一个数进行交换就可以了。

**归并排序：**  
归并排序采用的是分治的思想，首先是“分”，将一个数组反复二分为两个小数组，直到每个数组只有一个元素；其次是“治”，从最小数组开始，两两按大小顺序合并，直到并为原始数组大小，下面是图解：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMDQzODU5_size_16_color_FFFFFF_t_70 13]  
观察下“治”的过程，可以看出，“治”实际上是将已经有序的数组合并为更大的有序数组。那么怎样将已经有序的数组合并为更大的有序数组？很简单，创建一个临时数组C，比较A\[0\]，B\[0\]，将较小值放到C\[0\]，再比较A\[1\]与B\[0\]（或者A\[0\]，B\[1\]），将较小值放到C\[1\]，直到对A，B都遍历一遍。可以看出数组A，B都只需遍历一遍，所以对两个有序数组的排序的时间复杂度为O(n)。

而“分”就是将原始数组逐次二分，直到每个数组只剩一个元素，一个元素的数组自然是有序的，所以就可以开始“治”的过程了。

时间复杂度分析：分的过程需要三步：log8 = 3，而每一步都需要遍历一次8个元素，所以8个元素共需要运行 8log8 次指令，那么对于 n 个元素，时间复杂度为 O(nlogn)。

function mergeSort(arr) {
        
     const len=arr.length
     if(len==1)return arr
     const mid=Math.floor(len/2),left=arr.slice(0,mid),right=arr.slice(mid,len)
     return merge(mergeSort(left),mergeSort(right)) 
    }
    
    function  merge(left,right) {
        
      let res=[],l=0,r=0;
      while(l<left.length&&r<right.length){
        
        if(left[l]<right[r])res.push(left[l++])
        else if(left[l]==right[r]){
        
          res.push(left[l++])
          r++
        }else res.push(right[r++])
      }
      while(l<left.length)res.push(left[l++])
      while(r<right.length)res.push(right[r++])
      return res
    }
    
    console.log(mergeSort([2,9,1,0,8]))

**计数排序：**  
计数排序是利用数组下标作为参照物确定元素位置；运用下标作为参照即参与排序的元素可以变成数组下标,那么就要求被排元素必须是整数。

*  有一组整数序列 A,找到A中的最大值 max；
 *  新建累计数组B, B.length 为 max+1 ,这样的话B的最后一个元素下标为max；
 *  数组B值以0填充,开始计数, A中元素出现一次, 对应的B位置值加一,计算下标值在A中出现的频次；
 *  把B中每个元素与之前元素进行累加,表示已占用空间,奇妙发生在此,当前占用空间-1即是元素排序后存在的下标位置,然后自身计数-1,因为会有重复数据；
 *  新建写回数组C, 长度与A一致, 把在B中排序完成集合写回C。

![原生数组A][A]  
我们先分析几个便于理解

*  B\[0\]=0,已占据0空间, 即A中不存在这个元素；
 *  B\[1\]=1,已占据一个空间即 1-1=0 C\[0\]=1

以上是根据B的下标顺序来分析的,回写我们需要根据A中元素,A中第一个为6,在B中对应下标6,值为8,表示已占据8个空间,回写C\[8-1\] = 6。  
![在这里插入图片描述][20191023160638182.png]  
注释:值后小括号表示回写顺序

**基数排序：**  
基数排序是一种非比较型的整数排序算法。其基本原理是，按照整数的每个位数分组。在分组过程中，对于不足位的数据用0补位。

基数排序按照对位数分组的顺序的不同，可以分为LSD（Least significant digit）基数排序和MSD（Most significant digit）基数排序。

LSD基数排序，是按照从低位到高位的顺序进行分组排序。MSD基数排序，是按照从高位到低位的顺序进行分组排序。上述两种方式不仅仅是对位数分组顺序不同，其实现原理也是不同的。

***LSD基数排序：***  
对于序列中的每个整数的每一位都可以看成是一个桶，而该位上的数字就可以认为是这个桶的键值。比如下面数组

\[170, 45, 75, 90, 802, 2, 24, 66\]

首先我们要确认最大值，一个for循环得最大数，因为最大数的位数最长。  
然后，建立10个桶，亦即10个数组。  
然后再遍历所有元素，取其个位数，个位数是什么就放进对应编号的数组，1放进1号桶。

0号桶： 170，90
     1号桶： 无
     2号桶： 802，2
     3号桶： 无
     4号桶： 24
     5号桶： 45， 75
     6号桶： 66
     7－9号桶： 无

然后再依次将元素从桶里最出来，覆盖原数组，或放到一个新数组，我们把这个经过第一次排序的数组叫sorted。  
sorted = \[170,90,802,2,24,45,75,66\]  
然后我们再一次遍历sorted数组的元素，这次取十位的值。这时要注意，2不存在十位，那么默认为0

0号桶： 2，802
     1号桶： 无
     2号桶： 24
     3号桶： 无
     4号桶： 45
     5号桶： 无
     6号桶： 66
     7号桶： 170， 75
     8号桶： 无
     9号桶： 90

再全部取出来  
sorted = \[2，802,24，45，66，170，75，90\]  
开始百位上的入桶操作，没有百位就默认为0：

0号桶： 2，24，45，66，75，90
     1号桶： 170
     2－7号桶：无
     8号桶： 802
     9号桶： 无

再全部取出来  
sorted = \[2，24，45，66，75，90，170，802\]  
没有千位数，那么循环结束，返回结果桶sorted

//by 司徒正美
    function radixSort(array) {
        
        var max = Math.max.apply(0, array);
        var times = getLoopTimes(max),
            len = array.length;
        var buckets = [];
        for (let i = 0; i < 10; i++) {
        
            buckets[i] = []; //初始化10个桶
        }
        for (var radix = 1; radix <= times; radix++) {
        
            //个位，十位，百位，千位这样循环
            lsdRadixSort(array, buckets, len, radix);
        }
        return array;
    }
    // 根据数字某个位数上的值得到桶的编号
    function getBucketNumer(num, d) {
        
        return (num + "").reverse()[d];
    }
    //或者这个
    function getBucketNumer(num, i) {
        
        return Math.floor((num / Math.pow(10, i)) % 10);
    }
    //获取数字的位数
    function getLoopTimes(num) {
        
        var digits = 0;
        do {
        
            if (num > 1) {
        
                digits++;
            } else {
        
                break;
            }
        } while ((num = num / 10));
        return digits;
    }
    function lsdRadixSort(array, buckets, len, radix) {
        
        //入桶
        for (let i = 0; i < len; i++) {
        
            let el = array[i];
            let index = getBucketNumer(el, radix);
            buckets[index].push(el);
        }
        var k = 0;
        //重写原桶
        for (let i = 0; i < 10; i++) {
        
            let bucket = buckets[i];
            for (let j = 0; j < bucket.length; j++) {
        
                array[k++] = bucket[j];
            }
            bucket.length = 0;
        }
    }
    // test
    var arr = [278, 109, 63, 930, 589, 184, 505, 269, 8, 83];
    console.log(radixSort(arr));

***MSD基数排序:***  
最开始时也是遍历所有元素，取最大值，得到最大位数，建立10个桶。这时从百位取起。不足三位，对应位置为0.

0号桶： 45, 75, 90, 2, 24, 66
     1号桶： 107
     2-7号桶： 无
     8号桶： 802
     9号桶： 无

接下来就与LSD不一样。我们对每个长度大于1的桶进行内部排序。内部排序也是用基数排序。我们需要建立另10个桶，对0号桶的元素进行入桶操作，这时比原来少一位，亦即十位。

0号桶： 2
     1号桶： 无
     2号桶： 24
     3号桶： 无
     4号桶： 45
     5号桶： 无
     6号桶： 66
     7号桶： 75
     8号桶： 无
     9号桶： 90

然后继续递归上一步，因此每个桶的长度，都没有超过1，于是开始0号桶的收集工作：

0号桶： 2，24，45，66，75，90
     1号桶： 107
     2-7号桶： 无
     8号桶： 802
     9号桶： 无

将这步骤应用其他桶，最后就排序完毕。

//by 司徒正美
    function radixSort(array) {
        
        var max = Math.max.apply(0, array),
            times = getLoopTimes(max),
            len = array.length;
        msdRadixSort(array, len, times);
        return array;
    }
    
    //或者这个
    function getBucketNumer(num, i) {
        
        return Math.floor((num / Math.pow(10, i)) % 10);
    }
    //获取数字的位数
    function getLoopTimes(num) {
        
        var digits = 0;
        do {
        
            if (num > 1) {
        
                digits++;
            } else {
        
                break;
            }
        } while ((num = num / 10));
        return digits;
    }
    function msdRadixSort(array, len, radix) {
        
        var buckets = [[], [], [], [], [], [], [], [], [], []];
        //入桶
        for (let i = 0; i < len; i++) {
        
            let el = array[i];
            let index = getBucketNumer(el, radix);
            buckets[index].push(el);
        }
        //递归子桶
        for (let i = 0; i < 10; i++) {
        
            let el = buckets[i];
            if (el.length > 1 && radix - 1) {
        
                msdRadixSort(el, el.length, radix - 1);
            }
        }
        var k = 0;
        //重写原桶
        for (let i = 0; i < 10; i++) {
        
            let bucket = buckets[i];
            for (let j = 0; j < bucket.length; j++) {
        
                array[k++] = bucket[j];
            }
            bucket.length = 0;
        }
    }
    var arr = radixSort([170, 45, 75, 90, 802, 2, 24, 66]);
    console.log(arr);

参考：[经典九大排序（1）——简单排序][1]  
[JS实现插入排序][JS]  
[了解堆排序并用js实现][js]  
[JS实现堆排序][JS 1]  
[JS实现归并排序][JS 2]  
[JavaScript算法-计数排序(非比较型)][JavaScript_-]  
[计数排序，桶排序与基数排序][Link 1]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMDQzODU5_size_16_color_FFFFFF_t_70]: /images/20230531/fdefb5dd74ce4d1d9d613f996d6493cc.png
[20191023095111320.png]: /images/20230531/499afb231fdb49e8a69722f8a089cad7.png
[20191023095134831.png]: /images/20230531/96c4724bb1184c87bc07506efd5a0246.png
[20191023095201520.png]: /images/20230531/81d822ea09c1432caa8994724b2df5c6.png
[20191023095251283.png]: /images/20230531/e561856da46f4dfd85bc5ba3d335bbb4.png
[20191023095312455.png]: /images/20230531/2b8feaf14dc841c7aca55eebfaff96f6.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMDQzODU5_size_16_color_FFFFFF_t_70 1]: /images/20230531/738f9cfd7d1c43c0b984fff8bd0c254e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMDQzODU5_size_16_color_FFFFFF_t_70 2]: /images/20230531/9d9ca3fd3c054e30aed825343d868596.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMDQzODU5_size_16_color_FFFFFF_t_70 3]: /images/20230531/32ff2fdbfc6546a88c7d71b284a83b4f.png
[20191023102845631.png]: /images/20230531/2c291147fdf442948f68e1522903b404.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMDQzODU5_size_16_color_FFFFFF_t_70 4]: /images/20230531/f9042589558a43dda9b7c7e8f8ff7a6b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMDQzODU5_size_16_color_FFFFFF_t_70 5]: /images/20230531/140affea10594733a27a59078c2e3d93.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMDQzODU5_size_16_color_FFFFFF_t_70 6]: /images/20230531/4823288c6b8445eda13f5058b3d8dfa1.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMDQzODU5_size_16_color_FFFFFF_t_70 7]: /images/20230531/430d2482f3d546b988ee7fc53232dc08.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMDQzODU5_size_16_color_FFFFFF_t_70 8]: /images/20230531/d3a5902ef33145d6b565c74553952686.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMDQzODU5_size_16_color_FFFFFF_t_70 9]: /images/20230531/6bf4ba9d0de74e868f841d6e38f787aa.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMDQzODU5_size_16_color_FFFFFF_t_70 10]: /images/20230531/e45b5f2394a8409db50637f19f1722ee.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMDQzODU5_size_16_color_FFFFFF_t_70 11]: /images/20230531/7d29ab9853ec4a26a7406629f342bcf9.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMDQzODU5_size_16_color_FFFFFF_t_70 12]: /images/20230531/fb5c9e0c63a9462b9a892e3640b5dc48.png
[20191107160122696.png]: /images/20230531/796388c5b2ca400191b1a30fb8ea90f7.png
[20191107160134667.png]: /images/20230531/a14588b8746a4bf0a7214356fe4b2633.png
[20191107160154997.png]: /images/20230531/103f663c94ed4ea981553edeca6ff40e.png
[20191107160205566.png]: /images/20230531/9b9b791a69784b96b110895bd598261f.png
[20191107160214510.png]: /images/20230531/8d8287349cd449a6ad9e64b6f9136bd1.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMDQzODU5_size_16_color_FFFFFF_t_70 13]: /images/20230531/974c7052c04949cbaf624727e77670a0.png
[A]: /images/20230531/4d96b1b667af4582a07c7a4c009a98ff.png
[20191023160638182.png]: /images/20230531/47e1fed81fcd4749bb839c1f3f535c57.png
[1]: https://blog.csdn.net/weixin_38333555/article/details/80515605
[JS]: https://blog.csdn.net/bangbanggangan/article/details/80986501
[js]: https://blog.csdn.net/longpersevere/article/details/78400892
[JS 1]: https://segmentfault.com/a/1190000015487916?utm_source=tag-newest
[JS 2]: https://segmentfault.com/a/1190000015488807?utm_source=tag-newest
[JavaScript_-]: https://blog.csdn.net/an2766160/article/details/88064591
[Link 1]: https://segmentfault.com/a/1190000012923917