欢迎光临
我的个人博客网站

第十三章 排序算法 下部分


排序算法 下

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

计数排序

计数排序是一种用来排序整数的优秀算法,时间复杂度为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’

赞(0) 打赏
未经允许不得转载:张拓的天空 » 第十三章 排序算法 下部分
分享到: 更多 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

专业的IT技术经验分享 更专业 更方便

联系我们本站主机

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