山东公务员考试网计算机常识-选择类排序法

１、 简单选择排序法

基本思想：扫描整个线性表，从中选出最小的元素，将它交换到表的最前面；然后对剩下的子表采用同样的方法，直到子表空为止。

简单选择排序法在最坏情况下需要比较n(n-1)/2/次。

２、 堆排序法

方法：（1）首先将一个无序序列建成堆。

（2）然后将堆顶元素（序列中的最大项）与堆中最后一个元素交换（最大项应该在序列的最后）。不考虑已经换到最后的那个元素，只考虑前n-1个元素构成的子序，显然，该子序列已不是堆，但左、右子树仍为堆，可以将该子序列调事为堆。反复做第（2）步，真到剩下的子序列为空为止。适用规模较大的线性表，在最坏情况下，堆排序需要比较的次数为O（nlog2n）。

更多精彩资讯请关注查字典资讯网，我们将持续为您更新最新资讯!