第讲排序技术IVIP

1、仲志丹仲志丹机械电子工程教研室机械电子工程教研室机械电子工程教研室机械电子工程教研室软件技术基础软件技术基础n 排序：给定一组记录的集合 r1, r2, , rn， 其相应的关键码分别为 k1, k2, , kn， 排序是将这些记录排列成顺序为 rs1, rs2, , rsn的一个序列，使得相应的关键码满足ks1ks2ksn（称为升序）或ks1ks2ksn（称为降序）。机械电子工程教研室机械电子工程教研室软件技术基础软件技术基础n 排序的稳定性： 若记录序列中的任意两个记录 Rx、Ry 的关键字 Kx = Ky ； 如果在排序之前和排序之后，它们的相对位置保持不变，则这种排序方法是稳定的，否则

2、是不稳定的。机械电子工程教研室机械电子工程教研室软件技术基础软件技术基础n 内排序和外排序： 内排序：内排序：指在排序的整个过程中，待排序的所有指在排序的整个过程中，待排序的所有记录全部被放置在内存中记录全部被放置在内存中 外排序外排序：由于待排序的记录个数太多，不能同时：由于待排序的记录个数太多，不能同时放置在内存，而需要将一部分记录放置在内存，放置在内存，而需要将一部分记录放置在内存，另一部分记录放置在外存上，整个排序过程需要另一部分记录放置在外存上，整个排序过程需要在内外存之间多次交换数据才能得到排序的结果在内外存之间多次交换数据才能得到排序的结果机械电子工程教研室机械电子工程教研室软件

3、技术基础软件技术基础n对记录的排序所需关键字的比较次数； n对记录的排序所需记录的移动次数； n排序过程中所需的辅助空间。 在下述讨论中约定：文件的存储结构采用顺序结构，在下述讨论中约定：文件的存储结构采用顺序结构，即使用一维数组即使用一维数组RnRn表示表示n n个记录。个记录。机械电子工程教研室机械电子工程教研室软件技术基础软件技术基础排序方法排序方法插入类排序插入类排序选择类排序选择类排序交换类排序交换类排序归并排序归并排序直接插入排序直接插入排序折半插入排序折半插入排序简单选择排序简单选择排序堆排序堆排序起泡排序起泡排序多关键字排序多关键字排序分配类排序分配类排序链式基数排序链式基数排

4、序基数排序的顺序表结构基数排序的顺序表结构快速排序快速排序树形选择排序树形选择排序希尔排序希尔排序机械电子工程教研室机械电子工程教研室软件技术基础软件技术基础n 插入排序的基本思想是：每次将一个待排序的记录，按其插入排序的基本思想是：每次将一个待排序的记录，按其关键字大小插入到前面已经排好序的子表中的适当位置，关键字大小插入到前面已经排好序的子表中的适当位置，直到全部记录插入完成为止。也就是说，直到全部记录插入完成为止。也就是说，将待序列表分成将待序列表分成左右两部分，左边为有序表（有序序列），右边为无序表左右两部分，左边为有序表（有序序列），右边为无序表（无序序列）。整个排序过程就是将右边无

5、序表中的记录（无序序列）。整个排序过程就是将右边无序表中的记录逐个插入到左边的有序表中，构成新的有序序列。逐个插入到左边的有序表中，构成新的有序序列。n 根据不同的插入方法，插入排序算法主要包括：根据不同的插入方法，插入排序算法主要包括：u 直接插入排序直接插入排序u 折半插入排序折半插入排序u 希尔排序希尔排序机械电子工程教研室机械电子工程教研室软件技术基础软件技术基础基本思想：每次将一个待排序的记录，按其关键字大小插入每次将一个待排序的记录，按其关键字大小插入到前面已经排好序的子序列中的适当位置，直到全部记录到前面已经排好序的子序列中的适当位置，直到全部记录插入完成为止。插入完成为止。 设

6、数组为设数组为a0n-1a0n-1。u初始时，初始时，a0a0自成自成1 1个有序区，无序区为个有序区，无序区为a1.n-1a1.n-1。令。令i=1i=1u将将aiai并入当前的有序区并入当前的有序区a0i-1a0i-1中形成中形成a0ia0i的有序的有序区间。区间。ui+i+并重复第二步直到并重复第二步直到i=n-1i=n-1。排序完成。排序完成。机械电子工程教研室机械电子工程教研室软件技术基础软件技术基础void InsertSort(int a, int n) int i, j, k; int temp; for (i = 1; i =0; j-) if(ajj; k-) ak+1 =

