用快速排序对下面序列按字母顺序从小到大进行排序:( Jan , Feb , Mar , Apr , May , Jun , Jul , Aug , Sep , Oct , Nov , Dec )请给出前三次调用 Partition 的结果。
时间: 2023-09-24 09:09:27 浏览: 37
快速排序的核心是分治思想和Partition操作。Partition操作是指将数组分为小于等于pivot和大于等于pivot两部分。对于字母序列,可以将其转化为数字序列,如a=1,b=2,以此类推。假设我们选择Sep作为pivot,则Partition后的结果如下:
1. (Jan, Feb, Mar, Apr, May, Jun, Jul, Aug, Sep, Oct, Nov, Dec)
分界点:Sep
左侧数组:(Jan, Feb, Mar, Apr, May, Jun, Jul, Aug)
右侧数组:(Oct, Nov, Dec)
2. (Jan, Feb, Mar, Apr, May, Jun, Jul, Aug)
分界点:Aug
左侧数组:(Jan, Feb, Mar, Apr, May, Jun, Jul)
右侧数组:(Aug)
3. (Jan, Feb, Mar, Apr, May, Jun, Jul)
分界点:Jul
左侧数组:(Jan, Feb, Mar, Apr, May, Jun)
右侧数组:(Jul)
第三次调用Partition后,左侧数组已经有序,右侧数组只有一个元素,也是有序的。因此,整个序列已经排好序了。
相关问题
用快速排序对下面序列按字母顺序从小到大进行排序: (Jan, Feb, Mar, Apr, May, Jun, Jul, Aug, Sep, Oct, Nov, Dec) 请给出前三次调用Partition的结果。
快速排序的原理是通过分治法将一个大问题拆分成多个小问题来解决,其中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。
用快速排序对下面序列按字母顺序从小到大进行排序: (Jan, Feb, Mar, Apr, May, Jun, Jul, Aug, Sep, Oct, Nov, Dec) 请给出前三次调用Partition的结果。
首先,我们需要选择一个基准元素来进行划分。由于是按字母顺序进行排序,我们可以选择序列中间的元素 "Jun" 作为基准元素。
第一次调用Partition:
left = 0, right = 11, pivot = "Jun"
比较序列中的元素与基准元素 "Jun",可以得到以下两个子序列:
["Jan", "Feb", "Mar", "Apr", "May"] 和 ["Jul", "Aug", "Sep", "Oct", "Nov", "Dec"]
下面是第一次调用Partition的结果:
["Jan", "Feb", "Mar", "Apr", "May", "Jun", "Jul", "Aug", "Sep", "Oct", "Nov", "Dec"]
第二次调用Partition:
left = 0, right = 5, pivot = "Jun"
比较序列中的元素与基准元素 "Jun",可以得到以下两个子序列:
["Jan", "Feb", "Mar", "Apr", "May"] 和 ["Jun"]
下面是第二次调用Partition的结果:
["Jan", "Feb", "Mar", "Apr", "May", "Jun", "Jul", "Aug", "Sep", "Oct", "Nov", "Dec"]
第三次调用Partition:
left = 6, right = 11, pivot = "Jun"
比较序列中的元素与基准元素 "Jun",可以得到以下两个子序列:
["Jul", "Aug", "Sep", "Oct", "Nov", "Dec"] 和 ["Jun"]
下面是第三次调用Partition的结果:
["Jan", "Feb", "Mar", "Apr", "May", "Jun", "Jul", "Aug", "Sep", "Oct", "Nov", "Dec"]