用快速排序对下面序列按字母顺序从小到大进行排序:( Jan , Feb , Mar , Apr , May , Jun , Jul , Aug , Sep , Oct , Nov , Dec )请给出前三次调用 Partition 的结果。
时间: 2023-09-29 14:08:11 浏览: 96
快速排序的基本思想是将一个大问题划分成两个小问题,分别解决这两个小问题,最终将它们的解合并成一个整体的解。
对于该序列,快速排序的过程如下:
1. 选取一个基准元素,可以选择序列的第一个元素 Jan,将序列划分成两个子序列,一个子序列包含所有小于等于基准元素的元素,另一个子序列包含所有大于基准元素的元素。
初始序列:( Jan , Feb , Mar , Apr , May , Jun , Jul , Aug , Sep , Oct , Nov , Dec )
第一次调用 Partition 后的结果:
基准元素:Jan
左子序列:( ) 右子序列:( Feb , Mar , Apr , May , Jun , Jul , Aug , Sep , Oct , Nov , Dec )
2. 对左右子序列分别重复第一步的操作,直到所有子序列的长度小于等于1。
左子序列:( ) 右子序列:( Feb , Mar , Apr , May , Jun , Jul , Aug , Sep , Oct , Nov , Dec )
第二次调用 Partition 后的结果:
基准元素:Feb
左子序列:( ) 右子序列:( Mar , Apr , May , Jun , Jul , Aug , Sep , Oct , Nov , Dec )
左子序列:( ) 右子序列:( Mar , Apr , May , Jun , Jul , Aug , Sep , Oct , Nov , Dec )
第三次调用 Partition 后的结果:
基准元素:Mar
左子序列:( ) 右子序列:( Apr , May , Jun , Jul , Aug , Sep , Oct , Nov , Dec )
注意:Partition 操作每次只能分割出一个元素,因此需要多次调用 Partition 才能完成整个序列的排序。
阅读全文