《第10章排序.ppt》由会员分享，可在线阅读，更多相关《第10章排序.ppt（90页珍藏版）》请在三一文库上搜索。
1、第10章 排序,排序的基本概念（P200）,排序算法的稳定性：假定在待排序的记录集中，存在多个具有相同键值的记录，若经过排序，这些记录的相对次序仍然保持不变，即在原序列中，ki=kj且ri在rj之前，而在排序后的序列中，ri仍在rj之前，则称这种排序算法是稳定的；否则称为不稳定的。,排序的基本概念,排序的分类 1. 内排序：在排序的整个过程中，待排序的所有记录全部被放置在内存中 2. 外排序：由于待排序的记录个数太多，不能同时放置在内存，而需要将一部分记录放置在内存，另一部分记录放置在外存上，整个排序过程需要在内外存之间多次交换数据才能得到排序的结果。,排序的基本概念,排序算法的性能指标 1.
2、 时间开销： 比较：关键码之间的比较； 移动：记录从一个位置移动到另一个位置。 2. 空间开销： 辅助存储空间 3. 算法的稳定性,排序算法的存储结构,从操作角度看，排序是线性结构的一种操作，待排序记录可以用顺序存储结构或链接存储结构存储。 假定1：采用顺序存储结构，关键码为整型，且记录只有关键码一个数据项。 int rn+1; /待排序记录存储在r1rn，r0留做他用 假定2：将待排序的记录序列排序为升序序列。,10.2 冒泡排序,交换排序的主要操作是交换，其主要思想是：在待排序列中选两个记录，将它们的关键码相比较，如果反序（即排列顺序与排序后的次序正好相反），则交换它们的存储位置。 冒泡排
3、序的改进。（P202）,冒泡排序的时间性能分析,最好情况（正序）： 比较次数：n-1 移动次数：0 时间复杂度为O(n)。,最坏情况（反序）：,时间复杂度为O(n2)。,平均情况：时间复杂度为O(n2)。,冒泡排序的时间性能分析,冒泡排序的性能分析,在平均情况下，冒泡排序的时间复杂度与最坏情况同数量级。 冒泡排序只需要一个记录的辅助空间，用来作为记录交换的暂存单元。 冒泡排序是一种稳定的排序方法。,选择排序的主要操作是选择，其主要思想是:每趟排序在当前待排序序列中选出关键码最小的记录，添加到有序序列中。,10.3 选择排序,简单选择排序的主要思想是： 第i 趟在n-i+1（i=1,2,n-1）
4、个记录中选取关键码最小的记录作为有序序列中的第i个记录。 需解决的关键问题? 如何在待排序序列中选出关键码最小的记录？ 如何确定待排序序列中关键码最小的记录在有序序列中的位置？,简单选择排序,简单选择排序示例,i = 2,最小者 08 交换21,08,最小者 16 交换25,16,最小者 21 交换49,21,21,28,i = 1,25,16,49,08,08,i = 3,21,i = 4,最小者 25 交换25,28,i = 5,最小者 28 不交换,25,28,无序区只有 一个记录,简单选择排序示例,21,28,25,16,49,08,k,k,08,问题1：如何在无序区中选出关键码最小的
5、记录？,解决方法： 设置一个整型变量k，用于记录在一趟比较的过程中关键码最小的记录位置。,问题1：如何在无序区中选出关键码最小的记录？,解决方法： 设置一个整型变量k，用于记录在一趟比较的过程中关键码最小的记录位置。,算法描述： k=i; for (j=i+1; j=n; j+) if (rjrk) k=j;,问题2：如何确定最小记录的最终位置？,解决方法： 第i趟简单选择排序的待排序区间是ri rn，则ri是无序区第一个记录，所以，将index所记载的关键码最小的记录与ri交换。,算法描述： if (k!=i) rirk;,void SelectSort (Record r , int n)
6、 for (i=0; in-1; i+) k=i; for (j=i+1; jn; j+) if (rj.keyrk.key) k=j; if (k!=i) temp=ri; ri=rk; rk=temp; ,简单选择排序算法,最坏情况：3(n-1)次,简单选择排序算法的性能分析,移动次数： 最好情况（正序）：0次,空间性能：需一个辅助空间。 稳定性：是一种稳定的排序算法。,1,2,3,4,比较次数：,简单选择排序的时间复杂度为O(n2)。,10.4 插入排序,插入排序的基本思想是：将待排序表看做是左、右两部分，其中左边为有序区，右边为无序区，整个排序过程就是将右边无序区中的记录依次按关键字大
7、小逐个插入到左边有序区中，以构成新的有序区，直到全部记录都排好序。,直接插入排序,基本思想：在插入第 i（i1）个记录时，前面的 i-1个记录已经排好序。,直接插入排序,基本思想：在插入第 i（i1）个记录时，前面的 i-1个记录已经排好序。 需解决的关键问题： （1）如何构造初始的有序序列？ （2）如何查找待插入记录的插入位置?,r 0 1 2 3 4 5 6,21,18,25,22,10,25*,21,22,10,25,18,18,r0的作用?,暂存单元,监视哨,直接插入排序过程示例,问题1：如何构造初始的有序序列,解决方法： 将第1个记录看成是初始有序表，然后从第2个记录起依次插入到这个
8、有序表中，直到将第 n个记录插入。 算法描述： for (i=2; i=n; i+) 插入第i个记录，即第i趟直接插入排序； ,解决方法： 在i-1个记录的有序区r1 ri-1中插入记录ri，首先顺序查找ri的正确插入位置，然后将ri插入到相应位置。,r0有两个作用： 1. 进入循环之前暂存了ri的值，使得不致于因记录的后移而丢失ri的内容； 2. 在查找插入位置的循环中充当哨兵。,算法描述： r0=ri; j=i-1; while (r0rj) rj+1=rj; j-; ,问题2：如何查找待插入记录的插入位置?,最好情况下（正序）：,最坏情况下（逆序或反序）：,时间复杂度为O(n2)。,时间
9、复杂度为O(n)。,直接插入排序的时间性能分析,平均情况下（随机排列）：,时间复杂度为O(n2)。,直接插入排序的时间性能分析,直接插入排序的性能分析,空间性能：需要一个记录的辅助空间。 直接插入排序算法是一种稳定的排序算法。 直接插入排序算法简单、容易实现，适用于待排序记录基本有序或待排序记录较小时。 当待排序的记录个数较多时，大量的比较和移动操作使直接插入排序算法的效率降低。,10.5 希尔排序,对直接插入排序进行改进 改进的着眼点： （1）若待排序记录按关键码基本有序时，直接插入排序的效率可以大大提高； （2）由于直接插入排序算法简单，则在待排序记录数量n较小时效率也很高。,基本思想：将
10、整个待排序记录分割成若干个子序列，在子序列内分别进行直接插入排序，待整个序列中的记录基本有序时，对全体记录进行直接插入排序。 需解决的关键问题? （1）应如何分割待排序记录，才能保证整个序列逐步向基本有序发展？ （2）子序列内如何进行直接插入排序？,分割待排序记录的目的? 1. 减少待排序记录个数； 2. 使整个序列向基本有序发展。 基本有序：例如1, 2, 8, 4, 5, 6, 7, 3, 9； 局部有序：例如6, 7, 8, 9, 1, 2, 3, 4, 5。 局部有序不能提高直接插入排序算法的时间性能。 启示? 子序列的构成不能是简单地“逐段分割”，而是将相距某个“增量”的记录组成一个
11、子序列。,1 2 3 4 5 6 7 8 9,40,21,25,49,25*,16,初始序列,30,08,13,希尔插入排序过程示例,算法描述： for (d=n/2; d=1; d=d/2) 以d为增量，进行组内直接插入排序； ,解决方法： 将相隔某个“增量”的记录组成一个子序列。 增量应如何取？ 希尔最早提出的方法是d1=n/2，di+1=di/2。,问题1：应如何分割待排序记录？,解决方法： 在插入记录ri时，自ri-d起往前跳跃式（跳跃幅度为d）搜索待插入位置，并且r0只是暂存单元，不是哨兵。当搜索位置0，表示插入位置已找到。 在搜索过程中，记录后移也是跳跃d个位置。 在整个序列中，前
12、d个记录分别是d个子序列中的第一个记录，所以从第d+1个记录开始进行插入。,问题2：子序列内如何进行直接插入排序？,算法描述：,void ShellSort(Record r , int n) for (d=n/2;d=1;d=d/2) /以增量d进行直接插入排序 for (i=d; i0 /记录后移 d个位置 rj+d=temp ,问题2：子序列内如何进行直接插入排序？,希尔排序开始时增量较大，每个子序列中的记录个数较少，从而排序速度较快；当增量较小时，虽然每个子序列中记录个数较多，但整个序列已基本有序，排序速度也较快。 希尔排序算法的时间性能是所取增量的函数，而到目前为止尚未有人求得一种最
13、好的增量序列。 研究表明，希尔排序的时间性能在O(n2)和O(nlog2n)之间。当n在某个特定范围内，希尔排序所需的比较次数和记录的移动次数约为O(n1.3 ) 。,希尔排序算法的时间性能,10.6 快速排序,首先选一个轴值（即比较的基准），通过一趟排序将待排序记录分割成独立的两部分，前一部分记录的关键码均小于或等于轴值，后一部分记录的关键码均大于或等于轴值，然后分别对这两部分重复上述方法，直到整个序列有序。 需解决的关键问题： 如何选择轴值？ 如何实现分割（称一次划分）？ 如何处理分割得到的两个待排序子序列？ 如何判别快速排序的结束？,问题1：如何选择轴值？,选择轴值的方法： 1.使用第一
14、个记录的关键码； 2.选取序列中间记录的关键码； 3.比较序列中第一个记录、最后一个记录和中间记录的关键码，取关键码居中的作为轴值并调换到第一个记录的位置； 4.随机选取轴值。 选取不同轴值的效果： 决定两个子序列的长度，子序列的长度最好相等。,13,65,27,50,38,49,55,问题2：如何实现一次划分？,解决方法： 取第一个记录的关键字值作为基准，将第一个记录暂存于temp中，设两个变量i，j分别指示将要划分的最左、最右记录的位置。 将j指向的记录关键字值与基准值进行比较，如果j指向的记录关键字值大，则j前移一个位置；重复此过程，直到j指向的记录关键字值小于基准值；若ij，则将j指向
15、的记录移到i所指位置。 将i指向的记录关键字值与基准值进行比较，如果i指向的记录关键字值小，则i后移一个位置；重复此过程，直到i指向的记录关键字值大于基准；若ij，则i指向的记录移到j所指位置。 重复、步，直到i=j。,问题2：如何实现一次划分？,问题2：如何实现一次划分？,算法描述：,int Partition(Record r , int i, int j) temp= ri; while (i= temp.key) j-； if (ij) ri+= rj; while (ij ,问题2：如何实现一次划分？,解决方法： 对分割得到的两个子序列递归地执行快速排序。,38,问题3：如何处理分割
16、得到的两个待排序子序列？,算法描述：,void QuickSort (Record r , int i, int j ) if (ij) pivot=Partition(r, i, j); QuickSort(r, i, pivot-1); QuickSort(r, pivot+1, j); 初始调用为QuickSort(r, 1, n),问题3：如何处理分割得到的两个待排序子序列？,解决方法： 若待排序列中只有一个记录，显然已有序，否则进行一次划分后，再分别对分割所得的两个子序列进行快速排序（即递归处理）。,问题4：如何判别快速排序的结束？,void QuickSort (Record r
17、, int i, int j ) if (ij) pivot=Partition(r, i, j); QuickSort(r, i, pivot-1); QuickSort(r, pivot+1, j); ,最坏情况： 每次划分只得到一个比上一次划分少一个记录的子序列（另一个子序列为空），为 O(n2)。,最好情况： 每一次划分对一个记录定位后，该记录的左侧子表与右侧子表的长度相同，为O(nlog2n)。,平均情况：为O(nlog2n)。,快速排序的时间性能分析,快速排序的性能分析,快速排序是一种不稳定的排序方法。 请举例说明。,简单选择排序的改进 改进的着眼点： 如何减少关键码间的比较次数。
18、若能利用每趟比较后的结果，也就是在找出键值最小记录的同时，也找出键值较小的记录，则可减少后面的选择中所用的比较次数，从而提高整个排序过程的效率。,10.7 堆排序,堆的定义,堆是具有下列性质的完全二叉树：每个结点的值都小于或等于其左右孩子结点的值（称为小根堆），或每个结点的值都大于或等于其左右孩子结点的值（称为大根堆）。,1. 小根堆的根结点是所有结点的最小者。 2. 较小结点靠近根结点，但不绝对。,1. 大根堆的根结点是所有结点的最大者。 2. 较大结点靠近根结点，但不绝对。,堆的定义,堆是具有下列性质的完全二叉树：每个结点的值都小于或等于其左右孩子结点的值（称为小根堆），或每个结点的值都大
19、于或等于其左右孩子结点的值（称为大根堆）。,堆和序列的关系,将堆用顺序存储结构来存储，则堆对应一组序列。,基本思想：首先将待排序的记录序列构造成一个堆，此时，选出了堆中所有记录的最大者，然后将它从堆中移走，并将剩余的记录再调整成堆，这样又找出了次小的记录，以此类推，直到堆中只有一个记录。 需解决的关键问题? 如何由一个无序序列建成一个堆（即初始建堆）？ 如何处理堆顶记录？ 如何调整剩余记录，成为一个新堆（即重建堆）？,堆调整,在一棵完全二叉树中，根结点的左右子树均是堆，如何调整根结点，使整个完全二叉树成为一个堆？,void sift ( int r , int k, int m ) /要筛选结
20、点的编号为k，堆中最后一个结点的编号为m i=k; j=2*i; /将筛选记录暂存 while (jrj) break; else ri rj; /将筛选记录移到正确位置 i=j; j=2*i; ,堆调整算法描述：,问题1：如何由一个无序序列建成一个堆？,算法描述： for (i=n/2; i=1; i-) sift(r, i, n) ;,最后一个结点（叶子）的序号是n， 则最后一个分支结点即为结点n的双亲， 其序号是n/2。,问题1：如何由一个无序序列建成一个堆？,问题2：如何处理堆顶记录？,对 应,对 应,算法描述： r1rn-i+1;,解决方法： 第 i 次处理堆顶是将堆顶记录r1与序列
21、中第n-i+1个记录rn-i+1交换。,问题2：如何处理堆顶记录？,问题3：如何调整剩余记录，成为一个新堆？,解决方法： 第 i 次调整剩余记录，此时，剩余记录有n-i个，调整根结点至第n-i个记录。,算法描述： sift(r, 1, n-i);,问题3：如何调整剩余记录，成为一个新堆？,堆排序算法,void HeapSort ( int r, int n) for (i=n/2; i=1; i-) /初建堆 sift(r, i, n) ; for (i=1; in; i+ ) r1rn-i+1; /移走堆顶 sift(r, 1, n-i); /重建堆 ,堆排序算法的性能分析,第1个for循环
22、是初始建堆，需要O(n)时间； 第2个for循环是输出堆顶重建堆，共需要取n-1次堆顶记录，第 i 次取堆顶记录重建堆需要O(log2i)时间，需要O(nlog2n)时间； 因此整个时间复杂度为O(nlog2n)，这是堆排序的最好、最坏和平均的时间代价。,10.8 归并排序,归并排序的主要操作是归并，其主要思想是：将若干有序序列逐步归并，最终得到一个有序序列。 归并：将两个或两个以上的有序序列合并成一个有序序列的过程。,基本思想：将一个具有n个待排序记录的序列看成是n个长度为1的有序序列，然后进行两两归并，得到n/2个长度为2的有序序列，再进行两两归并，得到n/4个长度为4的有序序列，直至得到
23、一个长度为n的有序序列为止。 需解决的关键问题? 如何将两个有序序列合成一个有序序列？ 怎样完成一趟归并？ 如何控制二路归并的结束？,问题1：如何将两个有序序列合成一个有序序列？,60 20 31 5 44 55 65,5,20,31,60,60 20 31 5 44 55 65,5,20,31,60,归并可以就地进行吗?,问题1：如何将两个有序序列合成一个有序序列？,在归并过程中，可能会破坏原来的有序序列，所以，将归并的结果存入另外一个数组中。,60 20 31 5 44 55 65,5,20,31,60,问题1：如何将两个有序序列合成一个有序序列？,60 20 31 5 44 55 65,
24、5,20,31,60,子序列的长度一定相等吗?,问题1：如何将两个有序序列合成一个有序序列？,60 20 31 5 44 55 65,5,20,31,60,问题1：如何将两个有序序列合成一个有序序列？,设相邻的有序序列为rs rm和rm+1 rt，归并成一个有序序列r1s r1t,问题1：如何将两个有序序列合成一个有序序列？,void Merge (int r , int r1 , int s, int m, int t ) i=s; j=m+1; k=s; while (i=m /后一个子序列 ,算法描述：,问题1：如何将两个有序序列合成一个有序序列？,问题2：怎样完成一趟归并？,60 20
25、 31 5 44 55 65,在一趟归并中，除最后一个有序序列外，其它有序序列中记录的个数相同，用长度h表示。,设参数i指向待归并序列的第一个记录，归并的步长是2h，在归并过程中，有以下三种情况：,若in-2h+1，则相邻两个有序表的长度均为h，执行一次归并，完成后i加2h，准备进行下一次归并；,i=1 n-2h+1=4,问题2：怎样完成一趟归并？,算法描述： while (in-2h+1) Merge (r, r1, i, i+h-1, i+2*h-1); i+=2*h; ,问题2：怎样完成一趟归并？,设参数i指向待归并序列的第一个记录，归并的步长是2h，在归并过程中，有以下三种情况：,若i
26、n-2h+1，则相邻两个有序表的长度均为h，执行一次归并，完成后i加2h，准备进行下一次归并；,若in-h+1，则表示仍有两个相邻有序表，一个长度为h，另一个长度小于h，则执行两个有序表的归并，完成后退出一趟归并。,i=4 n-2h+1=4 n-h+1=6,问题2：怎样完成一趟归并？,设参数i指向待归并序列的第一个记录，归并的步长是2h，在归并过程中，有以下三种情况：,算法描述： if (in-h+1) Merge (r, r1, i, i+h-1, n);,若in-h+1，则表示仍有两个相邻有序表，一个长度为h，另一个长度小于h，则执行两个有序表的归并，完成后退出一趟归并。,问题2：怎样完成
27、一趟归并？,设参数i指向待归并序列的第一个记录，归并的步长是2h，在归并过程中，有以下三种情况：,若in-h+1，则表明只剩下一个有序表，直接将该有序表送到r1的相应位置，完成后退出一趟归并。,i=9 n-h+1=8,问题2：怎样完成一趟归并？,设参数i指向待归并序列的第一个记录，归并的步长是2h，在归并过程中，有以下三种情况：,算法描述： if (i=n-h+1) for (k=i; k=n; k+) r1k=rk;,若in-h+1，则表明只剩下一个有序表，直接将该有序表送到r1的相应位置，完成后退出一趟归并。,问题2：怎样完成一趟归并？,设参数i指向待归并序列的第一个记录，归并的步长是2h
28、，在归并过程中，有以下三种情况：,void MergePass (int r , int r1 , int n, int h) i=1; while (in-2h+1) /情况1 Merge (r, r1, i, i+h-1, i+2*h-1); i+=2*h; if (in-h+1) Merge (r, r1, i, i+h-1, n); /情况2 else for (k=i; k=n; k+) /情况3 r1k=rk; ,一趟归并排序算法,解决方法： 开始时，有序序列的长度h=1，结束时，有序序列的长度h=n，用有序序列的长度来控制排序的结束。,问题3：如何控制二路归并的结束？,算法描述：
29、 void MergeSort (int r , int r1 , int n ) h=1; while (hn) MergePass (r, r1, n, h); h=2*h; MergePass (r1, r, n, h); h=2*h; ,问题3：如何控制二路归并的结束？,二路归并排序算法的性能分析,时间性能： 一趟归并操作是将r1rn中相邻的长度为h的有序序列进行两两归并，并把结果存放到r11r1n中，这需要O(n)时间。整个归并排序需要进行log2n趟，因此，总的时间代价是O(nlog2n)。这是归并排序算法的最好、最坏、平均的时间性能。 空间性能： 算法在执行时，需要占用与原始记录
30、序列同样数量的存储空间，因此空间复杂度为O(n)。,各种排序方法的比较,对排序算法应该从以下几个方面综合考虑： 时间复杂性； 空间复杂性； 稳定性； 算法简单性； 待排序记录个数n的大小； 记录本身信息量的大小； 关键码的分布情况。,时间复杂度比较,各种排序方法的比较,空间复杂度比较,各种排序方法的比较,稳定性比较,所有排序方法可分为两类， （1）一类是稳定的，包括直接插入排序、冒泡排序、直接选择排序和归并排序； （2）另一类是不稳定的，包括希尔排序、快速排序和堆排序。,算法简单性比较,从算法简单性看， （1）一类是简单算法，包括直接插入排序、直接选择排序和冒泡排序， （2）另一类是改进后的算
31、法，包括希尔排序、堆排序、快速排序和归并排序，这些算法都很复杂。,待排序的记录个数比较,从待排序的记录个数n的大小看，n越小，采用简单排序方法越合适，n越大，采用改进的排序方法越合适。因为n越小，O(n2)同O(nlog2n)的差距越小，并且输入和调试简单算法比输入和调试改进算法要少用许多时间。,记录本身信息量比较,记录本身信息量越大，移动记录所花费的时间就越多，所以对记录的移动次数较多的算法不利。,关键码的分布情况比较,当待排序记录按关键码有序时，插入排序和冒泡排序能达到O(n)的时间复杂度；对于快速排序而言，这是最坏的情况，此时的时间性能蜕化为O(n2)；选择排序、堆排序和归并排序的时间性能不随记录序列中关键字的分布而改变。,关键码的分布情况比较,当待排序记录按关键码有序时，插入排序和冒泡排序能达到O(n)的时间复杂度；对于快速排序而言，这是最坏的情况，此时的时间性能蜕化为O(n2)；选择排序、堆排序和归并排序的时间性能不随记录序列中关键字的分布而改变。,