Js算法中的排序 |
您所在的位置：网站首页 › js实现快速排序算法 › Js算法中的排序 |
Js算法中的排序
|
前言
关于JavaScript排序的算法有很多种，看下面图主要描述了一些排序算法的基本情况： 本文主要讲解Js排序中的冒泡和快速排序。 Sortsort是数组自带的一种排序方法，可以直接调用 let arr = [5, 3, 2, 4, 1] //升序排序 arr.sort((a, b) => { return a - b }) //return b-a; —> 降序排序 // console.log(arr);//[1,2,3,4,5] 冒泡排序 原理 比较相邻的元素。如果第一个比第二个大，就交换它们两个； 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数； 针对所有的元素重复以上的步骤，除了最后一个； 重复步骤1~3，直到排序完成。 代码实现 function bubbleSort(arr) { const len = arr.length //外层循环，每一次找到一个最大值 for (let i = 0; i < len; i++) { //内层循环，判断两个数的大小 for (let j = i + 1; j < len; j++) { if (arr[i] > arr[j]) { //解构赋值 [arr[i], arr[j]] = [arr[j], arr[i]] } } } return arr } 时间复杂度和空间复杂度时间复杂度：O(n^2) 空间复杂度： 0 图解用解构和API实现排序 function mySort(arr) { //定义一个空数组 let res = [] while (arr.length) { let min = Math.min(...arr)//找到最小值 res.push(min)//往空数组push进去每次找到的最小值 arr.splice(arr.indexOf(min), 1)//移除最小值，导致数组长度减一 } return res }上述代码时间复杂度：O(n^2) 空间复杂度：O(n) 时间复杂度和冒泡排序一样，开辟了新的空间。 快速排序 原理 从数组中选择一个"基准",所有比基准小的元素放在基准前面, 比基准大的元素放在基准的后面。 代码实现 let arr = [5, 1, 3, 6, 2, 0, 7] function quickSort(arr, left = 0, right = arr.length - 1) { if (arr.length > 1) { //帮我找分裂数组的下标 const lineIndex = partition(arr, left, right) if (left < lineIndex - 1) { quickSort(arr, left, lineIndex - 1) } if (lineIndex < right) { quickSort(arr, lineIndex, right) } } return arr } //将比基准值小的放在左边，比基准值大的放在右边 function partition(arr, left, right) { let piovtValue = arr[Math.floor((left + (right - left)) / 2)] let i = left, j = right while (i piovtValue) { j-- } if (i |
【本文地址】
今日新闻 |
推荐新闻 |