《内部排序》PPT课件.ppt

Chapter10 排序 2 排序的基本概念 直接插入排序 起泡排序 简单选择排序 快速排序 堆排序 6.1基本概念 4 排序 排序在计算机程序设计中有着非常重要的地位 ，许多具体应用要求对数据进行排序，而许多 复杂的算法也要求以排序为基础。 5 排序 排序：将一个数据元素的任意序列，重新排列 成一个按关键字有序的序列。 数据表(datalist): 它是待排序数据对象的有 限集合。 主关键字(key): 数据对象有多个属性域, 即 多个数据成员组成, 其中有一个属性域可用来 区分对象, 作为排序依据，称为关键字。也称 为排序码。 6 排序 有关排序的几个基本问题 l稳定与不稳定 l内部排序与外部排序（本章只关注内部排序） l性能的衡量 7 排序方法的分类 按照排序思想 l插入排序 l交换排序 l选择排序 l归并排序 l基数排序 按照时间复杂度 l简单排序 l先进排序 l其他 6.2 直接插入排序 9 直接插入排序 基本思想：如果要向一个已经排序的顺序表中插入元素基本思想：如果要向一个已经排序的顺序表中插入元素 且保持表的有序性，则只需先依次比较，找到该元素的且保持表的有序性，则只需先依次比较，找到该元素的 位置，然后移动元素进行插入即可。时间复杂度是位置，然后移动元素进行插入即可。时间复杂度是 O(nO(n).). 基于这一思想，如果要对一个表进行排序，则可以将表基于这一思想，如果要对一个表进行排序，则可以将表 看作两个部分，前看作两个部分，前N N个元素已经排好序，再将第个元素已经排好序，再将第N+1N+1个元个元 素插入到前素插入到前N N个元素中。从个元素中。从N=0N=0开始重复这个过程，直到开始重复这个过程，直到 N=LN=L。 10 直接插入排序 0 1 2 3 4 5 temp i = 1 i = 2 0 1 2 3 4 5 temp 212108082525494925*25* 1616 2121250808494925*25* 16162525 212125250808494925*25* 1616 2121252508084925*25* 16164949 212125250808494925*25* 1616 i = 3 212125250808494925* 161625*25* 212125250808494925*25*1616 11 直接插入排序 i = 4 i = 5 212125250808494925*25*16161616 212125250808494925*25*1616 2121252508494925*25*1616 212125250808494925*25*1616 0808 12 直接插入排序 直接插入排序的算法直接插入排序的算法 ltypedef int SortData; lvoid InsertSort ( SortData V , int n ) l l/按非递减顺序对表进行排序 l SortData temp; int i, j; l for ( i = 1; i 0; j- ) /从后向前顺序比较 l if ( temp aj+1) int temp = 0; temp = aj; aj = aj+1; aj+1 = temp; 20 起泡排序 最多做n-1趟起泡就能把所有对象排好序。 在对象的初始排列已经按排序码从小到大排好 序时,此算法只执行一趟起泡,做n-1次排序码比 较,不移动对象。这是最好的情形。 时间复杂度是O(n2)。 21 起泡排序 起泡排序的改进：在上面的程序中，如果序列 经过很少几次循环就已经完成了排序，程序仍 然会执行N-1次循环，造成多次循环做无用功。 例如对于下面的序列，实际上经过一次循环就 已经有序了。 212108082525494925251616 22 起泡排序 对于这种情况，我们可以设置一个标志，如果 一次循环发生数据交换，则令标志为1；如果一 次循环不发生数据交换，则令标志为0，当发现 标志为0时，就意味着已经排序完成了。 23 起泡排序 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+; 24 起泡排序 扩展阅读：双冒泡排序。 25 链表上的起泡排序 思考：在链表上进行起泡排序，相比顺序表有哪些不同？思考：在链表上进行起泡排序，相比顺序表有哪些不同？ l l 1 1：从前向后的过程，需要借助两个指针来完成。：从前向后的过程，需要借助两个指针来完成。 l l 2 2：需要用另外一个指针来指示已经被移动到最后的若干个元素。：需要用另外一个指针来指示已经被移动到最后的若干个元素。 l l 3 3：交换的过程有不同做法。：交换的过程有不同做法。 实现起来比较繁琐，建议课下练习。实现起来比较繁琐，建议课下练习。 6.4 简单选择排序 27 简单选择排序 在一组数据中选择具有最小排序关键字的一个。 若它不是这组数据中的第一个, 则将它与这组数据 中的第一个对调; 在剩下的N-1个数据中重复执行第、步, 直到 完成。 28 简单选择排序 简单选择排序的排序过程 212125 25 4949 25*25* 1616 0808 212125* 25* i i = 0= 0 4949 2525 1616 2525 1616 0808 4949 0808 25*25* 4949 2121 i i = 1= 1 i i = 2= 2 0808 1616 25*25*25252121 初始初始 交换交换21,0821,08 交换交换25,1625,16 交换交换49,2149,21 29 简单选择排序 简单选择排序的基本算法 typedef int SortData; void SelectSort ( SortData V, int n ) for ( int i = 0; i 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 三种排序算法的比较 上面介绍的三种排序算法都是基本排序算法，思路 也比较简单和直接。 时间复杂度为O(n2) 基本过程都是将表划分为两部分，一部分已经排好序，一 部分没有排好序，按照某种规则将未排序部分的元素加入 到已排序部分。 在实现时，都需要两层循环。 35 三种排序算法的比较 主要的区别就在于“如何从未排序的部分选择元素， 加入到已排序部分？” 插入排序：随意选择，有序插入。 起泡排序：相邻元素两两比较，将最小（最大）的元素附 加到已排序部分最前面（自然保证有序）。 选择排序：查找最小（最大）元素，将这个元素附加到已 排序部分的最后（自然保证有序） 。 6.5 快速排序 37 快速排序 基本思想是任取待排序对象序列中的某个对象 (例 如取第一个对象) 作为基准, 按照该对象的排序码 大小,将整个对象序列划分为左右两个子序列： 左侧子序列中所有对象的排序码都小于或等于基准对象 的排序码 右侧子序列中所有对象的排序码都大于基准对象的排序 码 38 快速排序 经过这样的处理，基准对象就被安置在了正确的 位置。 然后分别对左右两个子序列重复施行上述方法， 直到所有的对象都排在相应位置上为止。 基准对象也称为枢轴（或支点）记录。 39 快速排序 212108082525494925*25*1616 初始关键字 08082525494925*25*16162121 08082525494925*25*1616 0808 2525 494925*25*1616 08082525494925*25*1616 08082525494925*25*16162121 prikey 一次交换 二次交换 三次交换 四次交换 完成一趟排序 i j i j j i i j j i j i 40 快速排序 08082525494925*25*16162121 完成一趟排序 分别进行快速排序 08082525494925*25*16162121 有序序列 08082525494925*25*16162121 41 快速排序 快速排序的基本代码 void QuickSort ( SqList L.rlow L.rhigh; /小于基准的移到左侧 while(low L.rlow ; /大于基准的移到右侧 return low; 43 快速排序 快速排序的时间复杂度为O(nlogn)，是最快的内 排序算法之一 但是，由于快速排序的过程比较复杂，在对很短 的序列进行排序时，它的速度不如插入/比较/选择 排序。 44 快速排序 快速排序的改进 判断序列的长度，当小于特定长度时，就改用其他排序 方法。 使用非递归的方法。 45 快速排序 快速排序是“20世纪十大著名算法”之一。 单纯形法 蒙特卡洛模拟 快速傅里叶变换 6.6 堆排序 47 堆 首先介绍一种新的数据结构：堆(Heap)。 堆是一种特殊的二叉树，首先，它是一个完全二 叉树，并且对于任意一个非叶子节点，其叶子的 值都大于（小于）该节点的值。相应的，称其为 一个大顶堆（小顶堆）。 注意：与二叉排序树的概念相区分。 堆必须是一个完全二叉树 节点值的大小只关注上下层而不分左右 48 堆 09 09 87 87 78 784545 65 6531 315323 23 53 17 17 小顶堆 大顶堆 49 堆的建立 思考：如何将一个任意的完全二叉树变成一个堆 。 算法基本思路：从最后一个非叶子节点开始（从 上到下，从左到右的顺序），对于每一个非叶子 节点重复执行以下操作（以调整为大顶堆为例） ： 将节点的值(k)与它的两个叶子节点的值(k1,k2)进行比 较,并且： 如果满足大顶堆的性质（kk1且kk2），则不进行操 作，退出循环。 如果不满足，则将其与叶子节点中较大的一个进行交 换，并继续执行循环。 50 堆的建立 以一个小顶堆的建立过程为例 5353 17177878 09 23456587 最后一个 09 23 456587 倒数第二个 51 堆的建立 以一个小顶堆的建立过程为例 5353 17 17787809 23 45 65 87 09 23 45 65 87 注意这一次调整有点麻烦 52 堆的建立 以一个小顶堆的建立过程为例 53 17177878 09 23 45 65 87 09 23 45 65 87 53 53 堆的建立 以一个小顶堆的建立过程为例 53 1717 7878 09 23 45 65 87 09 2345 65 8753 54 堆的建立 至此，小顶堆的建立就完成了。 55 堆排序 那么如何使用“堆”这种数据结构来排序呢？ 只需要如下的过程： 将堆中最后一个节点与根节点交换，并且将调整之后 的最后一个节点输出出来，就得到了目前堆中最小（ 最大）的元素。 将剩余的N-1个元素重新调整成堆（这一步只需要针 对根节点进行调整就可以）。 重复以上过程直到全部元素都被输出了。 56 堆排序 以利用大顶堆进行排序的过程为例： 4949 2525 25*25* 2121 16160808 0 1 2 345 0808 2525 25*25*1616 2121 4949 0 2 543 1 交换8与49，并输出49 57 堆排序 以利用大顶堆进行排序的过程为例： 2525 25*25* 0808 2121 16164949 0 1 2 345 1616 25*25* 08082525 2121 4949 0 2 543 1 重新调整为大顶堆，然后交换25与16，并输出25 58 堆排序 以利用大顶堆进行排序的过程为例： 25*25* 1616 0808 2121 25254949 0 1 2 345 0808 1616 25*25*2525 2121 4949 0 2 543 1 重新调整为大顶堆，然后交换25与8，并输出25 59 堆排序 以利用大顶堆进行排序的过程为例： 2121 1616 25*25* 0808 25254949 0 1 2 345 0808 1616 25*25*2525 2121 4949 0 2 543 1 重新调整为大顶堆，然后交换21与8，并输出21 60 堆排序 以利用大顶堆进行排序的过程为例： 1616 0808 25*25* 2121 25254949 0 1 2 345 0808 1616 25*25*2525 2121 4949 0 2 543 1 重新调整为大顶堆，然后交换8与16，并输出16 61 堆排序 以利用大顶堆进行排序的过程为例： 0808 0 现在堆中只剩下一个元素了，输出，完成排序。 62