NCRE计算机二级公共基础知识——排序

NCRE计算机二级公共基础知识——排序

【考点17】排序

1、交换排序

（1）冒泡排序法，在最坏的情况下，冒泡排序需要比较次数为n(n－1)/2。

（2）快速排序法 ，在最坏的情况下，快速排序需要比较次数为n(n－1)/2。

2、插入类排序法：

（1）简单插入排序法，最坏情况需要n(n-1)/2次比较；

（2）希尔排序法，最坏情况需要O(n1.5)次比较。（大写O是算法复杂度的表示方法）

3、选择类排序法：

（1）简单选择排序法，最坏情况需要n(n-1)/2次比较；

（2）堆排序法，最坏情况需要O(nlog2n)次比较。

相比以上几种(除希尔排序法外)，堆排序法的时间复杂度最小。