第1个回答 2019-12-02
（1）交换类排序法
交换类排序法是指借助数据元素之间的互相交换进行排序的一种方法。冒泡排序法与快速排序法都属于交换类排序方法。
冒泡排序法是一种最简单的交换类排序方法，它是通过相邻数据元素的交换逐步将线性表变成有序。假设线性表的长度为n，则在最坏情况下，冒泡排序需要经过n/2遍的从前往后的扫描和n/2遍的从后往前的扫描，需要的比较次数为n(n–1)/2。但这个工作量不是必需的，一般情况下要小于这个工作量。
快速排序法也是一种交换类的排序方法，但由于它比冒泡排序法的速度快，因此称之为快速排序法。其关键是对线性表进行分割，以及对各分割出的子表再进行分割。
（2）插入类排序法
插入类排序法主要有简单插入排序法和希尔排序法。
简单插入排序法，是指将无序序列中的各元素依次插入到已经有序的线性表中。在这种排序方法中，每一次比较后最多移掉一个逆序，因此，这种排序方法的效率与冒泡排序法相同。在最坏情况下，简单插入排序需要n(n–1)/2次比较。
希尔排序法对简单插入排序做了较大的改进。它是将整个无序序列分割成若干小的子序列分别进行插入排序。希尔排序的效率与所选取的增量序列有关。在最坏情况下，希尔排序所需要的比较次数为O(n
1.5
)。
（3）选择类排序
选择类排序主要有简单选择类排序法和堆排序法。
简单选择排序法的基本思想是：扫描整个线性表，从中选出最小的元素，将它交换到表的最前面（这是它应有的位置）；然后对剩下的子表采用同样的方法，直到子表空为止。对于长度为n的线性表，在最坏情况下需要比较n(n–1)/2次。
堆排序法也属于选择类排序法。具有n个元素的序列（h
1
,
h
2
,
…,
h
n
），当且仅当满足条件：
或
(i=1,
2,
…,
n/2）时称之为堆。可见，堆顶元素（即第一个元素）必为最大项。
堆排序的方法对于规模较小的线性表并不适合，但对于较大规模的线性表来说是很有效的。在最坏情况下，堆排序需要比较的次数为O(nlog
2
n
)。