一. 抉择排序的定义
抉择排序（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多平台公布