共计 1693 个字符，预计需要花费 5 分钟才能阅读完成。
前言
欢送关注『前端进阶圈』公众号，一起摸索学习前端技术 ……
前端小菜鸡一枚，分享的文章纯属个人见解，若有不正确或可待探讨点可随便评论，与各位同学一起学习~
排序算法 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 中有哪些非破坏性办法？
-
热点面试题：协商缓存和强缓存的了解及区别？
最初：
- 欢送关注『前端进阶圈』公众号，一起摸索学习前端技术 ……
- 公众号回复 加群 或 扫码, 即可退出前端交流学习群，长期交流学习 ……
- 公众号回复 加好友，即可添加为好友
正文完