[工学]chenz-DSA-PPT-Slides-ch

1、数据结构数据结构A 第第10章章 班 级 ：B080308-10任课教师 ：陈志老师上课地点和时间（1）教2410：星期2，下午第3大节（2）教2512：星期5，上午第1大节第第10章章 内排序内排序 排序是将一个数据元素的序列调整为按指定关键字排序是将一个数据元素的序列调整为按指定关键字值递增（或递减）次序排列的有序序列的过程。值递增（或递减）次序排列的有序序列的过程。第第10章章 内排序内排序第第10章章 内排序内排序 排序要求掌握排序要求掌握(比较各种排序比较各种排序)： (a)算法算法(手工排序过程，即写出各趟排序结果；手工排序过程，即写出各趟排序结果；趟数不要多或少趟数不要多或少)；

2、 (b)稳定性；稳定性；3,1,3= 1,3,3 (c)时间复杂度时间复杂度(最好、最坏和平均最好、最坏和平均)、比较次数和移动元素次数比较次数和移动元素次数； (d)适用场合；适用场合； (e)一趟排序结束后就能确定某个元素最终位置的算法有哪些？一趟排序结束后就能确定某个元素最终位置的算法有哪些？ (最后最后一趟排序前仍不能确定某个元素最终位置的算法有哪些？一趟排序前仍不能确定某个元素最终位置的算法有哪些？) (f)给出排序结果，判断是何种排序。给出排序结果，判断是何种排序。10.1 内排序的基本概念内排序的基本概念 设有设有n个数据元素的序列个数据元素的序列(R0,R1,Rn-1)，Ki

