第10章内部排序.ppt

Chapter10 排序,排序的基本概念直接插入排序起泡排序简单选择排序快速排序堆排序,6.1基本概念,排序,排序在计算机程序设计中有着非常重要的地位，许多具体应用要求对数据进行排序，而许多复杂的算法也要求以排序为基础。,排序,排序：将一个数据元素的任意序列，重新排列成一个按关键字有序的序列。数据表(datalist):它是待排序数据对象的有限集合。主关键字(key):数据对象有多个属性域,即多个数据成员组成,其中有一个属性域可用来区分对象,作为排序依据，称为关键字。也称为排序码。,排序,有关排序的几个基本问题稳定与不稳定内部排序与外部排序（本章只关注内部排序）性能的衡量,排序方法的分类,按照排序思想插入排序交换排序选择排序归并排序基数排序按照时间复杂度简单排序先进排序其他,6.2 直接插入排序,直接插入排序,基本思想：如果要向一个已经排序的顺序表中插入元素且保持表的有序性，则只需先依次比较，找到该元素的位置，然后移动元素进行插入即可。时间复杂度是O(n).基于这一思想，如果要对一个表进行排序，则可以将表看作两个部分，前N个元素已经排好序，再将第N+1个元素插入到前N个元素中。从N=0开始重复这个过程，直到N=L。,直接插入排序,直接插入排序,直接插入排序,直接插入排序的算法typedef int SortData;void InsertSort(SortData V,int n)/按非递减顺序对表进行排序 SortData temp;int i,j;for(i=1;i 0;j-)/从后向前顺序比较 if(temp Vj-1)Vj=Vj-1;else break;Vj=temp;,直接插入排序,时间复杂度为O(n2),折半插入排序,可见，插入排序由“查找”和“移动”两个基本过程组成，而查找这一步骤实际上是在一个有序表中进行的，因此可以用折半查找代替顺序查找来提高效率。但是由于移动这一过程无法被简化，因此折半插入排序仍然保值O(n2)的时间复杂度。,链表上的插入排序,链表上的插入排序仍然无法回避比较的过程，但是无需移动元素，从总体上看比顺序表上插入排序的性能好一些。,6.3 起泡排序,起泡排序,基本思想：基于两两比较的思想，对于N个元素，如果从第一个开始两两比较，将较小（较大）的一个交换到后面，则经过N-1次比较之后，最小（最大）的元素就被移动到最后一个位置。基于这一思想，如果要对一个表进行排序，则可以先对全部元素进行两两比较，将最小（最大）的元素移动到最后，再对前N-1元素重复过程，再对前N-2个直到所有的元素都排好序。,起泡排序,初始关键字,第一趟排序,第四趟排序,第二趟排序,第三趟排序,第五趟排序,起泡排序,起泡排序的基本算法typedef int SortData;void BubbleSort(SortData a,int n)for(int i=0;i aj+1)int temp=0;temp=aj;aj=aj+1;aj+1=temp;,起泡排序,最多做n-1趟起泡就能把所有对象排好序。在对象的初始排列已经按排序码从小到大排好序时,此算法只执行一趟起泡,做n-1次排序码比较,不移动对象。这是最好的情形。时间复杂度是O(n2)。,起泡排序,起泡排序的改进：在上面的程序中，如果序列经过很少几次循环就已经完成了排序，程序仍然会执行N-1次循环，造成多次循环做无用功。例如对于下面的序列，实际上经过一次循环就已经有序了。,起泡排序,对于这种情况，我们可以设置一个标志，如果一次循环发生数据交换，则令标志为1；如果一次循环不发生数据交换，则令标志为0，当发现标志为0时，就意味着已经排序完成了。,起泡排序,typedef int SortData;void BubbleSort(SortData V,int n)int i=1;int exchange=1;while(i=i;j-)if(Vj-1 Vj)/逆序 Swap(Vj-1,Vj);/交换 exchange=1;/标志置为1,有交换 i+;,起泡排序,扩展阅读：双冒泡排序。,链表上的起泡排序,思考：在链表上进行起泡排序，相比顺序表有哪些不同？1：从前向后的过程，需要借助两个指针来完成。2：需要用另外一个指针来指示已经被移动到最后的若干个元素。3：交换的过程有不同做法。实现起来比较繁琐，建议课下练习。,6.4 简单选择排序,简单选择排序,在一组数据中选择具有最小排序关键字的一个。若它不是这组数据中的第一个,则将它与这组数据中的第一个对调;在剩下的N-1个数据中重复执行第、步,直到完成。,简单选择排序,简单选择排序的排序过程,简单选择排序,简单选择排序的基本算法typedef int SortData;void SelectSort(SortData V,int n)for(int i=0;i n-1;i+)int k=i;/选择具有最小排序码的对象 for(int j=i+1;j n;j+)if(Vj Vk)k=j;/当前具最小排序码的对象 if(k!=i)/对换到第 i 个位置 Swap(Vi,Vk);,简单选择排序,时间复杂度仍为O(n2),链表上的简单选择排序,链表上的简单选择排序，最主要的区别仍然是元素的交换过程，可以采用与起泡相同的策略：只交换值交换节点,简单选择排序的递归实现,终止条件：表中只剩一个元素子问题：对后N-1个元素组成的表进行简单选择排序。子问题的操作：让第一个元素与最小元素进行交换，然后对剩余的N-1个元素进行简单选择排序。,简单选择排序的递归实现,void SelectSort(int a,int start,int n)if(n-start 1)int k=start;for(int i=start;i ai)k=i;int temp=astart;astart=ak;ak=temp;SelectSort(a,start+1,n);,三种排序算法的比较,上面介绍的三种排序算法都是基本排序算法，思路也比较简单和直接。时间复杂度为O(n2)基本过程都是将表划分为两部分，一部分已经排好序，一部分没有排好序，按照某种规则将未排序部分的元素加入到已排序部分。在实现时，都需要两层循环。,三种排序算法的比较,主要的区别就在于“如何从未排序的部分选择元素，加入到已排序部分？”插入排序：随意选择，有序插入。起泡排序：相邻元素两两比较，将最小（最大）的元素附加到已排序部分最前面（自然保证有序）。选择排序：查找最小（最大）元素，将这个元素附加到已排序部分的最后（自然保证有序）。,6.5 快速排序,快速排序,基本思想是任取待排序对象序列中的某个对象(例如取第一个对象)作为基准,按照该对象的排序码大小,将整个对象序列划分为左右两个子序列：左侧子序列中所有对象的排序码都小于或等于基准对象的排序码 右侧子序列中所有对象的排序码都大于基准对象的排序码,快速排序,经过这样的处理，基准对象就被安置在了正确的位置。然后分别对左右两个子序列重复施行上述方法，直到所有的对象都排在相应位置上为止。基准对象也称为枢轴（或支点）记录。,快速排序,快速排序,快速排序,快速排序的基本代码void QuickSort(SqList/对右序列同样处理,快速排序,int Partition(SqList,快速排序,快速排序的时间复杂度为O(nlogn)，是最快的内排序算法之一但是，由于快速排序的过程比较复杂，在对很短的序列进行排序时，它的速度不如插入/比较/选择排序。,快速排序,快速排序的改进判断序列的长度，当小于特定长度时，就改用其他排序方法。使用非递归的方法。,快速排序,快速排序是“20世纪十大著名算法”之一。单纯形法蒙特卡洛模拟快速傅里叶变换,6.6 堆排序,堆,首先介绍一种新的数据结构：堆(Heap)。堆是一种特殊的二叉树，首先，它是一个完全二叉树，并且对于任意一个非叶子节点，其叶子的值都大于（小于）该节点的值。相应的，称其为一个大顶堆（小顶堆）。注意：与二叉排序树的概念相区分。堆必须是一个完全二叉树节点值的大小只关注上下层而不分左右,堆,小顶堆,大顶堆,堆的建立,思考：如何将一个任意的完全二叉树变成一个堆。算法基本思路：从最后一个非叶子节点开始（从上到下，从左到右的顺序），对于每一个非叶子节点重复执行以下操作（以调整为大顶堆为例）：将节点的值(k)与它的两个叶子节点的值(k1,k2)进行比较,并且：如果满足大顶堆的性质（kk1且kk2），则不进行操作，退出循环。如果不满足，则将其与叶子节点中较大的一个进行交换，并继续执行循环。,堆的建立,以一个小顶堆的建立过程为例,堆的建立,以一个小顶堆的建立过程为例,注意这一次调整有点麻烦,堆的建立,以一个小顶堆的建立过程为例,堆的建立,以一个小顶堆的建立过程为例,堆的建立,至此，小顶堆的建立就完成了。,堆排序,那么如何使用“堆”这种数据结构来排序呢？只需要如下的过程：将堆中最后一个节点与根节点交换，并且将调整之后的最后一个节点输出出来，就得到了目前堆中最小（最大）的元素。将剩余的N-1个元素重新调整成堆（这一步只需要针对根节点进行调整就可以）。重复以上过程直到全部元素都被输出了。,堆排序,以利用大顶堆进行排序的过程为例：,交换8与49，并输出49,堆排序,以利用大顶堆进行排序的过程为例：,重新调整为大顶堆，然后交换25与16，并输出25,堆排序,以利用大顶堆进行排序的过程为例：,重新调整为大顶堆，然后交换25与8，并输出25,堆排序,以利用大顶堆进行排序的过程为例：,重新调整为大顶堆，然后交换21与8，并输出21,堆排序,以利用大顶堆进行排序的过程为例：,重新调整为大顶堆，然后交换8与16，并输出16,堆排序,以利用大顶堆进行排序的过程为例：,现在堆中只剩下一个元素了，输出，完成排序。,堆排序,堆排序的过程很繁琐，这导致它在数据量很小的情况下性能不佳。但是它的时间复杂度是nlogn级别的，特别是即使在最坏情况下，它的时间复杂度仍然保持nlogn，这是它相对快速排序最大的优势。,堆排序的程序实现,堆有一个很好的性质（思考：哪一点？），利用这一点，可以在一个顺序结构上实现堆排序。“完全二叉树”这一性质还决定了在顺序存储时，如果从顺序表的第一个位置开始存储（第0个位置留空），并且树的第一个节点存储在第k个位置，则它的根节点就在第k/2个位置。把握上面两点，二叉排序树的程序实现就很容易理解了。课本算法10.10,10.11.,