电子科技大学 软件技术基础 3.8.2排序算洁（二) 主讲教师：刘民岷 ■ 航空航天学院 软件技术基础课程组
软件技术基础 主讲教师：刘民岷 航空航天学院 软件技术基础课程组
3、 快速排序 快速排序法是一位计算机科学家C.A.R.Hoare推出并命名的。曾被 认为是最好的一种排序方法。快速排序法是对冒泡排序法的一种 改进，也是基于交换排序的一种算法。因此，被称为“分区交换 排序” 在待排序序列中按某种方法选取一个元素K，以它为分界点，用 交换的方法将序列分为两个部分：比该值小的放在左边，否则在 右边。形成 {左子序列)K{右子序列 再分别对左、右两部分实施上述分解过程，直到各子序列长度为1 ,即有序为止。 电子科技大学刘民岷 排序算法 2
电子科技大学 刘民岷 排序算法 2 • 快速排序法是一位计算机科学家C.A.R.Hoare推出并命名的。曾被 认为是最好的一种排序方法。快速排序法是对冒泡排序法的一种 改进，也是基于交换排序的一种算法。因此，被称为“分区交换 排序”。 • 在待排序序列中按某种方法选取一个元素K，以它为分界点，用 交换的方法将序列分为两个部分：比该值小的放在左边，否则在 右边。形成 {左子序列} K {右子序列} 再分别对左、右两部分实施上述分解过程，直到各子序列长度为1 ，即有序为止
3、 快速排序（续） ,分界点元素值K的选取方法不同，将构成不同的排序法，也将影 响排序的效率： 取左边第1个元素为分界点； -取中点A[(Ieft+right)/2]为分界点； 一选取最大和最小值的平均值为分界点等。 ·设有序列{al,a2,.,An,选取中点元素K为分界点，分别从序列两 头分别与K进行比较，小于K的元素交换到左边，否则交换到右边；一 趟处理后，左边子序列的元素均小于分界点值K,右边子序列元素均 大于等于K值。 电子科技大学刘民岷 排序算法 3
电子科技大学 刘民岷 排序算法 3 • 分界点元素值K的选取方法不同，将构成不同的排序法，也将影 响排序的效率： – 取左边第1个元素为分界点； – 取中点A[(left+right)/2]为分界点； – 选取最大和最小值的平均值为分界点等。 • 设有序列{a1，a2，…,An},选取中点元素K为分界点,分别从序列两 头分别与K进行比较,小于K的元素交换到左边,否则交换到右边;一 趟处理后,左边子序列的元素均小于分界点值K,右边子序列元素均 大于等于K值
3、 快速排序（续）一一 算洁步骤 >分别从两端开始，指针指向第一个元素Alleft],指针指向最后 一个元素A[right],分界点取K; >循环（s) ·从右边开始进行比较： 若K≥A[们，则将A[们交换到左边； 若KA,则i=计1，再进行比较； 若K≤A,则将A[)交换到右边。 ■ 当=时，一次分解操作完成。 > 在对分解出的左、右两个子序列按上述步骤继续进行分解，直 到子序列长度为1（不可再分）为止，也即序列全部有序。 电子科技大学刘民岷 排序算法 4
电子科技大学 刘民岷 排序算法 4 ➢ 分别从两端开始，指针i指向第一个元素A[left]，指针j指向最后 一个元素A[right]，分界点取K ； ➢ 循环（ij） ▪ 从右边开始进行比较： 若K A[j]，则将A[j]交换到左边； 若K A[i]，则 i=i+1，再进行比较； 若K A[i]，则将A[i]交换到右边。 ▪ 当i=j时，一次分解操作完成。 ➢ 在对分解出的左、右两个子序列按上述步骤继续进行分解，直 到子序列长度为1（不可再分）为止，也即序列全部有序
3、快速排序（续）一一 算洁举例 例序列{49,38,60,90,70,15,30,49}的一趟快速排序。 初始状态：49 386049701530 比较次数 k=49 49 3860 497015 30 2(i1、j1) 30 38 6049 7015 49 30 38 49 49 70 15 60 3(i2、j1) 30 38 15 49 70 60 3(i1、j2) i {30 3815 49} 49{70 60} 小计：8 电子科技大学刘民岷 排序算法 5
电子科技大学 刘民岷 排序算法 5 • 例 序列{49,38,60,90,70,15,30,49}的一趟快速排序
归并排序 归并(Merge)于 排序法是将两个（或两个以上）有序表合 并成一个新的有序表；即把待排序序列分为若干个子序列 ，每个子序列是有序的。然后再把有序子序列合并为整体 有序序列。 将已有序的子序列合并，得到完全有序的序列；即先使每 个子序列有序，再使子序列段间有序。若将两个有序表合 并成一个有序表，称为2-路归并。 归并排序步骤： 把待排序的n个记录看作是长度为1的有序序列。将相邻子序列两 两归并为长度为2的有序序列； 把得到的/2个长度为2的有序子序列再归并为长度为2*2的有序 序列； 按$tep2的方式，重复对相邻有序子序列进行归并操作，直到成为 一个有序序列为止。 电子科技大学刘民岷 排序算法 6
电子科技大学 刘民岷 排序算法 6 • 归并（Merge）排序法是将两个（或两个以上）有序表合 并成一个新的有序表；即把待排序序列分为若干个子序列 ，每个子序列是有序的。然后再把有序子序列合并为整体 有序序列。 • 将已有序的子序列合并，得到完全有序的序列；即先使每 个子序列有序，再使子序列段间有序。若将两个有序表合 并成一个有序表，称为2-路归并。 • 归并排序步骤： – 把待排序的n个记录看作是长度为1的有序序列。将相邻子序列两 两归并为长度为2的有序序列； – 把得到的n/2个长度为2的有序子序列再归并为长度为 2*2 的有序 序列； – 按Step2的方式，重复对相邻有序子序列进行归并操作，直到成为 一个有序序列为止
4、归并排序（续） 归并排序步骤： -把待排序的n个记录看作是长度为1的有序序列。将相 邻子序列两两归并为长度为2的有序序列； -把得到的/2个长度为2的有序子序列再归并为长度为 2*2的有序序列； -按Step2的方式，重复对相邻有序子序列进行归并操作， 直到成为一个有序序列为止。 电子科技大学刘民岷 排序算法 7
电子科技大学 刘民岷 排序算法 7 • 归并排序步骤： – 把待排序的n个记录看作是长度为1的有序序列。将相 邻子序列两两归并为长度为2的有序序列； – 把得到的n/2个长度为2的有序子序列再归并为长度为 2*2 的有序序列； – 按Step2的方式，重复对相邻有序子序列进行归并操作， 直到成为一个有序序列为止
4、归并排序（续）一 举例 设有待排序数列{49,38,65,97,76,12,27} 一第一趟处理，先将每个元素看成是有序的子序列，即 [49][38][65][97][76][12][27] -第二趟处理，将长度为1的子序列合并为长度为2的子序列，即 [38,49][65,97][12,76][27] 第三趟处理，将长度为2的子序列合并为长度为4的子序列，即 [38,49,65,97][12,27,76] -第四趟处理，将长度为4的子序列合并为长度为8的序列，即 [12,27,38,49,65,76,97] 电子科技大学刘民岷 排序算法 8
电子科技大学 刘民岷 排序算法 8 设有待排序数列 {49，38，65，97，76，12，27} – 第一趟处理，先将每个元素看成是有序的子序列，即 [49] [38] [65] [97] [76] [12] [27] – 第二趟处理，将长度为1的子序列合并为长度为2的子序列，即 [38 ，49] [65，97] [12 ，76] [ 27 ] – 第三趟处理，将长度为2的子序列合并为长度为4的子序列，即 [38 ，49 ，65，97] [12 ，27，76 ] – 第四趟处理，将长度为4的子序列合并为长度为8的序列，即 [12，27，38 ，49 ，65，76，97]
5、排序算洁总结 ■简单插入排序 ■简单选择排序 稳定 ■冒泡排序 ■快速排序 不稳定 ■归并排序 电子科技大学刘民岷 排序算法 9
电子科技大学 刘民岷 排序算法 9 ◼ 简单插入排序 ◼ 简单选择排序 ◼ 冒泡排序 ◼ 快速排序 ◼ 归并排序 稳定 不稳定
