《内部排序》PPT课件.ppt

《《内部排序》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《内部排序》PPT课件.ppt（63页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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

2、排序思想l插入排序l交换排序l选择排序l归并排序l基数排序按照时间复杂度l简单排序l先进排序l其他6.2 直接插入排序9 直接插入排序 基本思想：如果要向一个已经排序的顺序表中插入元素基本思想：如果要向一个已经排序的顺序表中插入元素且保持表的有序性，则只需先依次比较，找到该元素的且保持表的有序性，则只需先依次比较，找到该元素的位置，然后移动元素进行插入即可。时间复杂度是位置，然后移动元素进行插入即可。时间复杂度是O(n).O(n).基于这一思想，如果要对一个表进行排序，则可以将表基于这一思想，如果要对一个表进行排序，则可以将表看作两个部分，前看作两个部分，前N N个元素已经排好序，再将第个元素

3、已经排好序，再将第N+1N+1个元个元素插入到前素插入到前N N个元素中。从个元素中。从N=0N=0开始重复这个过程，直到开始重复这个过程，直到N=LN=L。10 直接插入排序0 1 2 3 4 5 temp i=1i=20 1 2 3 4 5 temp212108082525494925*25*16162121250808494925*25*16162525212125250808494925*25*16162121252508084925*25*16164949212125250808494925*25*1616i=3212125250808494925*161625*25*2121252

4、50808494925*25*161611 直接插入排序i=4i=5212125250808494925*25*16161616212125250808494925*25*16162121252508494925*25*1616212125250808494925*25*1616080812 直接插入排序 直接插入排序的算法直接插入排序的算法ltypedef int SortData;lvoid InsertSort(SortData V,int n)ll/按非递减顺序对表进行排序l SortData temp;int i,j;l for(i=1;i 0;j-)/从后向前顺序比较 l if(t

5、emp Vj-1)Vj=Vj-1;l else break;l Vj=temp;l l 13 直接插入排序时间复杂度为O(n2)14 折半插入排序 可见，插入排序由可见，插入排序由“查找查找”和和“移动移动”两个基本过程组两个基本过程组成，而查找这一步骤实际上是在一个有序表中进行的，成，而查找这一步骤实际上是在一个有序表中进行的，因此可以用折半查找代替顺序查找来提高效率。因此可以用折半查找代替顺序查找来提高效率。但是由于移动这一过程无法被简化，因此折半插入排序但是由于移动这一过程无法被简化，因此折半插入排序仍然保值仍然保值O(n2)O(n2)的时间复杂度。的时间复杂度。15 链表上的插入排序

6、链表上的插入排序仍然无法回避比较的过程，但是无需链表上的插入排序仍然无法回避比较的过程，但是无需移动元素，从总体上看比顺序表上插入排序的性能好一移动元素，从总体上看比顺序表上插入排序的性能好一些。些。6.3 起泡排序17 起泡排序 基本思想：基于两两比较的思想，对于基本思想：基于两两比较的思想，对于N N个元素，如果个元素，如果从第一个开始两两比较，将较小（较大）的一个交换到从第一个开始两两比较，将较小（较大）的一个交换到后面，则经过后面，则经过N-1N-1次比较之后，最小（最大）的元素就次比较之后，最小（最大）的元素就被移动到最后一个位置。被移动到最后一个位置。基于这一思想，如果要对一个表进

7、行排序，则可以先对基于这一思想，如果要对一个表进行排序，则可以先对全部元素进行两两比较，将最小（最大）的元素移动到全部元素进行两两比较，将最小（最大）的元素移动到最后，再对前最后，再对前N-1N-1元素重复过程，再对前元素重复过程，再对前N-2N-2个个直到直到所有的元素都排好序。所有的元素都排好序。18 起泡排序2 21 10 08 82 25 5 4 49 9 2 25 5 1 16 62 21 14 49 92 25 5 2 25 5 1 16 6 0 08 82 21 14 49 92 25 52 25 51 16 6 0 08 82 21 14 49 92 25 5 2 25 51

