大连理工大学：《数据结构》课程教学课件（PPT讲稿）第八章 排序

第八章排序 ★排序定义一将一个数据元素（或记录)的任意 序列，重新排列成一个按关键字有序的序列叫~ ★排序分类 ?按待排序记录所在位置 ●内部排序：待排序记录存放在内存 ●外部排序：排序过程中需对外存进行访问的排序 必按排序依据原则 ●插入排序：直接插入排序、折半插入排序、希尔排序 ●交换排序：冒泡排序、快速排序 ●选择排序：简单选择排序、堆排序 ●归并排序：2-路归并排序 ●基数排序

第八章 排序 排序定义——将一个数据元素（或记录）的任意 序列，重新排列成一个按关键字有序的序列叫~ 排序分类 ❖按待排序记录所在位置 ⚫内部排序：待排序记录存放在内存 ⚫外部排序：排序过程中需对外存进行访问的排序 ❖按排序依据原则 ⚫插入排序：直接插入排序、折半插入排序、希尔排序 ⚫交换排序：冒泡排序、快速排序 ⚫选择排序：简单选择排序、堆排序 ⚫归并排序：2-路归并排序 ⚫基数排序

按排序所需工作量 ●简单的排序方法：T(n)=O(n) 。先进的排序方法：T(n)=O(logn) ●基数排序：T(n)=O(d.n) ★排序基本操作 比较两个关键字大小 必将记录从一个位置移动到另一个位置

❖按排序所需工作量 ⚫简单的排序方法：T(n)=O(n²) ⚫先进的排序方法：T(n)=O(logn) ⚫ 基数排序：T(n)=O(d.n) 排序基本操作 ❖比较两个关键字大小 ❖将记录从一个位置移动到另一个位置

§8.1插入排序 ★直接插入排序 排序过程：整个排序过程为-1趟插入，即先将序列 中第1个记录看成是一个有序子序列，然后从第2个记 录开始，逐个进行插入，直至整个序列有序 算法描述 目 Ch8 1.txt

§8.1 插入排序 直接插入排序 ❖排序过程：整个排序过程为n-1趟插入，即先将序列 中第1个记录看成是一个有序子序列，然后从第2个记 录开始，逐个进行插入，直至整个序列有序 ❖算法描述

例 i=1 (49386597761327 Ch8 1.txt i=238(3849) 65 97761327 i=365(384965) 97 761327 i=497(3849 65 97) 76 1327 i=576(384965 7697)1327 i=6 13(13 384965769727 =727(13273849657697 排序结果：(13273849657697) D

例 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 j j j j j j 27 38 49 65 76 97 排序结果：(13 27 38 49 65 76 97)

算法评价 目 Ch8 1.txt ●时间复杂度 ◆若待排序记录按关键字从小到大排列（正序） 关键字比较次数： 之1=n-1 i=2 记录移动次数： 2=2(n-1) i=2 ◆若待排序记录按关键字从大到小排列（逆序） 愈关键字比较次数： 2= (n+2)(n-1) 2 海记录移动次数： 2∑(i+1)= (n+4)(n-1) 2 ◆若待排序记录是随机的，取平均值 章关键字比较次数： n T(n)=0(n2) 章记录移动次数： ●空间复杂度： S()=0(1) Ch8 1.c

❖算法评价 ⚫时间复杂度 ◆若待排序记录按关键字从小到大排列(正序) 关键字比较次数： 1 1 2  = − = n n i 记录移动次数： 2 2( 1) 2  = − = n n i ◆若待排序记录按关键字从大到小排列(逆序) 关键字比较次数： 2 ( 2)( 1) 2 + −  = = n n i n i 记录移动次数： 2 ( 4)( 1) ( 1) 2 + −  + = = n n i n i ◆若待排序记录是随机的，取平均值 关键字比较次数： 4 2 n 记录移动次数： 4 2 n T(n)=O(n²) ⚫空间复杂度：S(n)=O(1) Ch8_1.c

★折半插入排序 必排序过程：用折半查找方法确定插入位置的排序叫~ 例 =1 (30)1370853942620 i=213 (13 30)708539426 20 =7 6 (6 13 3039 42 70 85)20 i=820 133039 4270 85)20 m i=820 6-s 30 39 42 70 85)20 i=8 20 (6 13 39 42 70 85)20 s mj i=820 (6 13 9 39 42 70 85)20 i=820 (6 13 203039 427085)

折半插入排序 ❖排序过程：用折半查找方法确定插入位置的排序叫~ 例 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 30 39 42 70 85 ) 20 s m j i=8 20 (6 13 30 39 42 70 85 ) 20 s m j i=8 20 (6 13 30 39 42 70 85 ) 20 s mj i=8 20 (6 13 30 39 42 70 85 ) 20 j s i=8 20 (6 13 20 30 39 42 70 85 )

算法描述 Ch8 2 txt 必算法评价 ●时间复杂度：T(n)=O(n) ●空间复杂度：S)=O(1)》 Ch8 2.c

❖算法描述 ❖算法评价 ⚫时间复杂度：T(n)=O(n²) ⚫空间复杂度：S(n)=O(1) Ch8_2.c

★希尔排序（缩小增量法） 必排序过程：先取一个正整数d1<n,把所有相隔d1的记 录放一组，组内进行直接插入排序；然后取d2<d1, 重复上述分组和排序操作；直至di=1,即所有记录放 进一个组中排序为止

希尔排序(缩小增量法) ❖排序过程：先取一个正整数d1<n，把所有相隔d1的记 录放一组，组内进行直接插入排序；然后取d2<d1， 重复上述分组和排序操作；直至di=1，即所有记录放 进一个组中排序为止

例初始：4938659776132748554 取d1=5 一趟分组：493865977613 274855 4 趟排序：1327485544938659776 取d2=3 二趟分组：13 2748554493865.9776 二趟排序：1344838274955659776 取d3=1 三趟分组：1327485544938 659776 三趟排序：4132738484955657697

取d3=1 三趟分组：13 27 48 55 4 49 38 65 97 76 三趟排序：4 13 27 38 48 49 55 65 76 97 例 初始： 49 38 65 97 76 13 27 48 55 4 一趟排序：13 27 48 55 4 49 38 65 97 76 二趟排序：13 4 48 38 27 49 55 65 97 76 取d1=5 一趟分组：49 38 65 97 76 13 27 48 55 4 取d2=3 二趟分组：13 27 48 55 4 49 38 65 97 76

必算法描述 Ch8_3.txt #define T 3 intd0={5,3,1; 例 1327485544938659776 一趟排序：1344838274955659776 iitt06111 二趟排序：1344838274955659776 Ch8 3.c

❖算法描述 Ch8_3.c 例 49 38 65 97 76 13 27 48 55 4 #define T 3 int d[]={5,3,1}; j i 13 27 49 38 一趟排序：13 27 48 55 4 49 38 65 97 76 j i j i 4 27 j j i i 55 j i 38 j j j i i i 二趟排序：13 4 48 38 27 49 55 65 97 76 j j i i 48 65 j i 55 97 j i 4 76