第10章内部排序.ppt

《第10章内部排序.ppt》由会员分享，可在线阅读，更多相关《第10章内部排序.ppt（63页珍藏版）》请在优知文库上搜索。

1、Chapter10 排序2 排序的基本概念直接插入排序起泡排序简单选择排序快速排序堆排序6.1基本概念4 排序排序在计算机程序设计中有着非常重要的地位，许多具体应用要求对数据进行排序，而许多复杂的算法也要求以排序为基础。5 排序排序：将一个数据元素的任意序列，重新排列成一个按关键字有序的序列。数据表(datalist):它是待排序数据对象的有限集合。主关键字(key):数据对象有多个属性域,即多个数据成员组成,其中有一个属性域可用来区分对象,作为排序依据，称为关键字。也称为排序码。6 排序有关排序的几个基本问题l稳定与不稳定l内部排序与外部排序（本章只关注内部排序）l性能的衡量7 排序方法的分

2、类按照排序思想l插入排序l交换排序l选择排序l归并排序l基数排序按照时间复杂度l简单排序l先进排序l其他6.2 直接插入排序9 直接插入排序10 直接插入排序0 1 2 3 4 5 temp i=1i=20 1 2 3 4 5 temp252525494949i=3252525*11 直接插入排序i=4i=516161616161608080812 直接插入排序ltypedef int SortData;lvoid InsertSort(SortData V,int n)ll/按非递减顺序对表进行排序l SortData temp;int i,j;l for(i=1;i 0;j-)/从后向前顺

3、序比较 l if(temp Vj-1)Vj=Vj-1;l else break;l Vj=temp;l l 13 直接插入排序时间复杂度为O(n2)14 折半插入排序15 链表上的插入排序6.3 起泡排序17 起泡排序18 起泡排序初始关键字第一趟排序第四趟排序第二趟排序第三趟排序第五趟排序19 起泡排序typedef int SortData;typedef int SortData;void BubbleSort(SortData a,int n)void BubbleSort(SortData a,int n)for(int i=0;in;i+)for(int i=0;in;i+)for

4、(int j=0;jn-i-1;j+)for(int j=0;j aj+1)if(aj aj+1)int temp=0;int temp=0;temp=aj;temp=aj;aj=aj+1;aj=aj+1;aj+1=temp;aj+1=temp;20 起泡排序最多做n-1趟起泡就能把所有对象排好序。在对象的初始排列已经按排序码从小到大排好序时,此算法只执行一趟起泡,做n-1次排序码比较,不移动对象。这是最好的情形。时间复杂度是O(n2)。21 起泡排序起泡排序的改进：在上面的程序中，如果序列经过很少几次循环就已经完成了排序，程序仍然会执行N-1次循环，造成多次循环做无用功。例如对于下面的序列，

5、实际上经过一次循环就已经有序了。22 起泡排序对于这种情况，我们可以设置一个标志，如果一次循环发生数据交换，则令标志为1；如果一次循环不发生数据交换，则令标志为0，当发现标志为0时，就意味着已经排序完成了。23 起泡排序typedef int SortData;typedef int SortData;void BubbleSort(SortData V,int n)void BubbleSort(SortData V,int n)int i=1;int i=1;int exchange=1;int exchange=1;while(i n&exchange)while(i=i;j-)for(

6、int j=n-1;j=i;j-)if(Vj-1 Vj)if(Vj-1 Vj)/逆序逆序 Swap(Vj-1,Vj);/Swap(Vj-1,Vj);/交换交换 exchange=1;/exchange=1;/标志置为标志置为1,1,有交换有交换 i+;i+;24 起泡排序扩展阅读：双冒泡排序。25 链表上的起泡排序6.4 简单选择排序27 简单选择排序在一组数据中选择具有最小排序关键字的一个。若它不是这组数据中的第一个,则将它与这组数据中的第一个对调;在剩下的N-1个数据中重复执行第、步,直到完成。28 简单选择排序简单选择排序的排序过程29 简单选择排序简单选择排序的基本算法typedef

7、int SortData;typedef int SortData;void SelectSort(SortData V,int n)void SelectSort(SortData V,int n)for(int i=0;i n-1;i+)for(int i=0;i n-1;i+)int k=i;/int k=i;/选择具有最小排序码的对象选择具有最小排序码的对象 for(int j=i+1;j n;j+)for(int j=i+1;j n;j+)if(Vj Vk)if(Vj 1)int k=start;for(int i=start;i ai)k=i;int temp=astart;ast

8、art=ak;ak=temp;SelectSort(a,start+1,n);34 三种排序算法的比较上面介绍的三种排序算法都是基本排序算法，思路也比较简单和直接。l时间复杂度为O(n2)l基本过程都是将表划分为两部分，一部分已经排好序，一部分没有排好序，按照某种规则将未排序部分的元素加入到已排序部分。l在实现时，都需要两层循环。35 三种排序算法的比较主要的区别就在于“如何从未排序的部分选择元素，加入到已排序部分？”l插入排序：随意选择，有序插入。l起泡排序：相邻元素两两比较，将最小（最大）的元素附加到已排序部分最前面（自然保证有序）。l选择排序：查找最小（最大）元素，将这个元素附加到已排序

