排序算法汇总

《排序算法汇总》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、Jsoi2004-2005第一轮函授B班第4讲讲义第四讲排序算法第一节排序及其基本概念一、基本概念1．什么是排序排序是数据处理中经常使用的一种重要运算。设文件由n个记录{R1，R2，……，Rn}组成，n个记录对应的关键字集合为{K1，K2，……，Kn}。所谓排序就是将这n个记录按关键字大小递增或递减重新排列。2．稳定性当待排序记录的关键字均不相同时，排序结果是惟一的，否则排序结果不唯一。如果文件中关键字相同的记录经过某种排序方法进行排序之后，仍能保持它们在排序之前的相对次序，则称这种排序方法是稳定的；否则，称这种排序方法是不稳定

2、的。3．排序的方式由于文件大小不同使排序过程中涉及的存储器不同，可将排序分成内部排序和外部排序两类。整个排序过程都在内存进行的排序，称为内部排序；反之，若排序过程中要进行数据的内、外存交换，则称之为外部排序。内排序适用于记录个数不是很多的小文件，而外排序则适用于记录个数太多，不能一次性放人内存的大文件。内排序是排序的基础，本讲主要介绍各种内部排序的方法。按策略划分内部排序方法可以分为五类：插入排序、选择排序、交换排序、归并排序和分配排序。二、排序算法分析1．排序算法的基本操作几乎所有的排序都有两个基本的操作：（1）关键字大小的比

3、较。（2）改变记录的位置。具体处理方式依赖于记录的存储形式，对于顺序型记录，一般移动记录本身，而链式存储的记录则通过改变指向记录的指针实现重定位。为了简化描述，在下面的讲解中，我们只考虑记录的关键字，则其存储结构也简化为数组或链表。并约定排序结果为递增。2．排序算法性能评价排序的算法很多，不同的算法有不同的优缺点，没有哪种算法在任何情况下都是最好的。评价一种排序算法好坏的标准主要有两条：（1）执行时间和所需的辅助空间，即时间复杂度和空间复杂度；（2）算法本身的复杂程度，比如算法是否易读、是否易于实现。第二节插入排序插入排序的基本

4、思想是：每次将一个待排序的记录，按其关键字大小插入到前面已经排好序的记录集中，使记录依然有序，直到所有待排序记录全部插入完成。一、直接插入排序1．直接插入排序的思想13Jsoi2004-2005第一轮函授B班第4讲讲义假设待排序数据存放在数组A[1..n]中，则A[1]可看作是一个有序序列，让i从2开始，依次将A[i]插入到有序序列A[1..i-1]中，A[n]插入完毕则整个过程结束，A[1..n]成为有序序列。2．排序过程示例（用【】表示有序序列）待排序数据：【25】548542119727315（n=10）i=2：【2554

5、】8542119727315i=3：【82554】542119727315i=4：【8255454】2119727315i=5：【821255454】19727315i=6：【1821255454】9727315i=7：【182125545497】27315i=8：【1282125545497】7315i=9：【128212554547397】15i=10：【12815212554547397】排序结束3．算法实现可在数组中增加元素A[0]作为关键值存储器和循环控制开关。第i趟排序，即A[i]的插入过程为：①保存A[i]→A[0

6、]②③如果A[j]<=A[0]（即待排序的A[i]），则A[0]→A[j+1]，完成插入；否则，将A[j]后移一个位置：A[j]→A[j+1]；；继续执行③对于上面的数据实例，i从2依次变化到10的过程中，j值分别为{1，0，3，1，0，6，1，7，3}4．程序代码procedureinsertsort(n:integer);vari,j:integer;beginfori:=2tondobegina[0]:=a[i];j:=i-1;whilea[j]>a[0]do{决定运算次数和移动次数}begina[j+1]:=a[j];j

7、:=j-1;end;a[j+1]:=a[0];end;end;5．算法分析（1）稳定性：稳定13Jsoi2004-2005第一轮函授B班第4讲讲义（2）时间复杂度：①原始数据正序，总比较次数：n-1②原始数据逆序，总比较次数：③原始数据无序，第i趟平均比较次数=，总次数为：④可见，原始数据越趋向正序，比较次数和移动次数越少。（3）空间复杂度：仅需一个单元A[O]二、希尔排序1．基本思想：任取一个小于n的整数S1作为增量，把所有元素分成S1个组。所有间距为S1的元素放在同一个组中。第一组：{A[1]，A[S1+1]，A[2*S1+

8、1]，……}第二组：{A[2]，A[S1+2]，A[2*S1+2]，……}第三组：{A[3]，A[S1+3]，A[2*S1+3]，……}……第s1组：{A[S1]，A[2*S1]，A[3*S1]，……}先在各组内进行直接插人排序；然后，取第二个增量S2（