3、是是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 (i1,3,3 反之，反之，称该排序算法是称该排序算法是不稳定的不稳定的。3,1,3=1,3,310.1 内排序的基本概念内排序的基本概念序列中两个元素

4、序列中两个元素Ri和和 Rj (i1,3,3 反之，称该排序算法是不稳定的。反之，称该排序算法是不稳定的。3,1,3=1,3,3如果待排序元素总数相对于内存而言较小，整个排序过程如果待排序元素总数相对于内存而言较小，整个排序过程可以在可以在内存内存中进行，则称之为中进行，则称之为内部排序内部排序；如果待排序元素总数较多，不能全部放入内存，排序过程如果待排序元素总数较多，不能全部放入内存，排序过程中中需访问外存需访问外存，则称之为，则称之为外部排序外部排序。10.1 内排序的基本概念内排序的基本概念序列中两个元素序列中两个元素Ri和和 Rj (i1,3,3 反之，称该排序算法是不稳定的。反之，称

5、该排序算法是不稳定的。3,1,3=1,3,3如果待排序元素总数相对于内存而言较小，整个排序过程如果待排序元素总数相对于内存而言较小，整个排序过程可以在内存中进行，则称之为内部排序；可以在内存中进行，则称之为内部排序；如果待排序元素总数较多，不能全部放入内存，排序过程如果待排序元素总数较多，不能全部放入内存，排序过程中需访问外存，则称之为外部排序。中需访问外存，则称之为外部排序。本章讨论内部排序本章讨论内部排序,采用顺序存储方式采用顺序存储方式&用一个一维数组用一个一维数组An+1 (n为序列中元素个数为序列中元素个数)存储序列中存储序列中各元素的关键字，忽略元素的其它部分，把精力集中在

6、排序各元素的关键字，忽略元素的其它部分，把精力集中在排序算法上。算法上。10.2 简单排序算法简单排序算法本节介绍三种简单的排序算法：本节介绍三种简单的排序算法：l 简单选择排序简单选择排序l 冒泡排序冒泡排序l 直接插入排序直接插入排序 它们的时间复杂度在最坏情它们的时间复杂度在最坏情况下均为况下均为O(n2)。虽然这些算法对数据量较大的情况虽然这些算法对数据量较大的情况不大实用不大实用, , 但仍然可从中体验排序但仍然可从中体验排序的基本方法的基本方法第第10章章 内排序内排序10.1 排序的基本概念排序的基本概念 10.2 简单排序算法简单排序算法 10.2.1 简单选择排序简单选择排序

7、 10.2.2 直接插入排序直接插入排序 10.2.3 冒泡排序冒泡排序10.3 快速排序快速排序10.4 2路合并排序路合并排序10.2 简单排序算法简单排序算法10.2.1 简单选择排序基本思想基本思想第第1趟在初始序列趟在初始序列(A0 An-1)中找一个最小值，与序中找一个最小值，与序列中第一个元素列中第一个元素A0交换，这样子序列交换，这样子序列(A0)有序。有序。下一趟排序在子序列下一趟排序在子序列(A1 An-1)中进行。中进行。第第i趟排序在子序列趟排序在子序列(Ai-1 An-1)中找最小值元素与子中找最小值元素与子序列中的第一个元素序列中的第一个元素Ai-1交换。经过交换。

8、经过n-1趟排序后使得趟排序后使得初始序列有序。初始序列有序。10.2 简单排序算法简单排序算法10.2.1 简单选择排序 0 1 2 3 4 5 6 0 1 2 3 4 5 6初始序列：初始序列： （4848 36 68 72 12 36 68 72 12 4848 0202）第第1 1趟：趟： （0202）（）（3636 68 72 68 72 12 12 4848 48 48）第第2 2趟：趟： （02 12) 02 12) （6868 72 72 3636 4848 48 48）第第3 3趟：趟： （02 12 36) (02 12 36) (7272 68 68 4848 48 48

9、）第第4 4趟：趟： （02 12 36 02 12 36 4848) () (6868 72 72 4848）第第5 5趟：趟： （02 12 36 02 12 36 4848 48 48) () (7272 6868 ）第第6 6趟：趟： （02 12 36 02 12 36 4848 48 48 68) (72 68) (72）排序结果：排序结果： （02 12 36 02 12 36 4848 48 48 68 72 68 72）图图10-1 10-1 简单选择排序示意图简单选择排序示意图10.2 简单排序算法简单排序算法10.2.1 简单选择排序程序程序 10-1 简单选择排序简单选

10、择排序 template void SelectSort(T A, int n) int small; for (int i=0; in-1; i+ ) / n-1趟趟 small=i; for (int j=i+1; jn; j+) if (AjAsmall) small=j; Swap(Ai,Asmall); /endfor /函数函数Swap(T &a, T &b)交换两个元素交换两个元素时间复杂度按比较次数衡量为时间复杂度按比较次数衡量为O(n2)。10.2 简单排序算法简单排序算法10.2.1 简单选择排序48 36 68 72 12 48 02ismall=ji i

11、指向无序区的指向无序区的开始位置开始位置j j为扫描为扫描“指针指针”; ;smallsmall变量用来记录无序变量用来记录无序区中最小元素的索引值区中最小元素的索引值; ;0 14 60248整个无序序列的最小整个无序序列的最小值值0202被放到被放到i i位置后位置后, ,第一遍扫描结束第一遍扫描结束, ,进进入第二遍扫描入第二遍扫描; ;0 1 2 3 4 5 60 1 2 3 4 5 610.2 简单排序算法简单排序算法10.2.1 简单选择排序 该算法必须进行该算法必须进行n-1趟，每趟进行趟，每趟进行n-i-1次比较，这样次比较，这样总的比较次数为总的比较次数为 时间复杂度按比较次

12、数衡量为时间复杂度按比较次数衡量为O(n2)。另外，还需移。另外，还需移动元素动元素3(n-1)次或交换元素（次或交换元素（n-1）次。简单选择排序是不）次。简单选择排序是不稳定的排序方法。稳定的排序方法。关于稳定性问题：关于稳定性问题： 3,1,3进行简单选择排序：进行简单选择排序： 1,3,3 1,3,3 (似乎是稳定的似乎是稳定的) 3,3,1进行简单选择排序：进行简单选择排序： 1,3,3 1,3,3 202)1()1(ninnin10.2 简单排序算法简单排序算法10.2.2 直接插入排序 基本思想：将序列中第基本思想：将序列中第1个元素作为一个有序序列，然个元素作为一个有序序列，然

13、后将剩下的后将剩下的n-1个元素按关键字大小依次插入该有序序列，个元素按关键字大小依次插入该有序序列，经过经过n-1趟排序后即成为有序序列。趟排序后即成为有序序列。 0 1 2 3 4 5 6 0 1 2 3 4 5 6初始序列：初始序列： （4848） 3636 68 72 12 68 72 12 4848 02 02第第1 1趟：趟： （36 4836 48） 6868 72 12 72 12 4848 02 02第第2 2趟：趟： （36 48 6836 48 68） 7272 12 12 4848 02 02第第3 3趟：趟： （36 48 68 7236 48 68 72） 1212

14、 4848 02 02第第4 4趟：趟： （12 36 48 68 7212 36 48 68 72） 4848 02 02第第5 5趟：趟： （12 36 48 12 36 48 4848 68 72 68 72） 0202第第6 6趟：趟： （02 12 36 48 02 12 36 48 4848 68 72 68 72）排序结果：排序结果： （02 12 36 02 12 36 4848 48 48 68 72 68 72）10.2 简单排序算法简单排序算法10.2.2 直接插入排序程序程序 10-2 直接插入排序直接插入排序template void InsertSort(T A,

15、int n) for(int i=1; i0 & tempAj-1) Aj=Aj-1; j-; Aj=temp; 10.2 简单排序算法简单排序算法10.2.2 直接插入排序1236 68 7248 02i ii i之前是有序区之前是有序区; ;排序开排序开始的时候始的时候i=1;i=1;jj j是扫描是扫描 “ “指针指针”; ;向前寻找插入的位置向前寻找插入的位置；temp =temp = 36 36 temptemp中存放新的欲处中存放新的欲处理元素；理元素；686872721212363612124810.2 简单排序算法简单排序算法10.2.2 直接插入排序在最坏情况下需要比

16、较在最坏情况下需要比较次。次。次，移动元素次，移动元素111(2)(4)(1)2niinn 112)1(ninni因此最坏情况时间复杂度为因此最坏情况时间复杂度为 O(n2)，它是稳定的排序方法。，它是稳定的排序方法。10.2 简单排序算法简单排序算法10.2.2 直接插入排序template void InsertSort(T A, int n) for ( int i=1; i0 & temp Aj-1) Aj=Aj-1; j-; Aj=temp;关于稳定性问题：关于稳定性问题： 2,3,1,3： 2,3,1,3 1,2,3,3 1,2,3,3 为何变成了不稳定的？为何变成了不稳定

17、的？=10.2 简单排序算法简单排序算法10.2.3 冒泡排序 基本思想：第基本思想：第1趟在序列趟在序列(A0 An-1)中从前往后进中从前往后进行两个相邻元素的比较，若后者小，则交换，比较行两个相邻元素的比较，若后者小，则交换，比较n-1次。次。第第1趟排序结束，最大元素被交换到趟排序结束，最大元素被交换到An-1中中(即沉底即沉底)。 下一趟排序只需在子序列下一趟排序只需在子序列(A0 An-2)中进行。如果中进行。如果在某一趟排序中未交换元素，说明子序列已经有序，则不在某一趟排序中未交换元素，说明子序列已经有序，则不再进行下一趟排序。再进行下一趟排序。 0 1 2 3 4 5 6 0

18、1 2 3 4 5 6初始序列：（初始序列：（48 36 68 72 12 48 36 68 72 12 4848 02 02）第第1 1趟：趟： （36 48 68 12 36 48 68 12 4848 02 02）7272第第2 2趟：趟： （36 48 12 36 48 12 4848 02 02）6868 72 7210.2 简单排序算法简单排序算法10.2.3 冒泡排序（ 68 72 12 68 72 12 4848 02 02）（36 36 72 12 72 12 4848 02 02）（36 48 36 48 12 12 4848 02 02）（36 48 68 36 48 6

19、8 4848 02 02）（36 48 68 12 36 48 68 12 02 02）（36 48 68 12 36 48 68 12 4848 ）（36 48 68 12 36 48 68 12 4848 02) 02) 7272（36 48 68 12 36 48 68 12 4848 02 02） 7272（36 48 12 36 48 12 4848 02 02）6868 72 72（36 12 48 0236 12 48 02）4848 68 72 68 72（12 36 0212 36 02）4848 4848 68 72 68 72（12 0212 02）3636 48 48

