用快速排序对下面序列按字母顺序从小到大进行排序: (Jan, Feb, Mar, Apr, May, Jun, Jul, Aug, Sep, Oct, Nov, Dec) 请给出前三次调用Partition的结果。
时间: 2023-09-17 19:12:54 浏览: 126
快速排序的原理是通过分治法将一个大问题拆分成多个小问题来解决,其中Partition函数是将序列分成两个子序列的关键。对于这个序列,我们可以选择任意一个元素作为pivot,假设我们以第一个元素"Jan"作为pivot,Partition函数的过程如下:
1. 首先将pivot挪到最右边,即将"Jan"和"Dec"交换位置,现在序列变为:(Dec, Feb, Mar, Apr, May, Jun, Jul, Aug, Sep, Oct, Nov, Jan)
2. 初始化左右指针i=0, j=10,从左向右扫描,找到第一个大于等于pivot的元素,即找到"Dec",将i指向"Dec",从右向左扫描,找到第一个小于pivot的元素,即找到"Nov",将j指向"Nov"。
3. 交换i和j指向的元素,现在序列变为:(Nov, Feb, Mar, Apr, May, Jun, Jul, Aug, Sep, Oct, Dec, Jan)
4. 继续重复2-3步骤,直到i>=j,此时将pivot和i指向的元素交换位置,序列变为:(Nov, Feb, Mar, Apr, May, Jun, Jul, Aug, Sep, Oct, Jan, Dec)
第一次调用Partition的结果为:(Nov, Feb, Mar, Apr, May, Jun, Jul, Aug, Sep, Oct, Jan, Dec),pivot为"Jan",i=10,j=10。
第二次调用Partition的结果为:(Dec, Feb, Mar, Apr, May, Jun, Jul, Aug, Sep, Oct, Nov, Jan),pivot为"Dec",i=0,j=0。
第三次调用Partition的结果为:(Feb, Apr, Mar, Dec, May, Jun, Jul, Aug, Sep, Oct, Nov, Jan),pivot为"Feb",i=1,j=2。
阅读全文