前端算法之堆--桶排序和快速排序

2024-01-06 22:36

本文主要是介绍前端算法之堆--桶排序和快速排序,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

  • 前 K 个高频元素
    • 使用API实现
    • 使用桶排序
  • 数组中的第K个最大元素
    • 直接使用 javaScript API
    • 使用快速排序
  • 扩展:桶排序
    • 例子
  • 扩展:快速排序
    • 快速排序的步骤:
    • 快速排序示例:

前 K 个高频元素

leetcode链接:https://leetcode.cn/problems/top-k-frequent-elements/

给你一个整数数组 nums 和一个整数 k ,请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。

示例 1:

输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]

示例 2:

输入: nums = [1], k = 1
输出: [1]

提示:

1 <= nums.length <= 105
k 的取值范围是 [1, 数组中不相同的元素的个数]
题目数据保证答案唯一,换句话说,数组中前 k 个高频元素的集合是唯一的

进阶: 你所设计算法的时间复杂度 必须 优于 O(n log n) ,其中 n 是数组大小。

更多详细内容,请微信搜索“前端爱好者戳我 查看

使用API实现

/*** @param {number[]} nums* @param {number} k* @return {number[]}*/
var topKFrequent = function(nums, k) {let map = new Map() // 定义一个map类型let arr = [...new Set(nums)] // 获取数组去重后的元素// 一次遍历nums值,把他们出现的频次放在map里面nums.map(num => {if(map.has(num)){map.set(num,map.get(num) + 1)} else {map.set(num,1)}})// 现针对去重元素进行排序return arr.sort((a,b) => {map.get(b) - map.get(a)}).slice(0,k)
};

使用桶排序

桶排序适用 top k中 频次题,计数排序适用 top k中 值的题

/*** @param {number[]} nums* @param {number} k* @return {number[]}*/// 桶排序 原理:1. 将数据滑倒到有限个桶里面,再将桶进行排序
// 用map存储频次,用数组表达桶,频次作为数据下表表达,针对不同的频次的熟悉,聚合
var topKFrequent = function(nums, k) {let map = new Map() // 定义一个map类型 // 一次遍历nums值,把他们出现的频次放在map里面nums.map(num => {if(map.has(num)){map.set(num,map.get(num) + 1)} else {map.set(num,1)}})if(map.size <=k ){return [...map.keys()]}return bucketSort(map,k)
};// 桶排序内容
const bucketSort = (map,k) => {let arr = [] let res = [] //结果// 针对map中每个元素遍历map.forEach((value,key) => {// 可以利用频次作为下标,降数据分配到桶里if(!arr[value]) {arr[value] = [key]} else {arr[value].push(key)} })// 倒序排列for(let i = arr.length -1 ; i >=0 && res.length < k ;i-- ){if(arr[i]){res.push(...arr[i]) }}return res
}

数组中的第K个最大元素

leetcode地址:https://leetcode.cn/problems/kth-largest-element-in-an-array/

给定整数数组 nums 和整数 k,请返回数组中第 k 个最大的元素。

请注意,你需要找的是数组排序后的第 k 个最大的元素,而不是第 k 个不同的元素。

你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。

示例 1:

输入: [3,2,1,5,6,4], k = 2
输出: 5

示例 2:

输入: [3,2,3,1,2,4,5,5,6], k = 4
输出: 4

提示:

1 <= k <= nums.length <= 10^5
-10^4 <= nums[i] <= 10^4

直接使用 javaScript API

/*** @param {number[]} nums* @param {number} k* @return {number}*/
var findKthLargest = function(nums, k) {nums.sort((a,b) => b-a ).slice(0,k)return nums[k -1]
};

使用快速排序

快速排序:本质是:拆分,分而治之

