前言
欢送关注 『前端进阶圈』 公众号 ，一起摸索学习前端技术......
前端小菜鸡一枚，分享的文章纯属个人见解，若有不正确或可待探讨点可随便评论，与各位同学一起学习~
排序算法 Quick Sort
原理
- 疾速排序在每一轮筛选一个基准元素，并让其余比基准元素大的元素移到数列的一遍，比基准元素小的元素挪动数列的另一边，从而把数列拆解成两局部。
- 工夫复杂度为：O(n log n)
- 每一轮的比拟和替换，须要把数组的全副元素都遍历一遍，工夫复杂度为 O(n),这样的遍历须要多少轮呢？如果元素个数为 n，那么均匀状况下须要 log n 轮。
基准元素的抉择
- 基准元素: pivot，在分治过程中，以基准元素为核心，把他的元素挪动到他的左右两边。
- 可应用随机抉择一个元素作为基准元素，让基准元素和数列首元素替换地位。这样能够无效地将数列分成两个局部，然而也有极小的几率会抉择数列的最大值和最小值，会影响分治的成果。
- 工夫复杂度为：O(n log n),最坏状况为：O(n²)
元素的替换
- 选定好基准元素后，前面就是把小于基准元素的替换到基准元素的一遍，把大于基准元素的元素都替换到基准元素的另一边。
可应用的办法：
- 双边循环法
- 单边循环法
双边循环法：抉择一个基准元素，并设置两个指针 left 和 right，指向最左或最右的连个元素。
- 执行循环，从 right 指针开始，让指针指向的元素跟基准元素做比拟，如果大于或等于 pivot,则指针向挪动，如果小于 pivot，则 right 指针进行挪动，切换到 left 指针。
单边循环法
- 单边循环法：首先选定基准元素 pivot，同时，设置一个 mark 指针指向数列的起始地位，这个 mark 指针代表小于基准元素的区域边界。如果遍历到的元素大于基准元素，就持续往后遍历。如果遍历到的元素小于基准元素，把 mark 的指针右移一位，因为小于 pivot 的区域边界增大了。第二让最新遍历到的元素和 mark 指针所在的地位的元素替换地位。因为最新遍历到的元素属于小于 pivot 的区域。
Array.prototype.quickSort = function () { // 递归函数 let rec = (arr) => { // 边界条件 if (arr.length <= 1) return arr; // 分区数组 let left = []; let right = []; // 基准元素 let mid = arr[0]; // 循环遍历 for (let i = 1; i < arr.length; i++) { // 比基准小的元素放在基准后面 left，否则放在基准前面 right if (arr[i] < mid) { left.push(arr[i]); } else { right.push(arr[i]); } } // 递归调用两遍的子数组 return [...rec(left), mid, ...rec(right)]; }; // 初始化递归函数 let res = rec(this); res.forEach((item, index) => { this[index] = item; });};let arr = [98, 4, 6, 84, 42, 8674, 434, 56, 465];arr.quickSort();console.log(arr);文章特殊字符形容：
- 问题标注
Q:(question) - 答案标注
R:(result) - 注意事项规范：
A:(attention matters) - 详情形容标注：
D:(detail info) - 总结标注：
S:(summary) - 剖析标注：
Ana:(analysis) - 提醒标注：
T:(tips)
往期回顾：
- 热点面试题：浏览器和Node的宏工作和微工作？
- 这是你了解的CSS选择器权重吗？
- 热点面试题：JS 中 call, apply, bind 概念、用法、区别及实现？
- 热点面试题： 罕用位运算办法？
- Vue数据监听Object.definedProperty()办法的实现
- 热点面试题：Virtual DOM 相干问题？
- 热点面试题： Array中有哪些非破坏性办法？
热点面试题：协商缓存和强缓存的了解及区别？
最初：
- 欢送关注 『前端进阶圈』 公众号 ，一起摸索学习前端技术......
- 公众号回复 加群 或 扫码, 即可退出前端交流学习群，长期交流学习......
- 公众号回复 加好友，即可添加为好友