8、16 6 0 08 82 21 14 49 92 25 5 2 25 51 16 6 0 08 8初始关键字第一趟排序第四趟排序第二趟排序第三趟排序2 21 14 49 92 25 5 2 25 51 16 60 08 8第五趟排序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(int j=0;jn

9、-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次循环，造成多次循环做无用功。例如对于下面的序列，实际上经过一次循环就已

10、经有序了。2 21 10 08 82 25 54 49 92 25 51 16 622 起泡排序对于这种情况，我们可以设置一个标志，如果一次循环发生数据交换，则令标志为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&e

11、xchange)while(i=i;j-)for(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 链表上的起泡排序 思考：在链表上进行起泡排序，相比顺序表有哪些不同？思考：在链表上进行起泡排序，相比顺序表有哪些不同？l l1 1：从前向后的过程，需要借助两个指针来完成。：从前向后的过程，需要借助两个指针来完成。l l2 2：需要用另外一个指针来指

12、示已经被移动到最后的若干个元素。：需要用另外一个指针来指示已经被移动到最后的若干个元素。l l3 3：交换的过程有不同做法。：交换的过程有不同做法。实现起来比较繁琐，建议课下练习。实现起来比较繁琐，建议课下练习。6.4 简单选择排序27 简单选择排序在一组数据中选择具有最小排序关键字的一个。若它不是这组数据中的第一个,则将它与这组数据中的第一个对调;在剩下的N-1个数据中重复执行第、步,直到完成。28 简单选择排序简单选择排序的排序过程21212525494925*25*16160808212125*25*i=0=04949252516162525161608084949080825*25*4

13、9492121i=1=1i=2=20808161625*25*25252121初始初始初始初始交换交换交换交换21,0821,08交换交换交换交换25,1625,16交换交换交换交换49,2149,2129 简单选择排序简单选择排序的基本算法typedef 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;/选择具有最小排序码的对

14、象选择具有最小排序码的对象 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;astart=ak;ak=temp;SelectSort(a,start+1,n);34 三种排序算法的比较上面介绍的三种排序算法都是基本排序算法，思路也比较简单和直接。l时间复杂度为O(n2)l基本过程都是将表划分为两部分，一部分已经排好序，一部分没有排好序，按照某种规则将未排序部分的元素加入到已排序部分。l在实现时，都需要两层循环。35 三种

15、排序算法的比较主要的区别就在于“如何从未排序的部分选择元素，加入到已排序部分？”l插入排序：随意选择，有序插入。l起泡排序：相邻元素两两比较，将最小（最大）的元素附加到已排序部分最前面（自然保证有序）。l选择排序：查找最小（最大）元素，将这个元素附加到已排序部分的最后（自然保证有序）。6.5 快速排序37 快速排序基本思想是任取待排序对象序列中的某个对象(例如取第一个对象)作为基准,按照该对象的排序码大小,将整个对象序列划分为左右两个子序列：l左侧子序列中所有对象的排序码都小于或等于基准对象的排序码 l右侧子序列中所有对象的排序码都大于基准对象的排序码38 快速排序经过这样的处理，基准对象就被

16、安置在了正确的位置。然后分别对左右两个子序列重复施行上述方法，直到所有的对象都排在相应位置上为止。基准对象也称为枢轴（或支点）记录。39 快速排序212108082525494925*25*1616初始关键字初始关键字08082525494925*25*1616212108082525494925*25*161608082525494925*25*161608082525494925*25*161608082525494925*25*16162121prikey一次交换一次交换二次交换二次交换三次交换三次交换四次交换四次交换完成一趟排序完成一趟排序ijijjiijji ji40 快速排序080

17、82525494925*25*16162121完成一趟排序完成一趟排序分别进行快速排序分别进行快速排序08082525494925*25*16162121有序序列有序序列08082525494925*25*1616212141 快速排序快速排序的基本代码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

18、+1,high);/对右序列同样处理 42 快速排序int Partition(SqList&L,int 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)，是最快的内排序算法之一但是，由于快速排序的过程比较复杂，在对很短的序列进行排序时，它的速度不如插入/比较/选择排序。4

19、4 快速排序快速排序的改进l判断序列的长度，当小于特定长度时，就改用其他排序方法。l使用非递归的方法。45 快速排序快速排序是“20世纪十大著名算法”之一。l单纯形法l蒙特卡洛模拟l快速傅里叶变换6.6 堆排序47 堆首先介绍一种新的数据结构：堆(Heap)。堆是一种特殊的二叉树，首先，它是一个完全二叉树，并且对于任意一个非叶子节点，其叶子的值都大于（小于）该节点的值。相应的，称其为一个大顶堆（小顶堆）。注意：与二叉排序树的概念相区分。l堆必须是一个完全二叉树l节点值的大小只关注上下层而不分左右48 堆090987877878454565653131532323531717小顶堆大顶堆49 堆

20、的建立思考：如何将一个任意的完全二叉树变成一个堆。算法基本思路：从最后一个非叶子节点开始（从上到下，从左到右的顺序），对于每一个非叶子节点重复执行以下操作（以调整为大顶堆为例）：l将节点的值(k)与它的两个叶子节点的值(k1,k2)进行比较,并且：l如果满足大顶堆的性质（kk1且kk2），则不进行操作，退出循环。l如果不满足，则将其与叶子节点中较大的一个进行交换，并继续执行循环。50 堆的建立以一个小顶堆的建立过程为例5353171778780923456587最后一个最后一个0923456587倒数第二个倒数第二个51 堆的建立以一个小顶堆的建立过程为例5353171778780923456

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

22、序以利用大顶堆进行排序的过程为例：4949252525*25*2121161608080123450808252525*25*161621214949025431交换8与49，并输出4957 堆排序以利用大顶堆进行排序的过程为例：252525*25*0808212116164949012345161625*25*0808252521214949025431重新调整为大顶堆，然后交换25与16，并输出2558 堆排序以利用大顶堆进行排序的过程为例：25*25*161608082121252549490123450808161625*25*252521214949025431重新调整为大顶堆，然后

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