排序算法 下

以下被称为分布式排序的算法，原始数组中的数据会分发到多个中间结构（桶），再合起来放回原始数组。最著名的分布式算法有计数排序、桶排序和基数排序，这三种算法非常相似。

计数排序

计数排序是一种用来排序整数的优秀算法，时间复杂度为O(n + k)，其中k是临时计数数组的大小，但是，他需要更多的内存来存放临时变量。

• 先创建一个排序数据中最大值 + 1创建一个数组(关于这部分我刚开始也不是很明白，js的数组不是动态的吗!何必多此一举去找排序数据的最大值，然后创建一个数组呢???后来想了一下数组的扩容是不是要数据迁移，那样的确不如提前创建大一点，然后找了一下资料: 探究JS V8引擎下的“数组”底层实现)，感兴趣的可以瞧一瞧。
• 然后开始计数，其实就是以下标代表数据，然后以值作为数据出现的次数(分布式中的第一步)
• 循环计数的数组，然后将其回归到原数组上(分布式中的第二步)

export function sortArray(arr: Array<number>) {          if (arr.length < 2){         return;     }          let len = findMaxNumber(arr) + 1;     let countArr = new Array(len).fill(0);      for (let i = 0; i < arr.length; i++) {         countArr[arr[i]]++;     }      for (let i = 0,index = 0; i < countArr.length; i++) {          for (let j = 0; j < countArr[i]; j++) {             arr[index++] = i;         }     } }  /**  * 找最大数  * @param arr  */ function findMaxNumber(arr: Array<number>):number {     let max:number = 0;          for (let i = 0; i < arr.length; i++) {         if(arr[i] > max){             max = arr[i];         }     }     return max; }   let arr = [54,8,45,7, 1,2,45,9,8,452,35,754,127,6,21,124,454] sortArray(arr)  // @ts-ignore console.log(arr) 

可以看出这种排序很适合那种有多个重复数据的整数数组，但是数据中有一个特别大的时候，计数数组将会占用很大的内存

还有这里创建的数组是 最大值 + 1，因为数组的下标是0开始的，所以 +1确保最大值也能加入数据

桶排序

桶排序也称之为箱排序，也是分布式排序算法中的一种，它将元素分为不同的桶(较小的数组)，然后使用一个简单的排序算法排序(比如说插入排序)，然后合并数组为结果

对于桶排序算法，我们需要指定需要多少个桶来排序各个元素，默认情况下，我们会使用5个桶(这里我认为是每个桶的容量为5，而且看这个作者命名bucketSize，也觉得就是桶容量，不过确定了一个桶的容量，自然就确定了桶的个数，后面我还是以桶容量来说明该参数)。桶排序在所有元素平分到各个桶时的表现最好。如果元素非常稀疏，则使用更多的桶会更好。如果元素非常密集，则使用较少的桶会比较好，因此我们允许bucketSize以参数的形式传递

• 第一步: 创建桶

  创建桶看似很简单，实际上还是有点难度的，需要做到几点

  • 算出桶的个数: Math.floor((最大值 - 最小值 ) / 单个桶的容量) + 1
  • 然后创建一个桶的个数对应大小的数组，内部填充[]，注意这里不能使用fill填充，fill填充的数组是同一个引用，所以会导致失败(这里创建了一个二维数组)
  • 将排序元素塞到对应的桶里去: (当前值 - 最小值) / 单个桶的容量，其实这个塞入的过程就已经对桶内数据进行了一次粗略排序

• 第二步: 对桶排序

  传回的是一个二维数组，桶是有序的(0号桶的内容会都小于1号桶的内容)

  使用插入排序对桶内数据排序

  组合为新的数组返回

import {sortArray as insertSort} from "./InsertSort"  export function sortArray(arr: Array<number>, bucketSize: number = 5) {      if (arr.length < 2) {         return arr;     }      // 创建桶     let buckets = createBuckets(arr, bucketSize);     // 桶排序并返回数组     return sortBuckets(buckets); }   /**  * 创建桶  * @param arr  * @param bucketSize  单个桶的容量  */ function createBuckets(arr: Array<number>, bucketSize: number):any[][] {     let minNum = arr[0];     let maxNum = arr[0];      // 循环查找最大值最小值     for (let i = 1; i < arr.length; i++) {          if (maxNum < arr[i]) {             maxNum = arr[i];         } else if (arr[i] < minNum) {             minNum = arr[i];         }      }      // 计算桶数     const bucketCount = Math.floor((maxNum - minNum) / bucketSize) + 1;     // 创建并初始化装桶的数组,这里就是一个二元数组了     const buckets = [];          //这个for循环不要使用fill替换     for (let i = 0; i < bucketCount; i++) {         buckets[i] = [];     }      for (let i = 0; i < arr.length; i++) {         // 计算下标的过程其实是对数据进行了一次简单的排序,然后桶就会呈现出有序性         const index = Math.floor((arr[i] - minNum) / bucketSize)         buckets[index].push(arr[i]);     }      return buckets; }  /**  * 对桶进行排序  * @param buckets  */ function sortBuckets(buckets: any[][]) {     let result = [];     for (let i = 0; i < buckets.length; i++) {         let element = buckets[i];          if(element !== null){             insertSort(element)             result.push(...element);         }     }      return result; }  let arr = [54,8,45,7, 1,2,45,9,8,452,35,754,127,6,21,124,454] let sortArr = sortArray(arr)  // @ts-ignore console.log(sortArr)  

还是想强调一下，填充桶数组的时候不能使用'fill'