南京邮电大学数据结构A第10章

数据结构A·第10章第10章内排序内容提要1、内排序的基本概念；2、简单排序算法；3、快速排序算法；4、两路合并排序;5、堆排序。10.1内排序的基本概念设有n个数据元素的序列(R0,R1,…,Rn-1)，Ki是Ri的关键字。所谓排序，就是找(0,1,…,n-1)的一种排列p(0),p(1),…,p(n-1)，使得序列按Kp(0)Kp(1)…Kp(n-1)（非递减）或Kp(0)Kp(1)…Kp(n-1)（非递增）的次序排列为：(Rp(0),Rp(1),…,Rp(n-1))10.1内排序的基本概念序列中两个元素Ri和Rj(ij),且Ki=Kj，排序后，Ri仍然排在Rj之前，则称所用的排序算法是稳定的。反之，称该排序算法是不稳定的。3,1,3=1,3,33,1,3=1,3,3如果待排序元素总数相对于内存而言较小，整个排序过程可以在内存中进行，则称之为内部排序；反之，如果待排序元素总数较多，不能全部放入内存，排序过程中需访问外存，则称之为外部排序。10.2简单排序算法本节介绍三种简单的排序算法：简单选择排序冒泡排序直接插入排序它们的时间复杂度在最坏情况下均为O(n2)。虽然这些算法对数据量较大的情况不大实用,但仍然可从中体验排序的基本方法课堂提要第10章内排序10.1排序的基本概念10.2简单排序算法10.2.1简单选择排序10.2.2直接插入排序10.2.3冒泡排序10.3快速排序10.42路合并排序第10章内排序排序要求掌握(比较各种排序)：(a)算法(手工排序过程，即写出各趟排序结果；趟数不要多或少)(b)稳定性；3,1,3=1,3,3(c)时间复杂度(最好、最坏和平均)、比较次数和移动元素次数；(d)适用场合；(e)一趟排序结束后就能确定某个元素最终位置的算法有哪些？(最后一趟排序前仍不能确定某个元素最终位置的算法有哪些？)(f)给出排序结果，判断是何种排序。10.2简单排序算法10.2.1简单选择排序基本思想：•第1趟：在初始序列(A[0]A[n-1])中找一个最小值，与序列中第一个元素A[0]交换，这样子序列(A[0])有序；•……•第i趟：在子序列(A[i-1]A[n-1])中找最小值元素与子序列中的第一个元素A[i-1]交换;•经过n-1趟排序后使得初始序列有序。10.2简单排序算法10.2.1简单选择排序0123456初始序列：（48366872124802）第1趟：（02）（366872124848）第2趟：（0212)（6872364848）第3趟：（021236)(72684848）第4趟：（02123648)(687248）第5趟：（0212364848)(7268）第6趟：（021236484868)(72）排序结果：（02123648486872）图10-1简单选择排序示意图10.2简单排序算法10.2.1简单选择排序程序10-1简单选择排序templateclassTvoidSelectSort(TA[],intn){intsmall;for(inti=0;in-1;i++){//n-1趟small=i;for(intj=i+1;jn;j++)if(A[j]A[small])small=j;Swap(A[i],A[small]);}//endfor}//函数Swap(T&a,T&b)交换两个元素时间复杂度按比较次数衡量为O(n2)。10.2简单排序算法10.2.1简单选择排序48366872124802ismall=ji指向无序区的开始位置j为扫描“指针”;small变量用来记录无序区中最小元素的索引值;01460248整个无序序列的最小值02被放到i位置后,第一遍扫描结束,进入第二遍扫描;012345610.2简单排序算法10.2.1简单选择排序该算法必须进行n-1趟，每趟进行n-i-1次比较，这样总的比较次数为时间复杂度按比较次数衡量为O(n2)。另外，还需移动元素3(n-1)次或交换元素（n-1）次。简单选择排序是不稳定的排序方法。关于稳定性问题：3,1,3进行简单选择排序：1,3,31,3,3(似乎是稳定的)3,3,1进行简单选择排序：1,3,31,3,3202)1()1(ninnin10.2简单排序算法10.2.2直接插入排序基本思想：将序列中第1个元素作为一个有序序列，然后将剩下的n-1个元素按关键字大小依次插入该有序序列，经过n-1趟排序后即成为有序序列。0123456初始序列：（48）366872124802第1趟：（3648）6872124802第2趟：（364868）72124802第3趟：（36486872）124802第4趟：（1236486872）4802第5趟：（123648486872）02第6趟：（02123648486872）排序结果：（02123648486872）10.2简单排序算法10.2.2直接插入排序程序10-2直接插入排序templateclassTvoidInsertSort(TA[],intn){for(inti=1;in;i++){intj=i;Ttemp=A[i];while(j0&&tempA[j-1]){A[j]=A[j-1];j--;}A[j]=temp;}}10.2简单排序算法10.2.2直接插入排序123668724802ii之前是有序区;排序开始的时候i=1;jj是扫描“指针”;向前寻找插入的位置；temp=36temp中存放新的欲处理元素；68721236124810.2简单排序算法10.2.2直接插入排序在最坏情况下需要比较次。次，移动元素111(2)(4)(1)2niinn112)1(ninni因此最坏情况时间复杂度为O(n2)，它是稳定的排序方法。10.2简单排序算法10.2.3冒泡排序基本思想：第1趟在序列(A[0]A[n-1])中从前往后进行两个相邻元素的比较，若后者小，则交换，比较n-1次。第1趟排序结束，最大元素被交换到A[n-1]中(即沉底)。下一趟排序只需在子序列(A[0]A[n-2])中进行。如果在某一趟排序中未交换元素，说明子序列已经有序，则不再进行下一趟排序。0123456初始序列：（48366872124802）第1趟：（364868124802）72第2趟：（3648124802）687210.2简单排序算法10.2.3冒泡排序（48366872124802）（36486872124802）（36486872124802）（36486872124802）（36486812724802）（36486812487202）（364868124802)72（364868124802）72（3648124802）6872（36124802）486872（123602）48486872（1202）3648486872（02）123648486872第一趟:（第1趟）（第2趟）（第3趟）（第4趟）（第5趟）（第6趟）10.2简单排序算法10.2.3冒泡排序程序10-3冒泡排序templateclassTvoidBubbleSort(TA[],intn){inti,j,last;i=n-1;while(i0){last=0;for(j=0;ji;j++)if(A[j+1]A[j]){Swap(A[j],A[j+1]);last=j;}i=last;}//endwhile}10.2简单排序算法10.2.3冒泡排序68361272480248j扫描“指针”；A[j+1]A[j]?Yes(直接后继较小),交换之;No(直接后继较大),无须交换;完成一遍扫描!10.2简单排序算法10.2.3冒泡排序冒泡排序最好情况(已有序)下只需进行一趟排序，n-1次比较，因此最好情况下的时间复杂度是O(n)。最坏进行n-1趟，第i趟比较(n-i)次，移动元素3(n-i)次，这样比较次数为：移动元素次数为3n(n-1)/2。最坏情况下的时间复杂度为O(n2)。冒泡排序是稳定的排序方法。)1(21)(11nninni10.3快速排序基本思想：对任意给定的序列中元素Rs(关键字为Ks)，经过一趟排序后，将原序列分割成两个子序列，其中，前一个子序列中的所有元素的关键字均小于等于Ks,后一个子序列中元素的关键字均大于等于Ks。称元素Rs为分割元素。以后只需对2个子序列分别进行快速排序，直到子序列为空或只有一个元素时得到有序序列。（48，36，68，72，12，48，02）（12，36，02，48）48（72，68）10.3快速排序48687236481202leftrightij和right“指针”指出了待排序的元素序列；扫描“指针”，向右扫描寻找=A[left]的元素;扫描“指针”，向左扫描寻找=A[left]的元素;36并不大于等于A[left],所以继续扫描;找到大于A[left]的元素(68),扫描暂停;准备和A[j]交换;找到小于A[left]的元素(02),准备和A[i]交换;∞交换以后,只要i和j尚未相遇,就继续各自的扫描以及交换操作;其目的是把较A[left]小的元素放到左边,较A[left]大的元素放到右边;此时,i和j已经“相遇”过,扫描结束,下面要把A[left]和A[j]交换,实现了各元素按“左边小右边大”的原则分布在A[left]两侧;接下来会分别把A[left]元素两侧的序列作为排序对象递归整个算法过程;(过程略)10.3快速排序01234567j算法要求A[n]=+∞，防止i超界。10.3快速排序10.3快速排序程序10-4快速排序templateclassTvoidQSort(TA[],intleft,intright){inti,j;if(leftright){i=left;j=right+1;do{doi++;while(A[i]A[left]);doj--;while(A[j]A[left]);if(ij)Swap(A[i],A[j]);}while(ij);Swap(A[left],A[j]);QSort(A,left,j-1);QSort(A,j+1,right);}//endif}10.3快速排序templateclassTvoidQuickSort(TA[],intn){A[n]=maxnum；QSort(A,0,n-1);}从上述快速排序算法中可以看出，经过每一趟排序后，若被分割成两个大小相近的子序列时，快速排序的效率最好，时间复杂度为O(nlog2n)；反之，若每次分割的两个子序列中有一个为空，即初始序列有序(顺序或逆序)，则效率最低，时间复杂度为O(n2)。快速排序是不稳定的排序方法。10.3快速排序为避免发生最坏情况，选择分割元素时可作三种处理：(1)将A[(left+right)/2]作为分割元素,与A[left]交换；(2)选left到right间的随机整数k，将A[k]与A[left]交换；(3)取A[left]、A[(left+right)/2]和A[right]之中间值与A[left]交换。对于快速排序：(1)为提高快速排序的效率，将递归程序改为非递归的；(2)为减小栈空间，先对较小子序列排序，将较大子序列进栈；10.4两路合并排序基本思想：将有n个元素的序列看成是n个长度为1的有序子序列，然后两两合并子序列，得到n/2个长度为2或1的有序子序列；再两两合并，…，直到得到一个长度为n的有序序列时结束。310.4两路合并排序48366872124802size=1i1j1i2j2第一趟排序;36486872124802size=2i1i2第二趟排序;j1j2此时i1+sizen的条件已经不满足,第一趟扫描结束;此时的状态,适合展示排序的细节,请注意!Temp48366872124802size=4i1j1i2j2先按从小到大的顺序放到Temp数组中,然后再写回A[];第三趟排序;过程同前(略);每一趟size以2倍增加,当size=