9、部分的最后（自然保证有序）。6.5 快速排序37 快速排序基本思想是任取待排序对象序列中的某个对象(例如取第一个对象)作为基准,按照该对象的排序码大小,将整个对象序列划分为左右两个子序列：l左侧子序列中所有对象的排序码都小于或等于基准对象的排序码 l右侧子序列中所有对象的排序码都大于基准对象的排序码38 快速排序经过这样的处理，基准对象就被安置在了正确的位置。然后分别对左右两个子序列重复施行上述方法，直到所有的对象都排在相应位置上为止。基准对象也称为枢轴（或支点）记录。39 快速排序初始关键字初始关键字prikey一次交换一次交换二次交换二次交换三次交换三次交换四次交换四次交换完成一趟排序完成

10、一趟排序ijijjiijji ji40 快速排序完成一趟排序完成一趟排序分别进行快速排序分别进行快速排序有序序列有序序列41 快速排序快速排序的基本代码void QuickSort(SqList&L,int low,int high)/在序列lowhigh 中递归地进行快速排序 if(low high)int pivotloc=Partition(L,low,high);/划分 QuickSort(L,low,pivotloc-1);/对左序列同样处理 QuickSort(L,pivotloc+1,high);/对右序列同样处理 42 快速排序int Partition(SqList&L,in

11、t low,int high)pivotkey=L.rlow.key;/基准对象关键字 while(lowhigh)while(low=pivotkey)-high;L.rlow L.rhigh;/小于基准的移到左侧 while(lowhigh&L.rlow.key L.rlow;/大于基准的移到右侧 return low;43 快速排序快速排序的时间复杂度为O(nlogn)，是最快的内排序算法之一但是，由于快速排序的过程比较复杂，在对很短的序列进行排序时，它的速度不如插入/比较/选择排序。44 快速排序快速排序的改进l判断序列的长度，当小于特定长度时，就改用其他排序方法。l使用非递归的方法。

12、45 快速排序快速排序是“20世纪十大著名算法”之一。l单纯形法l蒙特卡洛模拟l快速傅里叶变换6.6 堆排序47 堆首先介绍一种新的数据结构：堆(Heap)。堆是一种特殊的二叉树，首先，它是一个完全二叉树，并且对于任意一个非叶子节点，其叶子的值都大于（小于）该节点的值。相应的，称其为一个大顶堆（小顶堆）。注意：与二叉排序树的概念相区分。l堆必须是一个完全二叉树l节点值的大小只关注上下层而不分左右48 堆090987877878454565653131532323531717小顶堆大顶堆49 堆的建立思考：如何将一个任意的完全二叉树变成一个堆。算法基本思路：从最后一个非叶子节点开始（从上到下，从

13、左到右的顺序），对于每一个非叶子节点重复执行以下操作（以调整为大顶堆为例）：l将节点的值(k)与它的两个叶子节点的值(k1,k2)进行比较,并且：l如果满足大顶堆的性质（kk1且kk2），则不进行操作，退出循环。l如果不满足，则将其与叶子节点中较大的一个进行交换，并继续执行循环。50 堆的建立以一个小顶堆的建立过程为例5353171778780923456587最后一个最后一个0923456587倒数第二个倒数第二个51 堆的建立以一个小顶堆的建立过程为例53531717787809234565870923456587注意这一次调整有点麻烦52 堆的建立以一个小顶堆的建立过程为例5317177

14、878092345658709234565875353 堆的建立以一个小顶堆的建立过程为例5317177878092345658709234565875354 堆的建立至此，小顶堆的建立就完成了。55 堆排序那么如何使用“堆”这种数据结构来排序呢？只需要如下的过程：l将堆中最后一个节点与根节点交换，并且将调整之后的最后一个节点输出出来，就得到了目前堆中最小（最大）的元素。l将剩余的N-1个元素重新调整成堆（这一步只需要针对根节点进行调整就可以）。l重复以上过程直到全部元素都被输出了。56 堆排序以利用大顶堆进行排序的过程为例：012345025431交换8与49，并输出4957 堆排序以利用大

15、顶堆进行排序的过程为例：012345025431重新调整为大顶堆，然后交换25与16，并输出2558 堆排序以利用大顶堆进行排序的过程为例：012345025431重新调整为大顶堆，然后交换25与8，并输出2559 堆排序以利用大顶堆进行排序的过程为例：012345025431重新调整为大顶堆，然后交换21与8，并输出2160 堆排序以利用大顶堆进行排序的过程为例：012345025431重新调整为大顶堆，然后交换8与16，并输出1661 堆排序以利用大顶堆进行排序的过程为例：0现在堆中只剩下一个元素了，输出，完成排序。62 堆排序堆排序的过程很繁琐，这导致它在数据量很小的情况下性能不佳。但是它的时间复杂度是nlogn级别的，特别是即使在最坏情况下，它的时间复杂度仍然保持nlogn，这是它相对快速排序最大的优势。63 堆排序的程序实现堆有一个很好的性质（思考：哪一点？），利用这一点，可以在一个顺序结构上实现堆排序。“完全二叉树”这一性质还决定了在顺序存储时，如果从顺序表的第一个位置开始存储（第0个位置留空），并且树的第一个节点存储在第k个位置，则它的根节点就在第k/2个位置。把握上面两点，二叉排序树的程序实现就很容易理解了。l课本算法10.10,10.11.