数据结构-排序

《数据结构-排序》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、排序排序的稳定性假定待排序的序列中存在多个记录具有相同的键值。若经过排序，这些记录的相对次序仍然保持不变(即在原序列中ki=kj，且i

2、移动（或者：交换）（基数排序除外）1、插入排序（插入i号元素）PROCEDUREins_sort(x:integer;VARn:integer);VARi:integer;BEGINa[n+1]:=x;p:=1;WHILEx>a[p]DOp:=p+1;{查找插入位置}FORi:=nDOWNTOpDOa[i+1]:=a[i];{移动元素，空出位置}a[p]:=x;n:=n+1;END;算法的优化（基于查找的优化）插入排序时间复杂度:O(N2)优化思路：由于插入前的查找是在一个有序序列中进行的，所以这个查找

3、可用折半查找来优化。算法效率分析1、所需要的附加存储空间仍是一个记录空间。2、时间上仅仅减少了比较次数，而记录移动次数没有减少，所以时间复杂度仍是O(N2)。冒泡排序（排成非递增序列）1、第一趟从r[1]开始，让r[i]和r[i+1]进行逐对比较，若出现反序则交换，然后进行下一对的比较；否则，直接进行下一对的比较。2、第二趟从r[2]开始进行逐对比较。……3、第i趟从r[i]开始进行逐对比较。直到某趟比较没有发现“反序”为止。快速排序快速排序是对冒泡排序的改进。它的基本思想是通过一趟排序将待排序列分隔成

4、独立的两部分，其中前面一部分比后面一部分的记录都要小（非递增序列），然后分别对这两部分继续进行相同的排序处理。快速排序时，首先任意选取一个记录（通常可以是第一个记录r[1]）作为枢轴（支点），然后将所有小于枢轴的数安置在它的位置之前，将大于枢轴的数安置在枢轴之后，这个过程称为一趟快速排序。然后对左右两个部分继续进行相同的排序，直到区间为空。procedureqsort(l,r:integer);vari,j,mid,temp:integer;begini:=l;j:=r;mid:=a[(l+r)div2

5、];{将当前序列在中间位置的数定义为中间数}repeatwhilea[i]j;ifl

6、henqsort(i,r);end;{qsort}快速排序的时间空间复杂度分析平均时间为k*N*logN，k为常数，经验说明，在所有同数量级排序中，快速排序的常数因子k是最小的。所以，就平均时间而言，快速排序是目前认为最好的排序方法。当原始序列基本有序或正序时，快速排序将蜕化为冒泡排序。一种改进是“三者取中”的法则来选取枢轴记录，就是每趟快速排序之前，作为枢轴的记录应是r[s],r[t],r[(s+t)/2]中的中间值，这样可以大大改善快速排序在最坏情况下的性能。从时间上看，快速排序平均性能优于前面讨论

7、过的算法。从空间上看，快速排序需要一个栈空间来实现递归，若每趟排序都均匀地分隔成两个长度接近的子序列，则栈的最大深度为[log2n]+1，但若每趟排序k均取t值，则为最坏情况，堆栈的最大深度为n。算法优化分析快速排序较之冒泡排序，主要是两方面（比较和移动次数）的改进：（1）快速排序的一次交换必能保证某个记录放置到最终位置上（这也是我们设计交换算法的最终目标）（2）快速排序采用二分的思想，大大缩小了比较查找的范围。选择排序selectionsort的基本思想是：每趟在剩余的n-i+1(i=1,2,…,n-

8、1)个记录中选取关键字最小的作为有序序列中第i个记录。其中最简单、大家最熟悉的是“简单选择排序”（simpleselectionsort）。一趟简单选择排序的操作为：通过n-i次关键字的比较，从剩余的n-i+1个记录中选取最小的记录，并和第i个记录进行交换位置。PROCEDUREselectsort;VARi,j,k,temp:integer;BEGINfori:=1ton-1doBEGINk:=i;forj:=i+1tondoifa[k]