选择排序javascript
简单选择排序是人们最熟悉的比较方式,其算法思想为:从数组的开头开始,将第一个元素和其他元素进行比较。检查完所有元素后,最小的元素会被放到数组的第一个位置,然后算法会从第二个位置继续。这个过程会一直进行,当进行到数组的倒数第二个位置时,所有的数据便完成了排序。
代码如下:
分析可得,简单选择排序的时间复杂度为O(n2)。选择排序的主要操作是进行关键字之间的比较,因此改进简单选择排序应该从如何减少比较出发。其实现实生活中就有一个很好的例子,就是比赛总的锦标赛。8个人中选出冠军其实不需要7+6+5=18场比赛,可以通过两两比较也就是11场比赛。这种方法叫做树形选择排序。
树形选择排序是一种按照锦标赛的思想进行选择排序的方法,首先对n个记录的关键字进行两两比较,然后在其中n/2个较小者之间再进行两两比较,直到找出最小关键字。可以通过一个完全二叉树来表示,由于含有n个结点的完全二叉树的深度为log2n+1,所以排序过程中每选择一个次小关键字仅需要log2n次操作,所以其时间复杂度O(nlog2n),但是这种排序有一种缺点就是占用空间大。
所以我们需要介绍一种更加优秀的排序,也就是堆排序。
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。