TypeScript选择排序如何实现
导读:本文共2222字符,通常情况下阅读需要7分钟。同时您也可以点击右侧朗读,来听本文内容。按键盘←(左) →(右) 方向键可以翻页。
摘要: 一. 选择排序的定义选择排序(Selection Sort)是一种简单的排序算法。它的基本思想是:首先在未排序的数列中找到最小(大)元素,然后将其存放到数列的起始位置;接着,再从剩余未排序的元素中继续寻找最小(大)元素,然后放到已排序序列的末尾。以此类推,直到所有元素均排序完毕。选择排序的主要优点与数据移动有关。如果某个元素位于正确的最终位置,则它不会被移动。选... ...
目录
(为您整理了一些要点),点击可以直达。一. 选择排序的定义
选择排序(Selection Sort)是一种简单的排序算法。
它的基本思想是:
首先在未排序的数列中找到最小(大)元素,然后将其存放到数列的起始位置;
接着,再从剩余未排序的元素中继续寻找最小(大)元素,然后放到已排序序列的末尾。
以此类推,直到所有元素均排序完毕。
选择排序的主要优点与数据移动有关。
如果某个元素位于正确的最终位置,则它不会被移动。
选择排序每次交换一对元素,它们当中至少有一个将被移到其最终位置上,因此对n个元素的表进行排序总共进行至多n-1次交换。
在所有的完全依靠交换去移动元素的排序方法中,选择排序属于非常好的一种。
选择排序的实现方式很简单,并且容易理解,因此它是学习排序算法的很好的入门途径。
二. 选择排序的流程
选择排序流程详细步骤:
首先将要排序的数组复制到一个新数组中,这样原数组不会被改变。
初始化最小数字的索引值为0,然后在数组中循环,在当前索引后面的元素中找到最小的数字的索引。
如果当前索引位置的数字不是最小数字,那么将这两个数字互换。
继续寻找下一个数字,直到索引到最后一个元素,此时整个数组已经是从小到大排序的了。
重复上面的步骤,每次排序的范围都会减少一个,直到整个数组排序完毕。
三. 选择排序的图解
四. 选择排序的代码
以下是 TypeScript 实现的选择排序代码:
functionselectionSort(arr:number[]):number[]{//循环遍历整个数组for(leti=0;i<arr.length;i++){//预设最小数的索引为当前循环的索引letminIndex=i;//在后面的数中寻找更小的数for(letj=i+1;j<arr.length;j++){if(arr[j]<arr[minIndex]){//如果找到更小的数,记录它的索引minIndex=j;}}//如果当前循环的索引不是最小数的索引,交换它们if(i!==minIndex){[arr[i],arr[minIndex]]=[arr[minIndex],arr[i]];}}//返回排序后的数组returnarr;}//测试数据consttestArr=[5,2,9,1,5,6];//调用插入排序函数constsortedArr=selectionSort(testArr);//打印结果console.log(sortedArr);
以下是代码的详细说明:
首先循环遍历整个数组。
在每一次循环中,预设最小数的索引为当前循环的索引。
在后面的数中寻找更小的数,如果找到更小的数,记录它的索引。
如果当前循环的索引不是最小数的索引,交换它们。
重复步骤2-4,直到遍历完整个数组。
返回排序后的数组。
五. 选择排序的时间复杂度
计算选择排序算法的时间复杂度,通常是通过分析算法中每一步的执行次数来确定的。
我们分析选择排序中的每一步,再将每一步的时间复杂度加起来,最后得到的就是选择排序的时间复杂度。
在选择排序中,最多的操作是内层循环,其执行了N-1次,并且每次执行内层循环都要花费O(N)的时间。
因此,内层循环的时间复杂度是O(N^2)。
外层循环也要执行N-1次,因此,它的时间复杂度也是O(N^2)。
所以,整个选择排序算法的时间复杂度是O(N^2)。
</div> <div class="zixun-tj-product adv-bottom"></div> </div> </div> <div class="prve-next-news">
TypeScript选择排序如何实现的详细内容,希望对您有所帮助,信息来源于网络。