/*** @param {number[]} nums* @param {number} k* @return {number}*/
var findKthLargest = function(nums, k) {// 快速排序 分而治之// 1. 找到基准值// 1. 比他大的房右边,小的放左边// 3. 按照1 2 步骤继续拆分,直到找到下标// 创建指针,左右两端// 1. 左侧index 大于 右侧指针indexquickSort(nums)return nums[nums.length - k]
};// 快排
let quickSort = (arr) => {quick(arr,0,arr.length -1) // 基准:数组,起始值(开始指针),终止值(结束指针)
}const quick = (arr, left,right)=>{let index;if(left < right){index = partition(arr, left,right)// 左侧小于基准值if(left < index - 1){quick(arr,left,index - 1 )}if(index < right){quick(arr,index,right)}}
}// 找基准值
const partition = (arr, left,right)=>{let datum = arr[Math.floor(Math.random() * (right - left + 1)) + left] // 基准值let i = left // 左侧let j = right // 右侧while ( i <= j){ // 左侧while(arr[i] < datum){i ++ }// 右侧while(arr[j] > datum){j --}if( i <= j ){[arr[i],arr[j]] = [arr[j],arr[i]]  // 注意这里i+=1j-=1}}return i
}

扩展:桶排序

桶排序(Bucket Sort)是一种基于分治思想的排序算法。

它的基本思想是将要排序的数据分到几个有序的桶中,每个桶里的数据再单独进行排序。通常情况下,桶的数量是根据数据的分布情况来决定的。

桶排序的过程可以描述如下:

  1. 找出待排序数列中的最大值和最小值。
  2. 设置若干个桶,并将数据按照一定的规则放入对应的桶中。
  3. 对于每个非空桶,对其中的数进行排序。
  4. 将所有桶中的数据依次取出,组成有序数列。

桶排序的时间复杂度为O(n),但需要额外的空间来存储桶。在数据分布均匀的情况下,桶排序的效率很高,但如果数据分布不均匀,则可能会导致某些桶的大小远远超过其他桶,从而导致效率降低。

桶排序适用于数据范围不大的情况下,且数据分布均匀的情况下效率最高。在实际应用中,桶排序通常被用于外部排序,即当待排序数据无法全部载入内存时,先将数据分割成若干个能够装入内存的部分,对每部分进行排序,最后再将它们合并起来。

例子

下面举一个例子来说明桶排序的过程:

假设有一个待排序的数组[3, 6, 1, 8, 2, 5, 7, 4],现在我们要使用桶排序对其进行排序,具体步骤如下:

  1. 找出待排序数列中的最大值和最小值:最大值为8,最小值为1。
  2. 设置若干个桶,并将数据按照一定的规则放入对应的桶中。这里我们可以设置8个桶,每个桶的范围为[min + i * (max - min) / n, min + (i + 1) * (max - min) / n),其中n为桶的数量,i为桶的编号,min和max分别为待排序数列的最小值和最大值。按照这个规则,可以将待排序数组分到各个桶中,得到如下内容:
  • 桶1: [1, 2]
  • 桶2: [3, 4]
  • 桶3: [5]
  • 桶4: [6, 7]
  • 桶5: [8]
  1. 对于每个非空桶,对其中的数进行排序。这里可以使用插入排序等简单的排序算法对桶中的数据进行排序,得到如下内容:
  • 桶1: [1, 2] -> [1, 2]
  • 桶2: [3, 4] -> [3, 4]
  • 桶3: [5] -> [5]
  • 桶4: [6, 7] -> [6, 7]
  • 桶5: [8] -> [8]
  1. 将所有桶中的数据依次取出,组成有序数列。这里可以先将各个桶中的数据合并起来,得到一个有序的数组,即[1, 2, 3, 4, 5, 6, 7, 8]。

因此,桶排序的时间复杂度为O(n),但需要额外的空间来存储桶。在数据分布均匀的情况下,桶排序的效率很高,但如果数据分布不均匀,则可能会导致某些桶的大小远远超过其他桶,从而导致效率降低。

扩展:快速排序

快速排序(Quick Sort)是一种常用的排序算法,它通过将一个数组分割成两个子数组来进行排序。具体而言,快速排序选择一个基准元素(pivot),将数组中小于基准元素的元素放在基准元素的左边,大于基准元素的元素放在基准元素的右边,然后递归地对左右两个子数组进行排序。

快速排序的步骤:

  1. 选择基准元素(pivot),通常可以选择第一个元素、最后一个元素或者随机选择一个元素作为基准。
  2. 将数组划分为两个子数组:一个子数组中的元素都小于等于基准元素,另一个子数组中的元素都大于基准元素。这个过程称为分区(partition),可以使用双指针法实现。
  3. 对两个子数组分别进行递归排序,即重复步骤1和步骤2。
  4. 递归的基本情况是子数组的长度为0或1,此时可以认为子数组已经有序。
  5. 合并所有子数组的结果,得到最终的排序结果。

快速排序示例:

假设有一个待排序的数组[8, 4, 2, 9, 3, 5, 1, 6, 7],我们使用快速排序对其进行排序,具体步骤如下:

  1. 选择基准元素,可以选择第一个元素8。
  2. 使用双指针法将数组分为两个子数组:小于等于8的放在左边,大于8的放在右边。经过一次分区后,数组变为[4, 2, 3, 5, 1, 6, 7, 8, 9],此时基准元素8已经位于正确的位置。
  3. 对左侧子数组[4, 2, 3, 5, 1, 6, 7]和右侧子数组[9]分别进行递归排序。
  4. 对左侧子数组进行快速排序,选择基准元素4。经过一次分区后,左侧子数组变为[1, 2, 3, 4, 5, 6, 7],基准元素4位于正确位置。
  5. 对右侧子数组[9]进行递归排序,由于长度为1,无需处理。
  6. 合并左右子数组的结果,得到最终的排序结果:[1, 2, 3, 4, 5, 6, 7, 8, 9]。

快速排序的平均时间复杂度为O(nlogn),最坏情况下(当选择的基准元素总是数组中的最大或最小元素)的时间复杂度为O(n^2)。但由于其实现简单、性能优秀,在实际应用中被广泛使用。

这篇关于前端算法之堆--桶排序和快速排序的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/577844

相关文章

springboot security快速使用示例详解

《springbootsecurity快速使用示例详解》:本文主要介绍springbootsecurity快速使用示例,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝... 目录创www.chinasem.cn建spring boot项目生成脚手架配置依赖接口示例代码项目结构启用s

SpringBoot实现MD5加盐算法的示例代码

《SpringBoot实现MD5加盐算法的示例代码》加盐算法是一种用于增强密码安全性的技术,本文主要介绍了SpringBoot实现MD5加盐算法的示例代码,文中通过示例代码介绍的非常详细,对大家的学习... 目录一、什么是加盐算法二、如何实现加盐算法2.1 加盐算法代码实现2.2 注册页面中进行密码加盐2.

Vue中组件之间传值的六种方式(完整版)

《Vue中组件之间传值的六种方式(完整版)》组件是vue.js最强大的功能之一,而组件实例的作用域是相互独立的,这就意味着不同组件之间的数据无法相互引用,针对不同的使用场景,如何选择行之有效的通信方式... 目录前言方法一、props/$emit1.父组件向子组件传值2.子组件向父组件传值(通过事件形式)方

Java时间轮调度算法的代码实现

《Java时间轮调度算法的代码实现》时间轮是一种高效的定时调度算法,主要用于管理延时任务或周期性任务,它通过一个环形数组(时间轮)和指针来实现,将大量定时任务分摊到固定的时间槽中,极大地降低了时间复杂... 目录1、简述2、时间轮的原理3. 时间轮的实现步骤3.1 定义时间槽3.2 定义时间轮3.3 使用时

css中的 vertical-align与line-height作用详解

《css中的vertical-align与line-height作用详解》:本文主要介绍了CSS中的`vertical-align`和`line-height`属性,包括它们的作用、适用元素、属性值、常见使用场景、常见问题及解决方案,详细内容请阅读本文,希望能对你有所帮助... 目录vertical-ali

浅析CSS 中z - index属性的作用及在什么情况下会失效

《浅析CSS中z-index属性的作用及在什么情况下会失效》z-index属性用于控制元素的堆叠顺序,值越大,元素越显示在上层,它需要元素具有定位属性(如relative、absolute、fi... 目录1. z-index 属性的作用2. z-index 失效的情况2.1 元素没有定位属性2.2 元素处

Python实现html转png的完美方案介绍

《Python实现html转png的完美方案介绍》这篇文章主要为大家详细介绍了如何使用Python实现html转png功能,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 1.增强稳定性与错误处理建议使用三层异常捕获结构:try: with sync_playwright(

Vue 调用摄像头扫描条码功能实现代码

《Vue调用摄像头扫描条码功能实现代码》本文介绍了如何使用Vue.js和jsQR库来实现调用摄像头并扫描条码的功能,通过安装依赖、获取摄像头视频流、解析条码等步骤,实现了从开始扫描到停止扫描的完整流... 目录实现步骤:代码实现1. 安装依赖2. vue 页面代码功能说明注意事项以下是一个基于 Vue.js

CSS @media print 使用详解

《CSS@mediaprint使用详解》:本文主要介绍了CSS中的打印媒体查询@mediaprint包括基本语法、常见使用场景和代码示例,如隐藏非必要元素、调整字体和颜色、处理链接的URL显示、分页控制、调整边距和背景等,还提供了测试方法和关键注意事项,并分享了进阶技巧,详细内容请阅读本文,希望能对你有所帮助...

C++快速排序超详细讲解

《C++快速排序超详细讲解》快速排序是一种高效的排序算法,通过分治法将数组划分为两部分,递归排序,直到整个数组有序,通过代码解析和示例,详细解释了快速排序的工作原理和实现过程,需要的朋友可以参考下... 目录一、快速排序原理二、快速排序标准代码三、代码解析四、使用while循环的快速排序1.代码代码1.由快