TypeScript十大排序算法之选择排序实现示例详解

Nora ·
更新时间:2024-09-20
· 820 次阅读

目录

一. 选择排序的定义

二. 选择排序的流程

三. 选择排序的图解

四. 选择排序的代码

五. 选择排序的时间复杂度

六. 选择排序的总结

一. 选择排序的定义

选择排序(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)。

选择排序在数据规模较小时非常适用,在数据规模较大时不够高效。

以上就是TypeScript十大排序算法之选择排序实现示例详解的详细内容,更多关于TypeScript 选择排序算法的资料请关注软件开发网其它相关文章!



选择排序 选择 示例 TypeScript 排序算法 算法 排序

需要 登录 后方可回复, 如果你还没有账号请 注册新账号