电子斜技大学 软件技术基础 3.8.1挑序算洁（) 主讲教师：刘民岷 航空航天学院 a口2 软件技术基础课程组
软件技术基础 主讲教师：刘民岷 航空航天学院 软件技术基础课程组
排序的概念 排序是将一组数据元素按其排序码进行递增或递减排列的 运算操作。有关排序的基本概念： 排序码：排序的依据是排序码，它是数据元素中的一个或多个字段 ；排序码可以是关键字，也可以不是关键字。 排序算法的稳定性：如果待排序的序列中，存在多个具有相同排序 码的数据元素，若经过排序这些数据元素的相对次序保持不变，则 称这种排序算法是稳定的，若经过排序，这些数据元素的相对次序 发生了改变，则称这种排序算是不稳定的。 内部排序和外部排序：内部排序指对数据元素序列的整个排序过 程是在计算机内存中进行的排序；外部排序是指待排序的数据元素 太多，不能同时存放在内存中，所以排序操作不仅要使用内存，而 且还要使用外部存储器存储数据的排序。 电子科技大学刘民岷 排序算法 2
电子科技大学 刘民岷 排序算法 2 排序是将一组数据元素按其排序码进行递增或递减排列的 运算操作。有关排序的基本概念： • 排序码：排序的依据是排序码，它是数据元素中的一个或多个字段 ；排序码可以是关键字，也可以不是关键字。 • 排序算法的稳定性：如果待排序的序列中，存在多个具有相同排序 码的数据元素，若经过排序这些数据元素的相对次序保持不变，则 称这种排序算法是稳定的，若经过排序，这些数据元素的相对次序 发生了改变，则称这种排序算是不稳定的。 • 内部排序和外部排序：内部排序指对数据元素序列的整个排序过 程是在计算机内存中进行的排序；外部排序是指待排序的数据元素 太多，不能同时存放在内存中，所以排序操作不仅要使用内存，而 且还要使用外部存储器存储数据的排序
2、简单排序 采用顺序存储结构存放排序的数据元素，存储结构说明为： typedef struct{ keytype key; /排序码 ...}Elemtype; Elemtype x[MAXNUM]: 1)简单插入排序 2)简单选择排序 3)冒泡排序 电子科技大学刘民岷 排序算法 3
电子科技大学 刘民岷 排序算法 3 • 采用顺序存储结构存放排序的数据元素，存储结构说明为： typedef struct { … keytype key; //排序码 …}Elemtype; Elemtype x[MAXNUM]; 1）简单插入排序 2）简单选择排序 3）冒泡排序
2、简单排序（续） 1)简单插入排序 基本思想：将个元素的数列分为已有序和无序两个部分。每次处理 就是将无序数列的第一个元素与有序数列的元素从后往前逐个进行比较， 找出插入位置，将该元素插入到有序数列的合适位置中。 设有数列{18,12,10,12,30,16} 初始状态：{18}，{12,10,12,30,16} 比较次数 i=1 {18},{12,10,12,30,16} 1 1=2 {12,18},{10,12,30,16} 2 i=3 {10,12,18},{12,30,16} 2 i=4 {10,12,12,18},{30,16} 1 i=5 {10,12,12,18,30},{16} 3 {10,12,12,16,18,30} 电子科技大学刘民岷 排序算法 总计： 9次 4
电子科技大学 刘民岷 排序算法 4 1）简单插入排序 基本思想： 将n个元素的数列分为已有序和无序两个部分。每次处理 就是将无序数列的第一个元素与有序数列的元素从后往前逐个进行比较, 找出插入位置,将该元素插入到有序数列的合适位置中
2、简单排序（续） 2)简单选择排序 基本思想：每次从待排序的记录中选出关键字最小（或最大）的记 录，顺序放在已有序的记录序列的最后（或最前)面，直到全部数列 有序。 例12：待排序数据元素的排序码序列为(2,7,2,2,3,1)，按递增排序 的简单排序过程如下： 初始状态 [2 7 2 2 3 1] 第1趟 1 [7 2 2 3 2] 第2趟 1 2 [7 2 3 2] 第3趟 1 2 2 [7 3 2] 第4趟 1 2 2 2 [3 7] 第5趟 1 2 2 2 3 [7] 最终结果 1 2 2 2 3 7 电子科技大学刘民岷 排序算法 5
电子科技大学 刘民岷 排序算法 5 2）简单选择排序 • 基本思想：每次从待排序的记录中选出关键字最小（或最大）的记 录，顺序放在已有序的记录序列的最后（或最前）面，直到全部数列 有序。 • 例12：待排序数据元素的排序码序列为(2,7,2,2,3,1)，按递增排序 的简单排序过程如下： 初始状态 [2 7 2 2 3 1] 第1趟 1 [7 2 2 3 2] 第2趟 1 2 [7 2 3 2] 第3趟 1 2 2 [7 3 2] 第4趟 1 2 2 2 [3 7] 第5趟 1 2 2 2 3 [7] 最终结果 1 2 2 2 3 7
2、简单排序（续） 3)冒泡排序 指导思想： 两两比较待排序记录的关键字，并交换不满足顺序要求的那些偶对 元素，直到全部数列满足有序为止。 冒泡排序(Bubble sort)是基于交换排序的一种算法。 它是依次两两比较待排序元素；若为逆序（递增或递减）则进行交换， 将待排序元素从左至右比较一遍称为一趟“冒泡”。每趟冒泡都将待排 序列中的最大关键字交换到最后（或最前）位置。直到全部元素有序为 止。 电子科技大学刘民岷 排序算法 6
电子科技大学 刘民岷 排序算法 6 3）冒泡排序 •指导思想： 两两比较待排序记录的关键字，并交换不满足顺序要求的那些偶对 元素，直到全部数列满足有序为止。 •冒泡排序（Bubble sort）是基于交换排序的一种算法。 它是依次两两比较待排序元素；若为逆序(递增或递减)则进行交换， 将待排序元素从左至右比较一遍称为一趟“冒泡” 。每趟冒泡都将待排 序列中的最大关键字交换到最后（或最前）位置。直到全部元素有序为 止
2、简单排序（续） 3)冒泡排序 设有数列{65,97,76,13,27,49,58} 比较次数 第1趟{65,76,13,27,49,58}，{97} 6 第2趟 {65,13,27,49,58},{76,97} 5 第3趟{13,27,49,58}，{65,76,97} 4 第4趟{13,27,49}，{58,65,76,97} 3 第5趟{13,27}，{49,58,65,76,97} 2 第6趟{13}，{27,49,58,65,76,97} 优化间题？ 总计：21次 电子科技大学刘民岷 排序算法 7
电子科技大学 刘民岷 排序算法 7 3）冒泡排序 设有数列{ 65,97,76,13,27,49,58 } 比较次数 第1趟 {65，76，13，27，49，58}，{97} 6 第2趟 {65，13，27，49，58}，{76，97} 5 第3趟 {13，27，49，58}，{65，76，97} 4 第4趟 {13，27，49}，{58，65，76，97} 3 第5趟 {13，27}，{49，58，65，76，97} 2 第6趟 {13}，{27，49，58，65，76，97} 1 总计： 21 次
