TypeScript 算法手册【选择排序】
文章目录
【 已更新完 TypeScript 设计模式 专栏,感兴趣可以关注一下,一起学习交流🔥🔥🔥 】
1. 选择排序简介
1.1 选择排序定义
选择排序是一种简单直观的排序算法。它的工作原理是: 在未排序序列中找到最小(大)元素,存放到排序序列的起始位置,再从剩余未排序元素中继续寻找最小(大)元素,接着放到已排序序列的末尾。以此类推,直到所有元素均排序完毕。
假设你有一堆扑克牌需要整理,你会怎么做呢,你可能会先找出最小的牌,放在最左边,在剩下的牌中再找最小的,放在第二个位置,如此反复。这就是选择排序的基本思想。
用 TypeScript 代码表示一个简单的选择排序:
function selectionSort(arr: number[]): number[] {
const len = arr.length;
for (let i = 0; i < len - 1; i++) {
let minIndex = i;
for (let j = i + 1; j < len; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
if (minIndex !== i) {
[arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
}
}
return arr;
}
1.2 选择排序特点
- 简单直观: 选择排序的思想非常简单,容易理解和实现
- 不稳定性: 选择排序是不稳定的排序算法
- 原地排序: 选择排序是原地排序算法,不需要额外的存储空间
- 比较次数固定: 无论输入如何,选择排序的比较次数都是固定的
2. 选择排序步骤过程拆解
2.1 找到最小元素
// 找到最小元素的索引
let minIndex = i;
for (let j = i + 1; j < len; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
这个步骤就像在一堆扑克牌中找出最小的牌,你需要一张一张比较,记住最小的牌的位置。
2.2 交换元素
// 交换元素
if (minIndex !== i) {
[arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
}
找到最小的牌后,你会把它放到最左边,也就是与当前位置的牌交换。
2.3 重复过程
// 重复查找和交换
for (let i = 0; i < len - 1; i++) {
// ... 查找最小元素和交换的代码 ...
}
你会重复这个过程,每次都在剩下的牌中找最小的,直到所有的牌都排好序。
3. 选择排序的优化
3.1 双向选择排序
function doubleSelectionSort(arr: number[]): number[] {
let left = 0;
let right = arr.length - 1;
while (left < right) {
let minIndex = left;
let maxIndex = right;
for (let i = left; i <= right; i++) {
if (arr[i] < arr[minIndex]) {
minIndex = i;
}
if (arr[i] > arr[maxIndex]) {
maxIndex = i;
}
}
[arr[left], arr[minIndex]] = [arr[minIndex], arr[left]];
if (maxIndex === left) {
maxIndex = minIndex;
}
[arr[right], arr[maxIndex]] = [arr[maxIndex], arr[right]];
left++;
right--;
}
return arr;
}
这个优化版本就像你同时从牌堆的两端开始整理,一次找出最小和最大的两张牌,分别放到最左和最右。这样可以减少循环的次数,提高效率。
3.2 使用堆数据结构
虽然这已经超出了选择排序的范畴,但值得一提的是,如果我们使用堆数据结构来选择最小(或最大)元素,可以将时间复杂度从O(n^2)降低到O(nlogn)。这就是著名的堆排序算法。
案例代码和动态图
const array = [40, 25, 12, 22, 11];
const sortedArray = selectionSort(array);
console.log(sortedArray); // [11, 12, 22, 25, 40]
4. 选择排序的优点
- 代码简单,易于理解和实现
- 对于小规模的数据,性能还不错
- 交换次数少: 每次交换都会把一个元素放到它最终的位置,因此交换次数最多为n-1次
5. 选择排序的缺点
- 时间复杂度较高,为O(n^2)
- 不稳定: 相同元素的相对位置可能会发生变化
- 对于大规模数据,性能不佳
总结
选择排序虽然简单,在实际应用中并不常用,它的时间复杂度较高。理解选择排序的原理对于学习更复杂的排序算法很有帮助。它就像是排序算法中的"Hello World",是我们理解排序思想的第一步。
选择排序教会我们:最简单的方法虽然不是最快的,但是直观、容易理解,在某些特定场景下(如数据量小,或者交换操作成本很高时),选择排序可能是一个不错的选择。
在编程世界里,没有绝对的好与坏,只有合适与否,理解每种算法的特点,才能在实际应用中做出最佳选择。
喜欢的话就点个赞 ❤️,关注一下吧,有问题也欢迎讨论指教。感谢大家!!!
下期预告: TypeScript 算法手册 【插入排序】
原文地址:https://blog.csdn.net/bobostudio1995/article/details/142667310
免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!