20、4848 68 72 68 72（0202）1212 36 48 36 48 4848 68 72 68 72第一趟第一趟:（第第1 1趟趟）（第第2 2趟趟）（第第3 3趟趟）（第第4 4趟趟）（第第5 5趟趟）（第第6 6趟趟）10.2 简单排序算法简单排序算法10.2.3 冒泡排序程序程序10-3 冒泡排序冒泡排序template void BubbleSort(T A, int n) int i,j,last; i=n-1; while ( i0 ) last=0; for(j=0; ji; j+) if (Aj+1Aj) Swap(Aj,Aj+1); last=j; i=last;

21、/endwhile10.2 简单排序算法简单排序算法10.2.3 冒泡排序68361272480248j扫描扫描“指针指针”；Aj+1= Aleft= Aleft 的的元素元素; ;扫描扫描“指针指针”，向左，向左扫描寻找扫描寻找 = Aleft= Aleft 的元素的元素; ;3636并不大于等并不大于等于于AleftAleft,所所以继续扫描以继续扫描; ;找到大于找到大于AleftAleft 的的元素元素(68),(68),扫描暂停扫描暂停; ;准备和准备和AjAj 交换交换; ;找到小于找到小于AleftAleft 的元素的元素(02), (02), 准准备和备和AiAi 交换交换;

