序序列。
排序的方法有很多，根据待排序序列的规模以及对数据处理的要求，可以采用不同的排序方法。现介绍一些常用的排序方法。
排序可以在各种不同的存储结构上实现。现介绍的方法中，其排序的对象一般认为是顺序存储的线性表，在程序设计语言中就是一维数组。
*考点21 交换类排序法 重点
交换排序法是指借助数据元素之间的互相交换进行排序的一种方法。
冒泡排序法与快速排序法都属于交换类的排序方法。
1．冒泡排序法
冒泡排序法是一种最简单的交换类类排序法，它是通过相邻数据元素的交换逐步将线性表变成有序。
冒泡排序法的基本过程如下：
首先，从表头开始往后扫描线性表，在扫描过程中逐次比较相邻两个元素的大小。若相邻两个元素中，前面的元素大于后面的元素，则将它们互换，称为消去了一个逆序。显然，在扫描过程中，不断地将两相邻元素中的大者往后移动，最后就将线性表中的最大者换到了表的最后，这也是线性表中最大元素应有的位置。
然后，从后到前扫描剩下的线性表，同样，在扫描过程中逐次比较相邻两个元素的大小。若相邻两个元素中，后面的元素小于前面的元素，则将它们互换，这样就又消去了一个逆序。显然，在扫描过程中，不断地将两相邻元素中的小者往前移动，最后就将线性表中的最小者换到了表的最前面，这也是线性表中最小元素应有的位置。
对剩下的线性表重复上述过程，直到剩下的线性表变空为止，此时的线性表已经变为有序。
在上述排序过程中，对线性表的每一次来回扫描后，都将其中的最大者沉到了表的底部，最小者象气泡一样冒到表的前头。
冒泡排序又称下沉排序。
假设线性表的长度为n，则在最坏情况下，冒泡排序需要经过n/2遍的从前往后的扫描和n/2遍的从后往前的扫描，需要比较次数为n(n-1)/2。 重点
例：把下面的序列按冒泡排序法排好序。图中方框位置表示扫描过程中最后一次发生交换的位置。
原序列 5 1 7 3 1 6 9 4 2 8 6
第1遍(从前往后) 5 1 7 3 1 6 9 4 2 8 6 结果 1 5 3 1 6 7 4 2 8 6 9
(从后往前) 1 5 3 1 6 7 4 2 8 6 9 结果 1 1 5 3 2 6 7 4 6 8 9 第2遍…
最后得到： 1 1 2 3 4 5 6 6 7 8 9
2．快速排序法 了解
在前面所讨论的冒泡排序法中，由于在扫描过程中只对相邻两个元素进行比较，因此，在互换两个相邻元素时，只能消除一个逆序。如果通过两个（不是相邻）的元素的互换，能够消除线性表中的多个逆序，就会大大加快排序的速度。显然，为了通过一次交换能消除多个逆序，就不能象冒泡排序法那样对相邻两个元素进行交换，从而只能消除一个逆序。
快速排序法也是一种互换类的排序方法，但由于它比冒泡排序法的速度快，因此称之为快速排序法。
快速排序法的关键是对线性表进行分割，对各分割的子表再进行分割。
基本思想是：
对于长度为n的线性表,在最坏的情况下,快速排序法需要比较的次数为：n(n-1)/2。
因为：对排好序的线性表进行快速排序法是快速排序的最坏情况。
平均时间为：O(nlog2n)
最坏情况：n(n-1)/2，即O(n2)
*考点22 插入类排序法 重点
所谓插入排序，是指将无序序列中的各元素依次插入到已经有序的线性表中。
1．简单插入排序法
简单插入排序法是把待排序的元素看成一个有序表和一个无序表，开始时有序表中只包含一个元素，无序表中包含有n-1个元素，排序过程中每次从无序表中取出第一个元素，把它的排序码依次与有序表元素的排序码进行比较，将其插入到有序表中的适当位置，使之成为新的有序表。
从后往前比较，然后插入。
在简单插入排序法中，每一次比较后最多移掉一个逆序，因此这种排序方法的效率与冒泡排序法相同。在最坏情况下，简单插入排序需要n(n-1)/2次比较。
有序序列 比较前的无序序列
5 1 7 3 1 6 9
5 1 7 3 1 6 9 1 5 7 3 1 6 9 1 5 7 3 1 6 9 1 3 5 7 1 6 9 1 1 3 5 7 6 9
1 1 3 5 6 7 9 1 1 3 5 6 7 9 结果 2．希尔排序法
希尔排序法（Sehll Sort）属于插入类排序，但它对简单插入排序做了较大的改进。
希尔排序法的基本思想如下：
将整个无序序列分割成若干小的子序列分别进行插入排序。 子序列的分割方法如下：
将相隔某个增量h的元素构成一个子序列。在排序过程中，逐次减小这个增量，最后当h减到1时，进行一次插入排序，就完成了排序。增量序列一般取ht=n/2k(k=1,2,…,?log2n?)，其中n为待排序序列的长度。
在希尔排序过程中，虽然对于每一个子表采用的仍是插入排序，但是在子表中每进行一次比较就有可能移去整个线性表的多个逆序，从而改变整个排序过程的性能。
希尔排序的效率与所选取的增量序列有关。如果选取上述增量序列，则在最坏情况下，希尔排序所需要的比较次数为：O(n1.5) 即：n1.5=n3/2= nn
*考点23 选择类排序法 重点
1．简单选择排序法
选择排序法的基本思想如下：
扫描整个线性表，从中选出最小的元素，将它交换到表的最前面（这是它应有的位置）；然后，对剩下的子表采用同样的方法，直到子表空为止。
对于长度为n的序列，选择排序需要扫描n-1遍，每一遍扫描均从剩下的子表中选出最小的元素，然后将该最小的元素与子表中的第一个元素进行交换。
例：下图是简单选择排序法的示意图，图中有方框的元素是刚被选出来的最小元素。
原序列： 89 21 56 48 85 16 19 47 第1篇选择 16 21 56 48 85 89 19 47 第2篇选择 16 19 56 48 85 89 21 47
重点
第3篇选择 16 19 21 48 85 89 56 47 第4篇选择 16 19 21 47 85 89 56 48 第5篇选择 16 19 21 47 48 89 56 85 第6篇选择 16 19 21 47 48 56 89 85 第7篇选择 16 19 21 47 48 56 85 89 简单选择排序法示意图
简单选择排序法在最坏情况下需要比较n(n-1)/2次。
2．堆排序法
堆排序法属于选择类的排序方法： 堆的定义如下：
具有n个元素的序列（h1, h2,…, hn），当且仅当满足
?hi?h2i ?h?h2i?1?i?hi?h2i ?h?h2i?1?i（i=1,2,…,n/2）时称之为堆。现只讨论满足前者条件的堆。
由堆的定义可以看出，堆顶元素（即第一个元素）必为最大项。
在实际处理中，可以用一维数组H（1：n）来存储堆序列中的元素，也可以用完全二叉树来直观地表示堆的结构。
例如：序列（91，85，53，36，47，30，24，12）是一个堆，它所对应的完全二叉树如下图所示。可以看出，在用完全二叉树表示椎时，树中所有非叶子结点值均不小于其左、右子树的根结点值，因此，椎顶（完全二叉树的根结点）元素必为序列的n个元素中的最大项。