电子科技大学 软件技术基础 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[们交换到左边; 若K<A[们,则jj-1,再进行比较; ·从左边开始进行比较: 若K>A,则i=计1,再进行比较; 若K≤A,则将A[)交换到右边。 ■ 当=时,一次分解操作完成。 > 在对分解出的左、右两个子序列按上述步骤继续进行分解,直 到子序列长度为1(不可再分)为止,也即序列全部有序。 电子科技大学刘民岷 排序算法 4
电子科技大学 刘民岷 排序算法 4 ➢ 分别从两端开始,指针i指向第一个元素A[left],指针j指向最后 一个元素A[right],分界点取K ; ➢ 循环(ij) ▪ 从右边开始进行比较: 若K A[j],则将A[j]交换到左边; 若K < A[j] ,则 j=j-1,再进行比较; ▪ 从左边开始进行比较: 若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}的一趟快速排序