7、 ak; /将将ai放到正确位置上放到正确位置上 ak+1 = temp; 机械电子工程教研室机械电子工程教研室软件技术基础软件技术基础void lnsertSort(int a, int n) int i，j, temp； for(i=1; in；i+) if(ai0 & temp ai-1说明a0i也是有序的，无须调整。否则就令j=i-1,temp=ai。然后一边将数据aj向后移动一边向前搜索，当有数据aj aj，就交换aj和aj-1，再j-直到aj-1 = aj。这样也可以实现将一个新数据新并入到有序区间。 。void Insertsort3(int a, int n) int i, j

8、; for (i = 1; i =0 & ajaj+1; j-) Swap(aj, aj+1);机械电子工程教研室机械电子工程教研室软件技术基础软件技术基础111122142221nininnniRMNnnniKCN/ )()( ,/ )(22机械电子工程教研室机械电子工程教研室软件技术基础软件技术基础机械电子工程教研室机械电子工程教研室软件技术基础软件技术基础 折半插入排序（binary insertion sort）是对插入排序算法的一种改进，由于排序算法过程中，就是不断的依次将元素插入前面已排好序的序列中。由于前半部分为已排好序的数列，这样我们不用按顺序依次寻找插入点，可以采用折半查找的

9、方法来加快寻找插入点的速度。机械电子工程教研室机械电子工程教研室软件技术基础软件技术基础void BinSort(int a，int n) int i,j,temp; int low, high, mid; for(i=1;in; i+) temp=ai; low=0; high=i-1; while(low=high) mid=(low+high)/2; if(temp high+1;j- ) aj = aj-1; ahigh+1 = temp; 机械电子工程教研室机械电子工程教研室软件技术基础软件技术基础u采用折半插入排序法，可减少关键字的比采用折半插入排序法，可减少关键字的比较次数。插入

10、较次数。插入n-1n-1个元素的平均关键字的比个元素的平均关键字的比较次数为较次数为O(n logO(n log2 2n)n)。u折半插入排序法与直接插入排序法相比，折半插入排序法与直接插入排序法相比，关键字比较次数减少了，但数据移动次数关键字比较次数减少了，但数据移动次数并未改变，故时间复杂度依然是并未改变，故时间复杂度依然是O(nO(n2 2) )。u折半插入排序法也是一种折半插入排序法也是一种稳定稳定的排序法。的排序法。机械电子工程教研室机械电子工程教研室软件技术基础软件技术基础Donald L. Shell(March 1, 1924) USA the author of the Sh

11、ellsort 机械电子工程教研室机械电子工程教研室软件技术基础软件技术基础先将整个待排记录序列分割先将整个待排记录序列分割成若干小组（子序列），分别在组内进行直接插入成若干小组（子序列），分别在组内进行直接插入排序，待整个序列中的记录排序，待整个序列中的记录“基本有序基本有序”时，再对时，再对全体记录进行一次直接插入排序。全体记录进行一次直接插入排序。（1 1）首先取一个整数）首先取一个整数d d1 1nn，称之为增量，将待排序的记录称之为增量，将待排序的记录分成分成d d1 1个组，凡是距离为个组，凡是距离为d d1 1倍数的记录都放在同一个组，在倍数的记录都放在同一个组，在各组内进行直接

12、插入排序，这样的一次分组和排序过程称各组内进行直接插入排序，这样的一次分组和排序过程称为一趟希尔排序。为一趟希尔排序。（2 2）再设置另一个新的增量）再设置另一个新的增量d d2 2dd1 1，采用与上述相同的方法采用与上述相同的方法继续进行分组和排序过程。继续进行分组和排序过程。（3 3）继续取）继续取d di+1i+1d0; gap/=2) /步长步长 for(i=0; igap; i+) /直接插入排序直接插入排序 for(j=i+gap; jn; j+=gap) if(aj=0 & aktemp) ak+gap=ak; k -= gap; ak+gap=temp; 下面给出严格按照定义

