共计 1507 个字符，预计需要花费 4 分钟才能阅读完成。
一. 抉择排序的定义
抉择排序（Selection Sort）是一种简略的排序算法。
它的根本思维是：
- 首先在未排序的数列中找到最小（大）元素，而后将其寄存到数列的起始地位；
- 接着，再从残余未排序的元素中持续寻找最小（大）元素，而后放到已排序序列的开端。
- 以此类推，直到所有元素均排序结束。
抉择排序的次要长处与数据挪动无关。
- 如果某个元素位于正确的最终地位，则它不会被挪动。
- 抉择排序每次替换一对元素，它们当中至多有一个将被移到其最终地位上，因而对 n 个元素的表进行排序总共进行至少 n - 1 次替换。
- 在所有的齐全依附替换去挪动元素的排序办法中，抉择排序属于十分好的一种。
抉择排序的实现形式很简略，并且容易了解，因而它是学习排序算法的很好的入门路径。
二. 抉择排序的流程
抉择排序流程具体步骤：
- 首先将要排序的数组复制到一个新数组中，这样原数组不会被扭转。
- 初始化最小数字的索引值为 0，而后在数组中循环，在以后索引前面的元素中找到最小的数字的索引。
- 如果以后索引地位的数字不是最小数字，那么将这两个数字调换。
- 持续寻找下一个数字，直到索引到最初一个元素，此时整个数组曾经是从小到大排序的了。
- 反复下面的步骤，每次排序的范畴都会缩小一个，直到整个数组排序结束。
三. 抉择排序的图解
四. 抉择排序的代码
以下是 TypeScript 实现的抉择排序代码：
function selectionSort(arr: number[]): number[] {
// 循环遍历整个数组
for (let i = 0; i < arr.length; i++) {
// 预设最小数的索引为以后循环的索引
let minIndex = i;
// 在前面的数中寻找更小的数
for (let j = i + 1; j < arr.length; j++) {if (arr[j] < arr[minIndex]) {
// 如果找到更小的数，记录它的索引
minIndex = j;
}
}
// 如果以后循环的索引不是最小数的索引，替换它们
if (i !== minIndex) {[arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
}
}
// 返回排序后的数组
return arr;
}
// 测试数据
const testArr = [5, 2, 9, 1, 5, 6];
// 调用插入排序函数
const sortedArr = selectionSort(testArr);
// 打印后果
console.log(sortedArr);以下是代码的具体阐明：
- 首先循环遍历整个数组。
- 在每一次循环中，预设最小数的索引为以后循环的索引。
- 在前面的数中寻找更小的数，如果找到更小的数，记录它的索引。
- 如果以后循环的索引不是最小数的索引，替换它们。
- 反复步骤 2 -4，直到遍历残缺个数组。
- 返回排序后的数组。
五. 抉择排序的工夫复杂度
计算抉择排序算法的工夫复杂度，通常是通过剖析算法中每一步的执行次数来确定的。
咱们剖析抉择排序中的每一步，再将每一步的工夫复杂度加起来，最初失去的就是抉择排序的工夫复杂度。
-
在抉择排序中，最多的操作是内层循环，其执行了 N - 1 次，并且每次执行内层循环都要花费 O(N) 的工夫。
- 因而，内层循环的工夫复杂度是 O(N^2)。
-
外层循环也要执行 N - 1 次，因而，它的工夫复杂度也是 O(N^2)。
- 所以，整个抉择排序算法的工夫复杂度是 O(N^2)。
六. 抉择排序的总结
- 抉择排序是一种简略易懂的排序算法。
- 它的根本思维是遍历整个列表，每次找出最小的元素，并且将它移到列表的最右边，反复这个过程直到整个列表都有序排列。
- 在均匀状况下，抉择排序的工夫复杂度为 O(n^2)，在最坏状况下与最好状况下都为 O(n^2)。
- 抉择排序在数据规模较小时十分实用，在数据规模较大时不够高效。
本文由 mdnice 多平台公布
正文完