JS手撕(十一) 选择排序、快速排序
JS手撕(十一) 选择排序、快速排序
选择排序
原理
选择排序原理就是每次从未排序序列中选择最小元素,放到已排序序列的末尾。
那么如何选择最小元素,并把最小元素放到已排序序列的末尾?
只需要遍历寻找最小的数,并保存最小数的索引。遍历完之后,让最小数和已排序序列的末尾互换位置即可。
图片来自菜鸟教程
JS实现
function selectSort(arr) {
const len = arr.length;
let minIndex; // 保存最小数的索引
for (let i = 0; i < len - 1; i++) { // 排好前n-1个,第n个数就是剩下的最大的。
minIndex = i; // 设置最小数的索引的默认值
for (let j = i + 1; j < len; j++) {
if (arr[j] < arr[minIndex]) {
// 遍历的数比之前村的最小数还小,更改最小数的索引位置
minIndex = j;
}
}
// 让最小数和已排序序列的末尾互换位置
[arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
}
return arr;
}
测试:
const selectSort = require('./sort.js');
let arr = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 26, 4, 19, 50, 48];
console.log(selectSort(arr))
性能
时间复杂度:O(n²)
排序稳定性:不稳定
这里第一次遇到不稳定的排序。稍微举例子说明一下为什么是不稳定的。
上面一开始2*
是在2
之后的,排序完之后2*
变成在2
之前了,所以选择排序是不稳定的。
它是不稳定的关键就是让最小数和已排序序列的末尾互换位置时
,可能把大小相同的数中在前面的移动到了后面去。
快速排序
原理
快速排序原理就是:
- 从数组中挑出一个元素,称为基准(
pivot
)。 - 将所有比基准值小的放在基准前面,所有比基准值大的放在放在基准后面。该操作称为分区操作(
partition
) - 递归地把小于基准值地子序列和大于基准值地子序列排序
图片来自菜鸟教程
JS实现
function quickSort(arr, l, r) {
if (l >= r) {
return;
}
const partionIndex = partition(arr, l, r);
// 递归排序小于基准值的子数列
quickSort(arr, l, partionIndex - 1);
// 递归排序大于基准值的子数列
quickSort(arr, partionIndex + 1, r);
return arr;
}
function partition(arr, l, r) {
let pivot = l;
let index = l + 1;
for (let i = index; i <= r; i++) {
if (arr[i] < arr[pivot]) {
// 把小于标杆的移到左边
[arr[index], arr[i]] = [arr[i], arr[index]];
index++;
}
}
// 标杆归位
[arr[index - 1], arr[pivot]] = [arr[pivot], arr[index - 1]];
// 返回标杆的位置
return index - 1;
}
测试:
优化
快速排序最坏的情况是初始序列已经有序,第一趟排序经过n-1
次比较后,第一个元素仍然在原来的位置,第二趟经过n-2
次比较厚,也还在原来的位置。依此类推,最后的总比较次数是(n-1) + (n-2) + ... + 1 = n(n-1)/2
。即最坏时间复杂度是O(n²)
。
至于如何改进,那就是随机取基准。因为上面是一直取第一位为基准,所以就导致了初始序列有序的情况下时间复杂度是O(n²)
。而随机取基准就能解决这种情况。
修改起来也很简单,只需要将partition
函数那里的pivot
修改成取随机数即可,不过还需要将arr[pivot]
和arr[l]
切换位置,并将pivot
设置为l
。因为整个算法的逻辑都是按第一位是基准来写的,所以还用之前的逻辑的话,只能随机取值,并把它换到第一位。
// partition函数开始部分
// [l, r]区间取随机数,注意是闭区间
let pivot = Math.floor(Math.random() * (r - l) + l);
[arr[l], arr[pivot]] = [arr[pivot], arr[l]];
pivot = l;
JS特殊实现
主要利用concat
方法能用来合并数组,所以使用concat
搭配递归调用就能很方便的实现。
function quickSort(arr) {
if (arr.length <= 1) {
// 递归退出条件
return arr;
}
// 随机取基准索引
const pivotIndex = Math.floor(Math.random() * (arr.length - 1));
// 基准值
const pivot = arr.splice(pivotIndex, 1)[0];
const left = [];
const right = [];
for (const item of arr) {
if (item < pivot) {
// 小于基准值的放在基准值左边
left.push(item);
} else {
right.push(item);
}
}
// 递归+concat实现子数组排序
return quickSort(left).concat(pivot, quickSort(right));
}
性能
时间复杂度:O(nlogn)
排序稳定性:不稳定。因为比基准值小的时候,需要换到基准值的左边,这里会引起相同值的相对位置的变换,所以快速排序是不稳定的。
相关文章
- js中数组排序的五种方式「建议收藏」
- js对数字数组排序[通俗易懂]
- html如何只刷新页面指定,js控制页面刷新 JS刷新当前页面的几种方法总结
- javascript中js实现导出CSV文件功能
- 前端面试题 --- JS高阶和其他
- Js生成二维码_js在线生成二维码
- js中四舍五入的方法_JS取整
- 多重排序 js「建议收藏」
- js forEach和 map 区别
- JS小技巧,如何使用内置函数对数组内容进行排序
- 利用 JS 实现 Redis 的连接(js连接redis)
- 使用JS技术实现Oracle数据库链接(js 链接 oracle)
- CSS和JS标签style属性对照表(方便js开发的朋友)
- JS自定义带默认值的函数
- JS重要知识点小结
- js排序动画模拟冒泡排序
- js事件(Event)知识整理
- js快速排序的实现代码
- js获取url参数代码实例分享(JS操作URL)
- js中数组排序sort方法的原理分析