c语言中的排序方法.doc

排序技术
1、 所谓排序，就是要整理的文件中的记录，使之按关键字第增（或第减）的次序排列起来。
2、 常用交换类排序
冒泡排序法是一种最简单的交换类排序方法，它是通过相邻数据元素的交换逐步将线性表变成有序。
冒泡排序法的基本过程如下：
首先，从表头开始往后扫描线性表，在扫描的过程中逐次比较两个相邻元素的大小，若两个相邻的元素中，前面的元素大于后面的元素，则将它们交换，称之为消去了一个逆序。
然后，从后往前扫面剩下的线性表，同样，在扫描的过程中逐次比较两个相邻元素的大小，若后面的元素小于前面的元素，则将它们交换，这样就又消失了一个逆序，一次排序结束后，表中最大元素位于线性表的末尾。
对剩下的线性表重复上述过程，直到剩下的线性表变空为止，此时的线性表已经变为有序。
2、 快速排序法
快速排序法也是一种交换类排序方法，但由于它的排序速度比较快，因此称为快速排序法。
快速排序方法的基本思想如下：
从线性表中选取一个元素，设为t，将线性表后面小于t的元素转移到前面，而前面大于t的元素移到后面，结果就将线性表的分为两个部分（称为两个子表），t插入到其分界线的位置处，这个过程称为线性表的分割。通过对线性表的一次分割，就以t为分界线，将线性表分为了前后两个子表，且前面子表中的所有元素均不大于t，而后面子表中的元素均不小于t。
如果对分割后的各子表再按上述原则进行分割，并且这种分割过程的一直做下去，直到所有子表为空为止，此时的线性表就变成了有序表。
3、 插入类排序法
简单插入排序法：所谓插入排序，是指将无序序中的各元素依次插入到已经有序的线性表中。
希尔排序法：属于插入类排序，其基本思想为：将整个无序列分割成若干小的子序列分别进行插入排序。
子序列分割方法如下：
将相隔某个增量h的元素构成一个子序列。在排序过程中，逐次减少这个增量，最后当h减到1时，进行一次插入排序，排序即将发生。
3、 选择类排序法
（1）简单选择排序法
其基本思想：扫面整个线性表，从中选出最小的元素，将它交换到表的最前面，然后对剩下的子表采用同样的方法，直到子表空为止。
（2） 建堆排序法
堆排序的方法如下：
1）首先将一个无序序列建成堆
2） 然后将堆顶元素与堆中的最后一个元素交换，不考虑已经交换到最后的那个元素，只考虑前n-1个元素构成的子序列，显然，该子序列已不是堆，但左右子树仍为堆，可以将该子树调整为堆。
3） 反复做第二步，直到剩下的子序列为空为止。