TypeScript 算法手册【选择排序】
文章目录
- 1. 选择排序简介
- 1.1 选择排序定义
- 1.2 选择排序特点
- 2. 选择排序步骤过程拆解
- 2.1 找到最小元素
- 2.2 交换元素
- 2.3 重复过程
- 3. 选择排序的优化
- 3.1 双向选择排序
- 3.2 使用堆数据结构
- 案例代码和动态图
- 4. 选择排序的优点
- 5. 选择排序的缺点
- 总结
【 已更新完 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 算法手册 【插入排序】