5. 5排序算法--快速与归并 课件-2021-2022学年浙教版（2019）高中信息技术选修1

第五章 数据结构与算法 选修1《数据与数据结构》 5.5 排序算法 --快速与归并 学习目标 排序算法 快速排序算法 归并排序算法 快速排序算法 快速排序使用分治法策略来把一个串行（list）分为两个子串行（sub-lists）。 算法步骤： 1、 在数组中选一个基准数（通常为数组第一个）。 2、将数组中小于基准数的数据移到基准数左边，大于基准数的移到右边。 3、对于基准数左、右两边的数组，不断重复以上两个过程，直到每个子集只有一个元素，即为全部有序。 ·快速排序的基本思路 对长度为 n 的数组而言，快速排序的最坏运行情况是 O(n²),但它的平摊期望时间是 O(nlogn) 排序算法 ·快速排序的效率 快速排序算法 ·图解快速排序算法(升序) 排序算法 例如： 对列表a=[ 40, 38, 65, 97, 76, 13, 27, 49 ]的元素进行排序。 1、取第一个元素为基准数 （a[0] = 40） i 指向第一个元素，j 指向最后一个元素 快速排序算法 ·图解快速排序算法(升序) 排序算法 2、把比a[0]的值小的放左边，把比a[0]的值大的放在右边 ①移动 j 找到比a[0]小的值，把它赋值给a[i]，做到小的值放到左边的操作。 ②移动 i 找到比a[0]大的值，把它赋值给a[j]，做到大的值放到右边的操作。 快速排序算法 ·图解快速排序算法(升序) 排序算法 ③重复①②的操作。 快速排序算法 ·图解快速排序算法(升序) 排序算法 ④当重复①②操作时，遇到 i == j 时，停止重复①②的操作。 3、把基准数赋值给 a[i] ,即基准数的左边都是比它小，右边都比它大。 快速排序算法 ·图解快速排序算法(升序) 排序算法 4、把列表分成俩部分，比基准数小的为一个部分，比基准数大的为另一部分。 5、每个部分重复 1 2 3 步骤的操作，一直到只剩一个元素为止，结束重复操作。即，得到的序列，就是