[工学]数据结构 ch10 排序.ppt

4/19/2019,第十章 排序,10.1概述,10.2 插入排序,10.3 交换排序,10.4 选择排序,10.5 归并排序,10.6 基数排序,4/19/2019,10.1概述,一、什么是排序？,二、内部排序和外部排序,三、内部排序的方法,4/19/2019,10.1概述,排序是计算机内经常进行的一种操作，其目的是将一组“无序”的记录序列调整为“有序”的记录序列。,一、什么是排序？,例如：将下列关键字序列 52, 49, 80, 36, 14, 58, 61, 23, 97, 75 调整为 14, 23, 36, 49, 52, 58, 61 ,75, 80, 97,4/19/2019,一般情况下， 假设含n个记录的序列为 R1, R2, ， Rn 其相应的关键字序列为 K1, K2, ，Kn 这些关键字相互之间可以进行比较，即在它们之间存在着这样一个关系 Kp1Kp2Kpn 按此固有关系将式(1)的记录序列重新排列为 Rp1, Rp2, ，Rpn 的操作称作排序。,4/19/2019,二、内部排序和外部排序,在本章内先讨论内部排序的各种方法，然后介绍外部排序的基本过程。,若整个排序过程不需要访问外存便能完成，则称此类排序问题为内部排序；,反之，若参加排序的记录数量很大，整个序列的排序过程不可能在内存中完成，则称此类排序问题为外部排序。,4/19/2019,三、内部排序的方法,有序序列区,无序序列区,内部排序的过程是一个逐步扩大记录的有序序列长度的过程。在排序的过程中，参与排序的记录序列中存在两个区域：有序区和无序区。,使有序区中记录的数目增加一个或几个的操作称为一趟排序。,有序序列区,无序序列区,4/19/2019,1.插入类 将无序子序列中的一个或几个记录“插入”到有序序列中，从而增加记录的有序子序列的长度；,逐步扩大记录有序序列长度的方法大致有下列几类：,2.交换类 通过“交换”无序序列中的记录从而得到其中关键字最小或最大的记录，并将它加入到有序子序列中，以此方法增加记录的有序子序列的长度;,4/19/2019,3.选择类 从记录的无序子序列中“选择”关键字最小或最大的记录，并将它加入到有序子序列中，以此方法增加记录的有序子序列的长度;,4. 归并类 通过“归并”两个或两个以上的记录有序子序列，逐步增加记录有序序列的长度;,5.其它方法,下面将对每一类的排序算法介绍一至两个排序算法。,4/19/2019,有序序列R1i-1,无序序列 Rin,Ri,假设在排序过程中，记录序列R1n的状态为：,有序序列R1i,无序序列 Ri+1n,则一趟直接插入排序的基本思想为： 将记录Ri插入到有序子序列R1i-1中，使记录的有序序列从R1i-1变为R1i。,10.2 插入排序,4/19/2019,显然，完成这个“插入”需分三步进行：,2将Rj+1i-1中的记录后移一个位置；,3将Ri复制到Rj+1的位置上。,1查找Ri的插入位置j+1；,R1j Ri Rj+1i-1,4/19/2019,一、直接插入排序,二、折半插入排序,三、希尔排序,10.2 插入排序,4/19/2019,一、直接插入排序,利用顺序查找实现“在R1i-1中查找Ri的插入位置”的插入排序。,排序过程： 整个排序过程为i-1趟插入，即先将序列中第1个记录看成是一个有序子序列，然后从第2个记录开始，逐个进行插入，直至整个序列有序。,4/19/2019,算法实现的要点：,1.从Ri-1起向前进行顺序查找,监视哨设置在R0; R0 = Ri; / 设置“哨兵” for (j=i-1; R0.keyRj.key; -j); / 从后往前找 return j+1; / 返回Ri的插入位置为j+1,2.对于在查找过程中找到的那些关键字不小于Ri.key的记录，可以在查找的同时实现向后移动； for (j=i-1; R0.keyRj.key; -j); Rj+1 = Rj,3. i = 2，3，, n, 实现整个序列的排序。,for (i=2; i=2; +i); if(Ri.keyRi-1.key) 将Ri插入到= R1i-1中 ,4/19/2019,void InsertionSort ( Elem R , int n) / 对记录序列R1n作直接插入排序。 for ( i=2; i=n; +i ) R0 = Ri; / 复制为监视哨 for ( j=i-1; R0.key Rj.key; -j ) Rj+1 = Rj; / 记录后移 Rj+1 = R0; / 插入到正确位置 / InsertSort,算法描述：,4/19/2019,例,49 38 65 97 76 13 27,i=2 38 (38 49) 65 97 76 13 27,i=3 65 (38 49 65) 97 76 13 27,i=4 97 (38 49 65 97) 76 13 27,i=5 76 (38 49 65 76 97) 13 27,i=6 13 (13 38 49 65 76 97) 27,i=1 ( ),i=7 (13 38 49 65 76 97) 27,27,97,76,65,49,38,27,4/19/2019,（1）“比较”序列中两个关键字的大小；,时间分析：,实现排序的基本操作有两个：,（2）“移动”记录。,4/19/2019,最好的情况： 若待排序记录按关键字从小到大排列(正序),关键字“比较”次数：,最坏的情况： 若待排序记录按关键字从大到小排列(逆序),对于直接插入排序：,记录“移动”次数：,0,记录“移动”次数：,关键字“比较”次数：,4/19/2019,T(n)=O(n),若待排序记录是随机的，取平均值,关键字“比较”次数：,记录“移动”次数：,空间复杂度：,时间复杂度：,S(n)=O(1),4/19/2019,因为R1i-1是一个按关键字有序的有序序列，则可以利用折半查找实现“在R1i-1中查找Ri的插入位置”，如此实现的插入排序为折半插入排序。,二、折半插入排序,排序过程： 用折半查找方法确定插入位置的排序,4/19/2019,例,i=1 (30) 13 70 85 39 42 6 20,i=2 13 (13 30) 70 85 39 42 6 20,i=7 6 (6 13 30 39 42 70 85 ) 20,.,i=8 20 (6 13 20 30 39 42 70 85 ),4/19/2019,void BiInsertionSort (Elem R ， int n) / 对记录序列R1n作折半插入排序。 for ( i=2; i=high+1; -j ) Rj+1 = Rj; / 记录后移 Rhigh+1 = R0; / 插入 / BInsertSort,4/19/2019,算法评价 时间复杂度：T(n)=O(n) 空间复杂度：S(n)=O(1),折半插入排序比直接插入排序明显地减少了关键字间的“比较”次数，但记录“移动”的次数不变。,4/19/2019,三、希尔排序(缩小增量法),基本思想：对待排记录系列，先作“宏观”调整，再作“微观”调整。,所谓“宏观”调整，指的是“跳跃式”的插入排序。,4/19/2019,其中d为增量，它的值在排序过程中从大到小逐渐缩小，直至最后一趟排序减为1。,具体做法为：,将记录系列分成若干个子系列，分别对每个子系列作插入排序。,R1, R1+d, R1+2d, ,R1+kd,R2, R2d, R3d, , R(k+1)d,R2, R2+d, R2+2d, ,R2+kd,4/19/2019,4/19/2019,Ch8_3.c,49,13,38,27,27,4,55,38,65,48,97,55,76,4,4/19/2019,算法描述：,void ShellInsert(SqList / 插入 ,4/19/2019,void ShellSort(SqList ,4/19/2019,希尔排序特点,子序列的构成不是简单的“逐段分割”，而是将相隔某个增量的记录组成一个子序列,希尔排序可提高排序速度，因为,分组后n值减小，n更小，而T(n)=O(n),所以T(n)从总体上看是减小了,关键字较小的记录跳跃式前移，在进行最后一趟增量为1的插入排序时，序列已基本有序,增量序列取法,无除1以外的公因子,最后一个增量值必须为1,4/19/2019,一、起泡排序,二、一趟快速排序,三、快速排序,四、快速排序的时间分析,10.3 交换排序,4/19/2019,假设在排序过程中，记录序列R1n的状态为：,无序序列R1n-i+1,有序序列 Rn-i+2n,n-i+1,比较相邻记录，将无序序列中关键字最大的记录“交换”到Rn-i+1的位置上,第i趟起泡插入排序,无序序列R1n-i,有序序列 Rn-i+1n,一、起泡排序,4/19/2019,例,38,49,76,97,13,97,27,97,30,97,13,76,76,76,27,30,13,65,27,65,30,65,13,13,49,49,30,49,27,38,27,38,30,38,4/19/2019,void bubble_sort(Elem R,int n) / 将R中整数序列重新排列成自小至大有序的整数序列(起泡排序) int i=n, j; while(i1) lastexchangeIndex=1; for(j=1; jAj+1) Swap(Aj,Aj+1); lastexchangeIndex=j; /if i=lastexchangeIndex; /while /bubble_sort,起泡排序的结束条件为：最后一趟没有进行“交换”。,4/19/2019,算法评价 时间复杂度 最好情况（正序） 只需进行一趟起泡 比较次数：n-1 移动次数：0 最坏情况（逆序） 需进行n-1趟起泡 比较次数：,移动次数：,空间复杂度：S(n)=O(1),T(n)=O(n),4/19/2019,目标：找一个记录，以它的关键字作为“枢轴”，凡其关键字小于枢轴的记录均移动至该记录之前，反之，凡关键字大于枢轴的记录均移动至该记录之后。致使一趟排序之后，记录的无序序列Rst将分割成两部分：Rsi-1和Ri+1t,且 Rj.key Ri.key Rj.key (sji-1) 枢轴 (i+1jt),二、一趟快速排序,4/19/2019,例如:关键字序列,52, 49, 80, 36, 14, 58, 61, 97, 23, 75,调整为: 23, 49, 14, 36, (52) 58, 61, 97, 80, 75,其中(52)为枢轴，在调整过程中，需设立两个指针:low和high，它们的初值分别为:s和t, 之后逐渐减小high，增加low，并保证Rhigh.key52，而Rlow.key52,否则进行记录的“交换”。,4/19/2019,完成一趟排序： ( 27 38 13) 49 (76 97 65 50),49,27,49,65,13,49,49,97,4/19/2019,int Partition(SqList / 返回枢轴所在位置 ,算法描述,4/19/2019,在对无序序列中记录进行了一次分割之后，分别对分割所得两个子序列进行快速排序，依次类推，直至每个子序列中只含一个记录为止。,三、快速排序,4/19/2019,完成一趟排序： ( 27 38 13) 49 (76 97 65 50),分别进行快速排序： ( 13) 27 (38) 49 (50 65) 76 (97),快速排序结束： 13 27 38 49 50 65 76 97,49,27,49,65,13,49,49,97,4/19/2019,快速排序的算法描述如下:,void QSort (Elem R, int low, int high) / 对记录序列Rlowhigh进行快速排序 if (low high-1) / 长度大于1 pivotloc = Partition(L, low, high); / 将L.rlowhigh一分为二 QSort(L, low, pivotloc-1); / 对低子表递归排序，pivotloc是枢轴位置 QSort(L, pivotloc+1, high); / 对高子表递归排序 / QSort,4/19/2019,void QuickSort(Elem R, int n) / 对记录序列进行快速排序 QSort(R, 1, n); / QuickSort,4/19/2019,时间复杂度 最好情况（每次总是选到中间值作枢轴）T(n)=O(nlog2n) 最坏情况（每次总是选到最小或最大元素作枢轴）T(n)=O(n),空间复杂度：需栈空间以实现递归 最坏情况：S(n)=O(n) 一般情况：S(n)=O(log2n),T(n)=O(n),四、快速排序的时间分析,4/19/2019,一、简单选择排序,二、堆排序,10.4 选择排序,4/19/2019,一、简单选择排序,假设排序过程中，待排记录序列的状态为：,无序序列 Rin,有序序列R1i-1,从中选出关键字最小的记录加入有序序列。,第i趟简单选择排序是,有序序列R1i,无序序列 Ri+1n,有序序列中所有记录的关键字均小于无序序列中记录的关键字,4/19/2019,例,初始： 49 38 65 97 76 13 27 ,i=1,13,49,一趟： 13 38 65 97 76 49 27 ,i=2,27,38,六趟： 13 27 38 49 65 76 97 ,排序结束： 13 27 38 49 65 76 97,4/19/2019,void SelectSort(SqList ,算法描述,4/19/2019,算法评价 时间复杂度 记录移动次数 最好情况：0 最坏情况：3(n-1) 比较次数：,空间复杂度：S(n)=O(1),T(n)=O(n),4/19/2019,二、堆排序,堆排序的特点是，在以后各趟的“选择”中利用在第一趟选择中已经得到的关键字比较的结果。,堆的定义：,堆是满足下列性质的数列r1, r2, ，rn：,或,ri,r2i,R2i+1,4/19/2019,若将此数列看成是一棵完全二叉树，则堆或是空树或是满足下列特性的完全二叉树：其左、右子树分别是堆，并且当左/右子树不空时，根结点的值小于(或大于)左/右子树根结点的值。,ri,r2i,R2i+1,4/19/2019,例 （96，83，27，38，11，9）,例 （13，38，27，50，76，65，49，97）,可将堆序列看成完全二叉树，则堆顶元素（完全二叉树的根）必为序列中n个元素的最大值或最小值,分别称作大顶堆或小顶堆。,4/19/2019,先建一个“大顶堆”，即先选得一个关键字为最大的记录，然后与序列中最后一个记录交换，之后继续对序列中前n-1记录进行“筛选”，重新将它调整为一个“大顶堆”，再将堆顶记录和第n-1个记录交换，如此反复直至排序结束。,堆排序即是利用堆的特性对记录序列进行排序的一种排序方法。具体作法是：,4/19/2019,例如：,40，55，49，73，12，27，98，81，64，36,98，81，49，73，36，27，40，55，64，12,12，81，49，73，36，27，40，55，64，98,81，73，49，64，36，27，40，55，12，98,建大顶堆,交换98和12,筛选,4/19/2019,所谓“筛选”指的是，对一棵左/右子树均为堆的完全二叉树，“调整”根结点使整个二叉树为堆。,方法：输出堆顶元素之后，以堆中最后一个元素替代之；然后将根结点值与左、右子树的根结点值进行比较，并与其中大（小）者进行交换；重复上述操作，直至叶子结点，将得到新的堆，称这个从堆顶至叶子的调整过程为“筛选”,4/19/2019,（40，55，49，73，12，27，98，81，64，36，）,4/19/2019,（40，55，49，73，12，27，98，81，64，36）,（98，81，49，73，36，27，40，55，64，12）,4/19/2019,例 含8个元素的无序序列（49，38，65，97，76，13，27，50）,4/19/2019,例,4/19/2019,4/19/2019,4/19/2019,void HeapAdjust(HeapType / 插入 ,算法描述,4/19/2019,void HeapSort(HeapType / 将H.r1i-1重新调整为大顶堆 ,算法描述,4/19/2019,算法评价 时间复杂度：最坏情况下T(n)=O(nlogn) 空间复杂度：S(n)=O(1),4/19/2019,归并排序的基本思想是：,将两个或两个以上的有序子序列“归并”为一个有序序列。,10.5 归并排序,4/19/2019,在内部排序中，通常采用的是2-路归并排序。即：将两个位置相邻的有序子序列,有序子序列R1m,有序子序列Rm+1n,有 序 序 列 R1n,归并为一个有序序列。,4/19/2019,void Merge (Elem SR, Elem TR, int i, int m, int n) / 将有序的SRim和SRm+1n归并为 / 有序的TRin for (j=m+1, k=i; i=m / 将剩余的SRjn复制到TR / Merge,“归并”算法描述如下：,4/19/2019,例,初始关键字： 49 38 65 97 76 13 27,一趟归并后： 38 49 65 97 13 76 27,二趟归并后： 38 49 65 97 13 27 76,三趟归并后： 13 27 38 49 65 76 97,4/19/2019,算法评价 时间复杂度：T(n)=O(nlog2n) 空间复杂度：S(n)=O(n),Ch8_9.c,4/19/2019,归并排序的算法可以有两种形式：,递归的和递推的，它是由两种不同的程序设计思想得出的,递归形式的归并排序是一种自顶向下的分析方法,4/19/2019,如果记录无序序列Rst的两部分Rs(s+t)/2和R(s+t)/2+1t分别按关键字有序，则利用上述归并算法很容易将它们归并成整个记录序列是一个有序序列，由此，应该先分别对这两部分进行2-路归并排序。,归并排序的算法,4/19/2019,例,初始关键字： 49 38 65 97 76 13 27,38 49 65 97 13 76 27,38 49 65 97 13 27 76,13 27 38 49 65 76 97,49 38 65 97 76 13 27 ,49 38 65 97 76 13 27 ,4/19/2019,void Msort ( Elem SR, Elem TR1, int s, int t ) / 将SRst进行2-路归并排序为TR1st。 if (s=t) TR1s = SRs; else m = (s+t)/2; / 将SRst平分为SRsm和SRm+1t Msort (SR, TR2, s, m); / 递归地将SRsm归并为有序的TR2sm Msort (SR, TR2, m+1, t); /递归地SRm+1t归并为有序的TR2m+1t Merge (TR2, TR1, s, m, t); / 将TR2sm和TR2m+1t归并到TR1st / MSort,算法描述,4/19/2019,void MergeSort (Elem R) / 对记录序列R1n作2-路归并排序。 MSort(R, R, 1, n); / MergeSort,4/19/2019,算法评价 时间复杂度：T(n)=O(nlogn) 空间复杂度：S(n)=O(n),Ch8_9.c,4/19/2019,多关键字排序 定义：,例 对52张扑克牌按以下次序排序： 23A23A 23A23A 两个关键字：花色（ ） 面值（23A） 并且“花色”地位高于“面值”,多关键字排序方法 最高位优先法（MSD)：先对最高位关键字k1（如花色）排序，将序列分成若干子序列，每个子序列有相同的k1值；然后让每个子序列对次关键字k2（如面值）排序，又分成若干更小的子序列；依次重复，直至将每个子序列对最低位关键字kd排序；最后将所有子序列依次连接在一起成为一个有序序列,10.6 基数排序,4/19/2019,最低位优先法(LSD)：从最低位关键字kd起进行排序，然后再对高一位的关键字排序，依次重复，直至对最高位关键字k1排序后，便成为一个有序序列 MSD与LSD不同特点 按MSD排序，必须将序列逐层分割成若干子序列，然后对各子序列分别排序 按LSD排序，不必分成子序列，对每个关键字都是整个序列参加排序；并且可不通过关键字比较，而通过若干次分配与收集实现排序 链式基数排序 基数排序：借助“分配”和“收集”对单逻辑关键字进行排序的一种方法 链式基数排序：用链表作存储结构的基数排序,4/19/2019,链式基数排序步骤 设置10个队列，fi和ei分别为第i个队列的头指针和尾指针 第一趟分配对最低位关键字（个位）进行，改变记录的指针值，将链表中记录分配至10个链队列中，每个队列记录的关键字的个位相同 第一趟收集是改变所有非空队列的队尾记录的指针域，令其指向下一个非空队列的队头记录，重新将10个队列链成一个链表 重复上述两步，进行第二趟、第三趟分配和收集，分别对十位、百位进行，最后得到一个有序序列,4/19/2019,例,4/19/2019,4/19/2019,4/19/2019,算法评价 时间复杂度： 分配：T(n)=O(n) 收集：T(n)=O(rd) T(n)=O(d(n+rd) 其中：n记录数 d关键字数 rd关键字取值范围 空间复杂度：S(n)=2rd个队列指针+n个指针域空间,4/19/2019,f0=0 e0=0 f1=0 e1=0 f2=0 e2=0 f3=0 e3=0 f4=0 e4=0 f5=0 e5=0 f6=0 e6=0 f7=0 e7=0 f8=0 e8=0 f9=0 e9=0,1,1,2,