13、来写的希尔排序机械电子工程教研室机械电子工程教研室软件技术基础软件技术基础下面给出希尔排序void shellsort(int a, int n) int i, j, gap; for(gap=n/2; gap0; gap/=2) for(i=gap; i=0&ajaj+gap;j-=gap) Swap(aj, aj+gap);机械电子工程教研室机械电子工程教研室软件技术基础软件技术基础n在希尔排序中，各子序列的排序过程相对独立，但具体实现时，并不是先对一个子序列进行完全排序，再对另一个子序列进行排序。n顺序扫描整个待排序记录序列时，各子序列的元素将会反复轮流出现。根据这一特点，希尔排序从第一

14、个子序列的第二个元素开始，顺序扫描待排序记录序列对首先出现的各子序列的第二个元素，分别在各子序列中进行插入处理；然后对随后出现的各子序列的第三个元素，分别在各子序列中进行插入处理，直到处理完各子序列的最后一个元素。机械电子工程教研室机械电子工程教研室软件技术基础软件技术基础n时间复杂度当当d di i=1=1时，尽管这一趟希尔排序时，尽管这一趟希尔排序 相当于直接插相当于直接插入排序，移动次数相对于简单的直接插入排序入排序，移动次数相对于简单的直接插入排序而言会减少。而言会减少。希尔排序是一个较好的插入排序方法。希尔排希尔排序是一个较好的插入排序方法。希尔排序能迅速减少逆转数，尽管当间隔为序能

15、迅速减少逆转数，尽管当间隔为1 1时，希尔时，希尔排序相当于直接插入排序，但此时的关键字序排序相当于直接插入排序，但此时的关键字序列的逆转数已经很小，序列已经基本有序，列的逆转数已经很小，序列已经基本有序， 使使用的恰好是直接插入的最佳性质，它的复杂度用的恰好是直接插入的最佳性质，它的复杂度为为O O( (n n1.51.5) )，比直接插入好。，比直接插入好。机械电子工程教研室机械电子工程教研室软件技术基础软件技术基础n算法稳定性希尔排序的分析是一个复杂的问题，因为它的时希尔排序的分析是一个复杂的问题，因为它的时间耗费是所取的间耗费是所取的“增量增量”序列的函数。到目前为序列的函数。到目前为

16、止，尚未有人求得一种最好的增量序列。但大量止，尚未有人求得一种最好的增量序列。但大量研究也得出了一些局部的结论。研究也得出了一些局部的结论。在排序过程中，相同关键字记录的领先关系发生在排序过程中，相同关键字记录的领先关系发生变化，则说明该排序方法是变化，则说明该排序方法是不稳定不稳定的。的。机械电子工程教研室机械电子工程教研室软件技术基础软件技术基础排序算法改进方法时间复杂度直接插入O(n2)折半排序改进确定插入位置的方法，利用折半的思想确定有有序表中的插入位置。O(n2)希尔排序利用直接插入的最好性质： n比较小； 基本有序O(n1.5)机械电子工程教研室机械电子工程教研室软件技术基础软件技

17、术基础n所谓互换排序是指借助数据元素之间的互相交换进行排序的一种方法。冒泡排序(Bubble Sort)快速排序(Quick Sort)机械电子工程教研室机械电子工程教研室软件技术基础软件技术基础p 首先比较第一个和第二个数据，将其中较小的数据放到第一个位置，较大的放到第二个位置；然后比较第二个和第三个数据，仍将较小放到后一个位置。依此类推，直到比较第n-1和第n个数据。这样，就将待排序序列中的最大的一个放到了第n个数据，这个过程称为第一趟排序。p 下面对前N-1个数据重复这个过程（不用考虑第n个数据，因为它已经是最大的了），又将次大的数据放到了第n-1个位置。一般地，第i趟冒泡排序是对第1个

18、到第n-i+1个数据进行操作，选出原序列第i大的数据放到数组的第n-i+1位置。重复这个过程，直到i=n-1为止。机械电子工程教研室机械电子工程教研室软件技术基础软件技术基础初始关键字第一趟排序第四趟排序第二趟排序第三趟排序第五趟排序机械电子工程教研室机械电子工程教研室软件技术基础软件技术基础void BubbleSort(int a, int n) int i, j; for(i=0; in; i+) for (j=1; jaj) Swap(aj-1, aj);机械电子工程教研室机械电子工程教研室软件技术基础软件技术基础void BubbleSort(int r, int n) int i,