22、;交换以后交换以后, ,只要只要 i i 和和 j j 尚未相遇尚未相遇, ,就就继续各自的扫描以及交换操作继续各自的扫描以及交换操作; ; 目的是把较目的是把较AleftAleft 小的元素放到左小的元素放到左边边, ,较较AleftAleft 大的元素放到右边大的元素放到右边; ;此时此时,i,i和和j j已经已经“相遇相遇”过过, ,扫描结束扫描结束, ,下面要把下面要把AleftAleft 和和AjAj 交换交换, ,实现了实现了各元素按各元素按“左边小右边大左边小右边大”的原则分的原则分布在布在AleftAleft 两侧两侧; ;接下来会分别把接下来会分别把AleftAleft 元素

23、两侧元素两侧的序列作为排序对的序列作为排序对象递归整个算法过象递归整个算法过程程10.3 快速排序快速排序0 1 2 3 4 5 6 70 1 2 3 4 5 6 7j j算法要求算法要求An=+，防止，防止i超界。超界。10.3 快速排序快速排序10.3 快速排序快速排序程序程序10-4 快速排序快速排序template void QSort(T A,int left,int right) int i,j; if ( leftright ) i=left; j=right+1; do do i+; while (AiAleft); if (ij) Swap(Ai,Aj); while (ij

24、); Swap(Aleft,Aj); QSort(A,left,j-1); QSort(A,j+1,right);/endif10.3 快速排序快速排序template void QuickSort(T A,int n) An=maxnum； QSort(A,0,n-1);从上述快速排序算法中可以看出从上述快速排序算法中可以看出:经过每一趟排序后，若被分割成两个经过每一趟排序后，若被分割成两个大小相近大小相近的子序列时的子序列时，快速排序的效率最好，时间复杂度为，快速排序的效率最好，时间复杂度为O(nlog2n)；反之，若每次分割的两个子序列中有一个为空，即初始序反之，若每次分割的两个子序列中

