第八章排序 ★排序定义—将一个数据元素(或记录)的任意 序列,重新排列成一个按关键字有序的序列叫 ★排序分类 ◆按待排序记录所在位置 内部排序:待排序记录存放在内存 外部排序:排序过程中需对外存进行访问的排序 今按排序依据原则 ●插入排序:直接插入排序、折半插入排序、希尔排序 ●交换排序:冒泡排序、快速排序 ●选择排序:简单选择排序、堆排序 ●归并排序:2路归并排序 ●基数排序
第八章 排序 排序定义——将一个数据元素（或记录）的任意 序列，重新排列成一个按关键字有序的序列叫~ 排序分类 ❖按待排序记录所在位置 ⚫内部排序：待排序记录存放在内存 ⚫外部排序：排序过程中需对外存进行访问的排序 ❖按排序依据原则 ⚫插入排序：直接插入排序、折半插入排序、希尔排序 ⚫交换排序：冒泡排序、快速排序 ⚫选择排序：简单选择排序、堆排序 ⚫归并排序：2-路归并排序 ⚫基数排序
今按排序所需工作量 ●简单的排序方法:T(n)=O(n2) ●先进的排序方法:T(n)=O(ogn) ●基数排序:T(n)=O(dn) ★排序基本操作 今比较两个关键字大小 今将记录从一个位置移动到另一个位置
❖按排序所需工作量 ⚫简单的排序方法：T(n)=O(n²) ⚫先进的排序方法：T(n)=O(logn) ⚫ 基数排序：T(n)=O(d.n) 排序基本操作 ❖比较两个关键字大小 ❖将记录从一个位置移动到另一个位置
§8.1插入排序 ★直接插入排序 ◆排序过程:整个排序过程为n-1趟插入,即先将序列 中第1个记录看成是一个有序子序列,然后从第2个记 录开始,逐个进行插入,直至整个序列有序 ◆算法描述 CH8 1.txt
§8.1 插入排序 直接插入排序 ❖排序过程：整个排序过程为n-1趟插入，即先将序列 中第1个记录看成是一个有序子序列，然后从第2个记 录开始，逐个进行插入，直至整个序列有序 ❖算法描述
例 1(49386597761327 Ch8 1.trt i=238(3849)6597761327 i=365(384965)97761327 497(38496597)761327 i=576(3849657697)1327 613(133849657697)27 i=727(13273849657697 排序结果:(13273849657697
例 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.trt 0时间复条度 ◆若待排序记录按关键字从小到大排列(正序) 关键字比较次数: 记录移动次数:∑2=2(n-1) ◆若待排序记录按关键字从大到小排列(逆序) 关键字比较次数:>i (n+2)(n-1) 记录移动次数:∑(+1) (n+4)(n-1 ◆若待排序记录是随机的,取平均值 关键字比较次数 4 T(n)=O(n2) 记录移动次数: 4 ●空间复杂度:S(n=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