2011计算机等级考试二级公共基础知识要点(8)

会计考友

　1.8 排序技术　　排序是指将一个无序序列整理成按值非递减顺序排列的有序序列。
7 t5 d8 b! f( Z; Q, r　　交换类排序法：
　　(1)冒泡排序法，需要比较的次数为n(n-1)/2;
　　(2)快速排序法。
　　插入类排序法：
　　(1)简单插入排序法，最坏情况需要n(n-1)/2次比较;
. m- p% K, t  P  U/ M  P) ?　　(2)希尔排序法，最坏情况需要O(n1.5)次比较。
  O2 m2 O* q4 V　　选择类排序法：
　　(1)简单选择排序法, 最坏情况需要n(n-1)/2次比较;
/ z& C* `6 |# }" i: g　　(2)堆排序法，最坏情况需要O(nlog2n)次比较。