JavaScript实现的选择排序算法实例分析

代码如下：

分析可得，简单选择排序的时间复杂度为

O（n2）

树形选择排序是一种按照锦标赛的思想进行选择排序的方法，首先对n个记录的关键字进行两两比较，然后在其中n/2个较小者之间再进行两两比较，直到找出最小关键字。可以通过一个完全二叉树来表示，由于含有n个结点的完全二叉树的深度为log2n+1，所以排序过程中每选择一个次小关键字仅需要log2n次操作，所以其时间复杂度

O（nlog2n）

所以我们需要介绍一种更加优秀的排序，也就是堆排序。

附：

堆排序算法

堆排序只需要一个记录大小的辅助空间，每个待排序的记录仅占用一个存储空间。

堆排序利用了大根堆（或小根堆）堆顶记录的关键字最大（或最小）这一特征，使得当前无序区中选取最大（或最小）关键字的记录变得简单。我们以大跟堆为例子，排序的基本操作如下：

首先是建堆，建堆就是不断调整堆的过程，从len2处开始调整，一直到第一个节点，此处len是堆中元素的个数。建堆的过程是线性的过程，从len2到0处一直调用调整堆的过程，建堆的时间复杂度为O（n）。 接下来是调整堆，调整堆在建堆和堆排序的过程中都会用到，利用的思想是比较节点i和它的孩子节点left(i)和right(i)，选出三者最大（或最小）者，如果最大（小）值不是节点i而是它的一个子节点，那么交换两个节点，然后继续递归。 然后是堆排序：

1个节点继续进行堆调整的过程，然后再讲根节点取出，直到所有结点取出。

O(log2n)

下面模拟建堆的过程：

堆排序对于记录数较少的文件并不值得提倡，但是对于n较大的文件还是挺有效的。

更多关于JavaScript相关内容感兴趣的读者可查看本站专题：《》、《》、《》、《》、《》及《》

以上是大佬教程为你收集整理的JavaScript实现的选择排序算法实例分析全部内容，希望文章能够帮你解决JavaScript实现的选择排序算法实例分析所遇到的程序开发问题。

如果觉得大佬教程网站内容还不错，欢迎将大佬教程推荐给程序员好友。

本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。