算法之选择排序技术

本文主要是介绍算法之选择排序技术，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

　　选择排序主要是每一趟从待排序列中选取一个关键码最小的记录，也即第1趟从n个记录中选取关键码最小的记录，第2趟从剩下的n-1个记录中选取关键码最小的记录知道整个序列的记录选完。这样，由选取记录的顺序便得到按关键码有序的序列。

　　1、简单选择排序

　　　　简单选择排序的过程为：第1趟，从n个记录中找出关键码最小的记录与第1个记录交换；第2趟，从第2个记录开始的n-1个记录中再选出关键码最小的记录与第2个记录交换；如此类推，第i趟，则从第i个记录开始的n-i+1个记录中选出关键码最小的记录与第i个记录交换知道整个序列按关键码有序。其具体过程如下图示：有排序表“25 36 30 36 10 56 12”　　

 　　　　具体算法如下：

 　　2、树结构选择排序

　　　　树结构选择排序是按照锦标赛的思想进行的，首先将n个参赛的选手通过n/2次两两比较，再从n/2个胜者中进行两两比较，如此重复知道选择除胜者(如最大)。这个过程可用一个具有n个叶子结点的完全二叉树来表示，则该完全二叉树有2n-2或2n-1个结点。接下来，将第一名的结点看成成绩最差的，并从该结点(叶子位置)开始沿该结点到跟路径上一次进行各分支结点子女间的比较，胜出的就是第二名。因为与其比赛的均是刚刚输给第一名的选手。如此，继续进行下去，知道所有选手的名次排定。下面示例说明：

　　　　16个选手比赛，如下图所示，该方法占用空间较多，除需输出排序结果的n个单元外，尚需n-1个辅助单元。

　　　　产生第一名的过程：

 　　　　产生第二名的过程：

 　　　　具体算法如下：

 　　　　以上算法还可以试着优化。

　　3、堆排序

　　　　简单选择排序的思想简单易于实现，但其时间性能没有优势。因为在每趟选择中并没有把前面选择过程中的一些有用信息继承下来，因此每趟选择都是顺序地一一进行。如果能改善这一点则定会减少比较次数提供排序效率——堆排序算法就实现了这点。

 　　　　此处堆的定义为：设有n个元素的序列，当且仅当满足下述关系之一时，称之为堆。

　　　　　　，其中，前者称为小顶堆，后者称为大顶堆。

　　　　例如，序列12 36 24 85 47 30 53 91是一个小顶堆；序列91， 47 85 24 36 53 30 16是一个大顶堆。

　　　　一个有n个元素的序列是否是堆，可以和一棵完全二叉树对应起来，i和2i、2i+1的关系就是舒安琪逾期左、右孩子之间的位置关系(i=1, 2, ……，n/2)。因此，通常用完全二叉树的形式来直观地描述一个堆。以下两图分别对应上例用的小顶堆和大顶堆：

未完，待续……

这篇关于算法之选择排序技术的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！