25、有一个为空，即初始序列有序列有序(顺序或逆序顺序或逆序)，则效率最低，时间复杂度为，则效率最低，时间复杂度为O(n2)。快速排序是快速排序是不稳定不稳定的排序方法。的排序方法。10.3 快速排序快速排序 为避免发生最坏情况，选择分割元素时可作三种处理：为避免发生最坏情况，选择分割元素时可作三种处理： (1)将将A(left+right)/2作为分割元素作为分割元素,与与Aleft交换；交换； (2)选选left到到right间的随机整数间的随机整数k，将，将Ak与与Aleft交换；交换； (3)取取Aleft、A(left+right)/2和和Aright之中间值与之中间值与Aleft交换。交

26、换。 提高快速排序的效率：提高快速排序的效率： (1) 将递归程序改为非递归将递归程序改为非递归 (2) 先对短的子序列排序，长的子序列后排序先对短的子序列排序，长的子序列后排序10.4 两路合并排序（两路合并排序（1945年）年）约翰约翰冯冯诺伊曼诺伊曼/wiki/Merge_sort10.4 两路合并排序两路合并排序基本思想基本思想：将有：将有n个元素的序列看成是个元素的序列看成是n个长度为个长度为1的有序的有序子序列，然后两两合并子序列，得到子序列，然后两两合并子序列，得到 n/2 个长度为个长度为2或或1的有序子序列；再两两合并，的有序子序列

27、；再两两合并，直到得到一个长度为，直到得到一个长度为n的有序序列时结束。的有序序列时结束。10.4 两路合并排序两路合并排序4848363668687272121248480202size=1size=1i1j1i2j2第一趟第一趟排序排序; ;3636484868687272121248480202size=2size=2i1i2第二趟第二趟排序排序; ;j1j2此时此时i1+sizeni1+size= n size = n 时排序结束时排序结束; ;10.4 两路合并排序两路合并排序将两个子序列将两个子序列 (Ai1, Ai1+1, Aj1) (Ai2, Ai2+1, Aj2)合并为一个子

28、序列，保存在数组合并为一个子序列，保存在数组Temp从从k开始的位置开始的位置(Tempk,Tempk+1,Tempj1-i1+j2-i2+1+k)。 i1 i1 j1 i2 j1 i2 j2 j2A A k kTempTempkkkk=(j1-i1+j2-i2+1+k)=(j1-i1+j2-i2+1+k)10.4 两路合并排序两路合并排序程序程序10-5 两路合并的两路合并的C+程序程序template void Merge(T A, int i1, int j1, int i2, int j2) T *Temp=new Tj2-i1+1; int i=i1, j=i2, k=0; whil

29、e (i=j1 & j=j2) if (Ai=Aj) Tempk+=Ai+; else Tempk+=Aj+; while (i=j1) Tempk+=Ai+; /剩余部分存入剩余部分存入temp while (j=j2) Tempk+=Aj+; for(i=0; ik; i+) Ai1+=Tempi; delete Temp; i1 i1 j1 i2 j1 i2 j2 j2A A10.4 两路合并排序两路合并排序template void MergeSort(T A, int n) int i1,j1,i2,j2 int size=1; while ( sizen ) i1=0; w

30、hile ( i1+sizen-1) j2=n-1; else j2=i2+size-1; Merge(A,i1,j1,i2,j2); i1=j2+1; size *=2; /子序列长度增加子序列长度增加2倍倍/endwhile i1 i1 j1 i2 j1 i2 j2 j2A Asizesizesizesizesizesize j1 i2 j1 i2 j2 j2n-1n-110.4 两路合并排序两路合并排序 该算法中该算法中size的取值不超过的取值不超过 log2n 个，即最多进行个，即最多进行 log2n 趟排序，每趟都要扫描趟排序，每趟都要扫描n个元素，因此两路合并个元素，因此两路合并