19、j,temp; int flag = 1; for(i=0; in-1; i+) /* 共有共有N-1趟排序趟排序 */ flag = 1; for(j=0; jn-i-1; j+) if(rj 0) k = flag; flag = 0; for (j=1; j aj)Swap(aj-1, aj);flag=j; 下面对其进行优化，如果有100个数的数组，仅前面10个无序，后面90个都已排好序且都大于前面10个数字，那么在第一趟遍历后，最后发生交换的位置必定小于10，且这个位置之后的数据必定已经有序了，记录下这位置，第二次只要从数组头部遍历到这个位置就可以了。机械电子工程教研室机械电子工程教

20、研室软件技术基础软件技术基础n假设线性表长度为n，则在最坏情况下(初始状态是反序)n一般情况下要小于这个工作量。对于基本有序的序列，效率较高。112112)(2/ ) 1(3)( 3)(2/ ) 1()(nininOnninnOnnin移动次数的最大值比较次数的最大值机械电子工程教研室机械电子工程教研室软件技术基础软件技术基础n其实和传统的冒泡排序是一样的，唯一不同的地方是双向的。n假如说第一次把数组的最大值移动到了数组的alength-1的位置，传统的方式是指针再次回到a0进行移动，该方式是在alength-2开始，将最小的值移动到最左端a0的位置，然后在从a1的位置开始，这样双向反复，直到

21、排序完毕。机械电子工程教研室机械电子工程教研室软件技术基础软件技术基础机械电子工程教研室机械电子工程教研室软件技术基础软件技术基础void BiBubbleSort(int r, int n) int i,low,high,temp; int flag =1; low=0; high=n-1; while(lowhigh&flag) flag=0; for(i=low;irj+1) temp=rj;rj=rj+1;rj+1=temp; flag =1; high-; /*修改上界修改上界 */ for(j=high;jlow;j-) /*从下向上冒泡从下向上冒泡*/ if(rjrj-1) te

22、mp=rj;rj=rj-1;rj-1=temp; flag =1; low+; /*修改下界修改下界*/ /*while*/机械电子工程教研室机械电子工程教研室软件技术基础软件技术基础n快速排序是C.R.A.Hoare于1962年提出的一种划分交换排序。它采用了一种分治的策略，通常称其为分治法。n该方法的基本思想是：u先从数列中取出一个数作为基准数。u分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。u再对左右区间重复第二步，直到各区间只有一个数。机械电子工程教研室机械电子工程教研室软件技术基础软件技术基础n如何选择基准数？选择第一个元素n如何分区？机械电子工程教研室机

23、械电子工程教研室软件技术基础软件技术基础0123456789726 57 88 60 42 83 73 48 85以一个数组作为示例，取区间第一个数为基准数。初始时，i = 0; j = 9; X = ai = 72由于已经将a0中的数保存到X中，可以理解成在数组a0上挖了个坑，可以将其它数据填充到这来。从 j开始向前找一个比X小或等于X的数。当j=8，符合条件，将a8挖出再填到上一个坑a0中。a0=a8; i+; 这样一个坑a0就被搞定了，但又形成了一个新坑a8，这怎么办了？简单，再找数字来填a8这个坑。这次从i开始向后找一个大于X的数，当 i=3，符合条件，将a3挖出再填到上一个坑中a8=

24、a3; j-;01234567894865788604283738885i = 3; j = 7; X=72机械电子工程教研室机械电子工程教研室软件技术基础软件技术基础再重复上面的步骤，先从后向前找，再从前向后找先从后向前找，再从前向后找。从j开始向前找，当j=5，符合条件，将a5挖出填到上一个坑中，a3 = a5; i+;从i开始向后找，当i=5时，由于i=j退出。此时，i = j = 5，而a5刚好又是上次挖的坑，因此将X填入a5。01234567894865742607283738885可以看出看出a5前面的数字都小于它，前面的数字都小于它，a5后面的数字都后面的数字都大于它大于它。因此

25、再对a04和a69这二个子区间重复重复上述步骤就可以了。机械电子工程教研室机械电子工程教研室软件技术基础软件技术基础对挖坑填数进行总结对挖坑填数进行总结1i =L; j = R; 将基准数挖出形成第一个坑将基准数挖出形成第一个坑ai。2j-由后向前找比它小的数，找到后挖出此数填前由后向前找比它小的数，找到后挖出此数填前一个坑一个坑ai中。中。3i+由前向后找比它大的数，找到后也挖出此数由前向后找比它大的数，找到后也挖出此数填到前一个坑填到前一个坑aj中。中。4再重复执行再重复执行2，3二步，直到二步，直到i=j，将基准数填入，将基准数填入ai中。中。机械电子工程教研室机械电子工程教研室软件技术

26、基础软件技术基础int Split(int a, int low, int high) int x = alow; while(lowhigh) while(low=x) high-; if(lowhigh) alow=ahigh; low+; while(lowhigh&arraylow=pivot) low+; if(lowhigh) ahigh=alow; high-; alow=x; return low; 机械电子工程教研室机械电子工程教研室软件技术基础软件技术基础void QuickSort(int a, int low, int high) int i; if (low r) i

27、nt i = Split(a, low, high); QuickSort (a, low, i - 1); QuickSort (a, i + 1, high); 机械电子工程教研室机械电子工程教研室软件技术基础软件技术基础 快速排序算法的性能取决于划分的对称性。通过快速排序算法的性能取决于划分的对称性。通过修改算法修改算法Split，可以设计出采用随机选择策略的，可以设计出采用随机选择策略的快速排序算法。在快速排序算法的每一步中，当快速排序算法。在快速排序算法的每一步中，当数组还没有被划分时，可以在数组还没有被划分时，可以在a0:n-1中随机选出中随机选出一个元素作为划分基准，这样可以使划

28、分基准的一个元素作为划分基准，这样可以使划分基准的选择是随机的，从而可以期望划分是较对称的。选择是随机的，从而可以期望划分是较对称的。 int RandomSplit(int a, int low, int high) int i,x; i = random(p,r); x = ai; / 机械电子工程教研室机械电子工程教研室软件技术基础软件技术基础n最坏情况n如果序列为顺序排列如果序列为顺序排列n每次总是以最小数为基准每次总是以最小数为基准n每次分割的前子序列中总为空每次分割的前子序列中总为空时间复杂性为时间复杂性为O(n2)。n最好情况序列每次总是被均匀分割两个长度相当的子序列序列每次总是

29、被均匀分割两个长度相当的子序列时间复杂性为时间复杂性为O(nlgn) 可以选择选择基准避免最坏情况发生机械电子工程教研室机械电子工程教研室软件技术基础软件技术基础n最坏情况：每次划分基准偏向子序列的一端。栈的最大深度为n。n最好情况：每次将序列划分成长度接近的两个子序列，则栈的最大深度快速排序算法需要一个栈空间来实现递归机械电子工程教研室机械电子工程教研室软件技术基础软件技术基础l 最坏时间复杂度：最坏时间复杂度：O(n2) l 平均时间复杂度：平均时间复杂度：O(nlogn) l 辅助空间：辅助空间：O(n) 或或 O(logn)l 稳定性：不稳定稳定性：不稳定机械电子工程教研室机械电子工程

30、教研室软件技术基础软件技术基础直接选择排序直接选择排序堆排序堆排序树形选择排序树形选择排序机械电子工程教研室机械电子工程教研室软件技术基础软件技术基础n直接选择排序和直接插入排序类似，都将数据分为有序区和无序区，所不同的是直接插入排序是将无序区的第一个元素直接插入到有序区以形成一个更大的有序区，而直接选择排序是从无序区选一个最小的元素直接放到有序区的最后。重复第二步，直到各区间只有一个数。机械电子工程教研室机械电子工程教研室软件技术基础软件技术基础机械电子工程教研室机械电子工程教研室软件技术基础软件技术基础设数组为设数组为a0n-1a0n-1。1.1.初始时，数组全为无序区为初始时，数组全为无

31、序区为a0.n-1a0.n-1。令。令i=0i=02.2.在无序区在无序区ain-1ain-1中选取一个最小的元素，将其中选取一个最小的元素，将其与与aiai交换。交换之后交换。交换之后a0ia0i就形成了一个有序区。就形成了一个有序区。3.i+3.i+并重复第二步直到并重复第二步直到i=n-1i=n-1。排序完成。排序完成。void Selectsort(int a, int n) int i, j, nMinIndex; for (i = 0; i n; i+) nMinIndex = i; /找最小元素的位置找最小元素的位置 for (j = i + 1; j n; j+) if (aj anMinIndex) nMinIndex = j; Swap(ai, anMinIndex); 机械电子工程教研室机械电子工程教研室软件技术基础软件技术基础要特别提醒各位注意下要特别提醒各位注意下Swap()Swap()的实现，建议用的实现，建议用void S &a, int &b) int c = a; a = b; b = c; 不