1.1.8　排序技术

排序是指将一个无序序列整理成按值非递减顺序排列的有序序列。

1.交换类排序法

①冒泡排序法：对于长度为n的线性表，最坏情况下，需要比较n（n-1）/2次。

②快速排序法：对于长度为n的线性表，最坏情况下，需要比较nlog2n次。

2.插入类排序法

①简单插入排序法：对于长度为n的线性表，最坏情况下，需要比较n（n-1）/2次。

②希尔排序法：对于长度为n的线性表，最坏情况下，需要比较n1.5次。

3.选择类排序法

①简单选择排序法：对于长度为n的线性表，最坏情况下，需要比较n（n-1）/2次。

②堆排序法：对于长度为n的线性表，最坏情况下，需要比较nlog2n次。

4.各种排序比较（见表1-1-1）

表1-1-1　各种排序比较