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