09数据结构6—排序课件.pptVIP

第 一章　 数据结构 ;1.6 内部排序;1.排序的功能：将一个数据元素（或记录）的任意序列，重 新排成一个按关键字有序的序列。 2.内部排序与外部排序 根据排序时数据所占用存储器的不同,可将排序分为两类: 内部排序:整个排序过程完全在内存中进行. 外部排序:由于待排序记录数据量太大,内存无法容纳 全部数据,排序需要借助外部存储设备才能完成. 排序算法评价： 算法执行时间(最好、最差及平均情况) 需要附加空间大小;插入排序的基本思想： ;1.直接插入排序: 思路：认可第1个记录已排好序，然后将第2个到第n个记录依次插入到前面已排好序的记录组成的文件中。 具体过程(第i个记录Ri插入到前面i-1个已排好序的记录中) 将Ri的排序码与前面已排好序的排序码从右向左依次比较，找到Ri应插入的位置；将该位置以后直到Ri-1各记录顺序后移,空出位置插入Ri。;例直接插入排序:;该算法适合于n 较小的情况，时间复杂度为O(n2).;1.直接插入排序: 时效分析 ;2、折半插入排序 折半插入排序在寻找插入位置时，不是逐个比较而是利用折半查找的原理寻找插入位置。待排序元素越多，改进效果越明显。 ;3 .希尔排序 ;举例: 有一个含有14个数的序列,使用希尔排序进行升序排序 ( 39,80,76,41,13,29,50,78,30,11,100,7,41,86 ) 取增量：5，3，1;h=5;h=3;13 7 39 29 11 41 30 76 41 50 86 80 78 100;3 .希尔排序 ; 对待排序记录两两比较排序码，不满足排序顺序则交换。直到任何两个记录排序码满足排序要求。;1. 冒泡排序 基本思想：相邻元素两两比较，逆序则换。 第一趟冒泡排序：首先第一个元素与第二个元素比较，逆序则 交换；然后第二个元素与第三个元素比较；直到第n-1个元素与第n个元素比较为止。结果（关键字）最大的元素放在n位置。 第二趟冒泡排序：对前面n-1个元素进行相同操作，结果 次大元素放在n-1位置上。 第i趟冒泡排序：对前面n-i+1个元素进行相同操作，结 果(n-i+1)中最大元素放在(n-i+1)位置上。; ;for(j=1;j=9;j++) { flag=1; for(i=1;i=10-j;i++) if(a[i]a[i+1]) {flag=0; t=a[i]; a[i]=a[i+1]; a[i+1]=t; } if(flag) break; } (P48改进？) ;2. 快速排序 ;2. 快速排序 ;27 39 11 76 96 66 50;49 39 66 96 76 11 27 50 ;;1. 直接选择排序 ;Ch5_201.c;;首先包括n个元素的序列建堆,输出堆顶最小值。得到n个 元素中最小元素。 然后再对剩下n-1个元素重建堆,输出堆顶元素。得到n个 元素中次小元素。 反复执行(直到剩下子序列为空)，便得到一个有序列。;举例:一个无序序列(49,39,66,96,76,11,27,50)建小根堆的过程 1. 从第一个非叶子结点(序号=n/2=8/2=4,即图中值为96的结点开始筛选,筛选 原则是保证父结点的值要小于或等于叶子接点 ; 目前的堆中,堆顶元素11为最小值,输出后,重新对n-1个元素重新建一个新堆, 新堆中的堆顶是剩余的n-1个元素中的最小值,n个元素中的次最小值.;举例:输出堆顶元素并建新堆过程 ; 27;继续此过程，直到最后剩一个元素;总结;查找与排序补充习题讲解;5. 设待排序关键码序列为（33、18、9、25、67、82、53、 95、12、70），要按关键码值递增的顺???排序，采取以 第一个关键码为分界元素的快速排序法，第一趟排序完 成后关键码33被放到了第____个位置。 A. 3 B. 5 C. 7 D. 9 6. 希尔排序法属于哪一种类型的排序法______。 A. 交换类排序