《数据结构》 第十章上)
《数据结构》 第十章(上)
第十章内部排序 数据结构 10.1概述 10.2插入排序 10.2.1直接插入排序 10.2.2其它插入排序 10.2.3希尔排序 10.3快速排序 10.4选择排序 10.4.1简单选择排序 10.4.3堆排序 10.5归并排序 10.6基数排序 10.6.1多关键字的排序 10.6.2链式基数排序 10.7各种内部排序方法的比较讨论
数据结构 tjm 第十章 内部排序 10.1 概述 10.2 插入排序 10.2.1 直接插入排序 10.2.2 其它插入排序 10.2.3 希尔排序 10.3 快速排序 10.4 选择排序 10.4.1 简单选择排序 10.4.3 堆排序 10.5 归并排序 10.6 基数排序 10.6.1 多关键字的排序 10.6.2 链式基数排序 10.7 各种内部排序方法的比较讨论
数据结构 101概述 排序:将一个数据元素(或记录)的任意序列,重新 排列成一个按关键字有序的序列。 有序表与无序表:一组记录按关键字的递增或递减次 序排列得到的结果被称之为有序表,相应地,把排序 前的状态称为无序表。 正序表与逆序表:若有序表是按关键字升序排列的, 则称为升序表或正序表,否则称为降序表或逆序表。 不失普遍性,一般只讨论正序表。 内部排序和外部排序: 内部排序:待排序记录存放在内存 外部排序:排序过程中需对外存进行访问的排序
数据结构 tjm 10.1 概述 排序：将一个数据元素（或记录）的任意序列，重新 排列成一个按关键字有序的序列。 有序表与无序表：一组记录按关键字的递增或递减次 序排列得到的结果被称之为有序表，相应地，把排序 前的状态称为无序表。 内部排序和外部排序： 内部排序：待排序记录存放在内存 外部排序：排序过程中需对外存进行访问的排序 正序表与逆序表：若有序表是按关键字升序排列的， 则称为升序表或正序表，否则称为降序表或逆序表。 不失普遍性，一般只讨论正序表
数据结构 内部排序得方法: 插入排序:直接插入排序、折半插入排序、希尔排序 交换排序:冒泡排序、快速排序 选择排序:简单选择排序、堆排序 归并排序:2-路归并排序 其它排序:多关键字排序、基数排序 排序基本操作: 比较两个关键字大小 将记录从一个位置移动到另一个位置 排序算法的稳定性: 考虑有多个数据元素具有相同关键字的情况。 稳定:具有相同关键字的数据元素的相对位置关系 在排序前后保持不变。 不稳定:具有相同关键字的数据元素的相对位置关 系在排序前后发生了改变
数据结构 tjm 内部排序得方法： 插入排序：直接插入排序、折半插入排序、希尔排序 交换排序：冒泡排序、快速排序 选择排序：简单选择排序、堆排序 归并排序：2-路归并排序 其它排序: 多关键字排序、基数排序 排序基本操作： 比较两个关键字大小 将记录从一个位置移动到另一个位置 排序算法的稳定性: 考虑有多个数据元素具有相同关键字的情况。 稳定：具有相同关键字的数据元素的相对位置关系 在排序前后保持不变。 不稳定：具有相同关键字的数据元素的相对位置关 系在排序前后发生了改变
102插入排序 数据结构 1021直接插入排序 排序过程:整个排序过程为n-1趟插入,即先将序 列中第1个记录看成是一个有序子序列,然后从第2 个记录开始,逐个进行插入,直至整个序列有序 算法参见P265 例:i=1(49)386597761327 i=238(3849)6597761327 i365(384965)97761327 97638496597)761327 i=576(3849657697)1327 i=613(133849657697)27 i=727(3273849657697 排序结果:3p78955697)
数据结构 tjm 例: 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) 10.2 插入排序 10.2.1 直接插入排序 排序过程：整个排序过程为n-1趟插入，即先将序 列中第1个记录看成是一个有序子序列，然后从第2 个记录开始，逐个进行插入，直至整个序列有序。 算法参见P265