31、排序的时间复杂度是排序的时间复杂度是O(nlog2n)，但是它必须借助一个，但是它必须借助一个与原序列等大小的与原序列等大小的辅助数组辅助数组(O(n)方能实现。方能实现。 两路合并排序是一种两路合并排序是一种稳定稳定的排序方法。的排序方法。10.5 堆排序堆排序/wiki/Heapsort10.5 堆排序堆排序基本概念基本概念 堆排序是堆排序是“堆堆”数据结构在内排序中的应用。数据结构在内排序中的应用。所谓所谓堆堆，是指一棵包含，是指一棵包含 n 个结点的完全二叉树：个结点的完全二叉树：l该树中每个结点的关键字值该树中每个结点的关键字值“大于等于大

32、于等于”/“小于等小于等于于”其双亲结点的关键字值。其双亲结点的关键字值。l该树的该树的根根称为称为堆顶堆顶，它的关键字值是整棵树上，它的关键字值是整棵树上“最最小小”/“最大最大”的。的。堆顶元素关键字值最小的堆称为堆顶元素关键字值最小的堆称为最小堆最小堆。堆顶元素关键字值最大的堆称为堆顶元素关键字值最大的堆称为最大堆最大堆。10.5 堆排序堆排序基本思想基本思想将初始序列将初始序列构造构造成最大堆；成最大堆；第一趟排序，将堆顶元素第一趟排序，将堆顶元素A0和堆底元素和堆底元素An-1交换位置交换位置，调用，调用AdjustDown函数将函数将A0向下调整，使得剩余的前向下调整，使得剩余的前

33、n1个元素还是堆；个元素还是堆；第第i趟时，将趟时，将A0与与An-i交换，交换，A0向下调整，使得剩余向下调整，使得剩余的前的前n-i个元素还是堆；直到堆中只剩一个记录结束。个元素还是堆；直到堆中只剩一个记录结束。4848686836360202484812127272第一步第一步, ,也就是第一也就是第一趟排序趟排序, ,首先将初始首先将初始序列构造成堆序列构造成堆; ;r r构造堆的扫描构造堆的扫描“指针指针”; ; 初始时初始时,r=(n-2)/2;,r=(n-2)/2;对对r r所指的树做向下调整所指的树做向下调整操作操作, , 最后的结果是大最后的结果是大的元素放在树顶端的元素放在

34、树顶端; ;调整结束后调整结束后, r, r指针向指针向前移动前移动; ;此时堆构造完毕此时堆构造完毕, , 然后把堆顶然后把堆顶元素和堆底元素交换元素和堆底元素交换; ;堆底的堆底的元素变为最大的元素元素变为最大的元素; ;这时就这时就完成了第一趟排序完成了第一趟排序; ;第二趟排序和第一趟排序的过程相同第二趟排序和第一趟排序的过程相同, , 只不过只不过, , 第二趟排序过程没有第二趟排序过程没有 72 72 这个元素参与这个元素参与; ; 可可以想见以想见, , 经过多趟排序经过多趟排序( (过程略过程略) )后后, , 序列从上序列从上到下到下, , 从左到右从左到右, , 依次升序排

35、列依次升序排列; ; 10.5 堆排序堆排序10.5 堆排序堆排序初始序列初始序列: 48 36 68 72 12 : 48 36 68 72 12 4848 02 02构造的堆构造的堆: 72 48 68 36 12 : 72 48 68 36 12 4848 02 02第第1 1趟结果趟结果: 68 48 : 68 48 4848 36 12 02(72) 36 12 02(72)第第2 2趟结果趟结果: 48 36 : 48 36 4848 02 12 ( 02 12 (6868 72) 72)第第3 3趟结果趟结果: : 4848 36 12 02 (48 68 72) 36 12 02 (48 68 72