我是靠谱客的博主 可耐钢笔,这篇文章主要介绍js快速排序-(搬运+理解,从视频到文字),现在分享给大家,希望可以做个参考。

视频理解
快排思想:

  1. 选定Pivot中心轴
  2. 大于Pivot的放到Pivot右边
  3. 小于Pivot的放到Pivot左边
  4. 分别对Pivot的左右子序列重复以上操作(直到序列长度为 1)
  • 阮一峰版本:https://www.cnblogs.com/hjx-blog/articles/9183453.html
    选取数组中间位置为 pivot,两个容器 left=[]right=[]。遍历数组,把小于 pivot 的放到 left 容器中;把大于 pivot 的放到 right 容器中哦。
    基线条件:
    当数组长度≤1,结束递归
    递归操作:
  1. 找到 pivot
  2. 从数组中删除pivot
  3. 遍历数组,把小于pivot的放到left,大于pivot的放到right
  4. 拼接 left,pivot,right
    **返回值:**拼接后的数组
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
let arr = [49,38,65,97,76,13,27,49]; function quicksort(arr){ if(arr.length<=1) return arr; let pivotIndex = Math.floor(arr.length/2); let pivot = arr.splice(pivotIndex,1)[0]; let [left,right] = [[],[]]; for(let i=0;i<arr.length;i++){ if(arr[i]<=pivot){ left.push(arr[i]) }else{ right.push(arr[i]) } } return quicksort(left).concat(pivot,quicksort(right)) } console.log(quicksort(arr))

时间复杂度:应该也是 O(NlogN)
空间复杂度:O(N)。每次都要开辟 left,right 两个空间。
问题:生产环境中,每次都要开辟额外的内存空间,不可。

注意:arr.spice(从哪个索引开始删,删几个,替换1,替换2,....)
arr.spice() 方法会改变原数组
返回值是被删除的元素组成的数组!

  • 快排面试版本:
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
function quickSort(arr,left,right){ if(left>=right) return;//递归的基线条件 let i=left,j=right; pivot = arr[left]; while(i<j){//当 i<j 的时候,i,j 向中间靠拢,符合条件交换 while(i<j&&arr[j]>=pivot){//j从右向左寻找比pivot小的数 j-- } while(i<j&&arr[i]<=pivot){//i从左往右寻找比pivot大的数 i++ } [arr[i],arr[j]] = [arr[j],arr[i]];//交换位置 }//退出循环时,ij指向同一个数 [arr[left],arr[i]] = [arr[i],arr[left]];//记得把pivot放到中间 quickSort(arr,left,i-1); quickSort(arr,i+1,right); return arr; } console.log(quickSort(arr,0,arr.length-1))

时间复杂度:O(NlogN)。空间复杂度:原地交换,O(1)

快排复杂度

  • 最优:O(NlogN)。每次取到的元素刚好可以平分整个数组。 参考:

时间复杂度: T [ n ] = 2 T [ n / 2 ] + f ( n ) T[n] = 2T[n/2] + f(n) T[n]=2T[n/2]+f(n)
T[n/2] - 平分后,子数组所花费的时间复杂度;f(n) - 平分这个数组所花费的时间
第一次递归: T [ n ] = 2 T [ n / 2 ] + n T[n] = 2T[n/2] + n T[n]=2T[n/2]+n
第二次递归: T [ n ] = 2 ∗ 2 ( T [ n / 4 ] + n / 2 ) + f ( n ) T[n] = 2*2(T[n/4]+n/2) + f(n) T[n]=22(T[n/4]+n/2)+f(n) = 2 2 T [ n / 2 2 ] + 2 n 2^2T[n/{2^2}]+2n 22T[n/22]+2n
第三次递归: 2 3 T [ n / 2 3 ] + 3 n 2^3T[n/{2^3} ] + 3n 23T[n/23]+3n
第 m 次递归: 2 m T [ n / 2 m ] + m n 2^mT[n/{2^m} ] + mn 2mT[n/2m]+mn
到 T(1) 不能再分。所以 n / 2 m = 1 n/{2^m} =1 n/2m=1
m = l o g n m=logn m=logn
T[n] = 2^m T[1] + mn ;其中m = logn;
= nT[1] + nlogn = n + nlogn;根据曲线图,nlogn 远大于 n,所以取 nlogn

  • 最差: O ( N 2 ) O(N^2) O(N2)。每次取到的 pivot 是数组中最大/最小那个元素。这种情况就是冒泡排序了,每次只能排好一个元素的顺序。

最后

以上就是可耐钢笔最近收集整理的关于js快速排序-(搬运+理解,从视频到文字)的全部内容,更多相关js快速排序-(搬运+理解内容请搜索靠谱客的其他文章。

本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
点赞(70)

评论列表共有 0 条评论

立即
投稿
返回
顶部