设要将序列(Q, H, C, Y, P, A, M, S, R, D, F, X)中的关键码按字母序的升序重新排列,经过一次快速排序一趟扫描的结果是(采用初始数据为支点,两头交替逼近的实现方法)的结果是?
时间: 2023-09-18 09:11:25 浏览: 156
快速排序的一趟扫描过程中,是将待排序序列中小于支点的元素移到支点左边,大于支点的元素移到支点右边,最终将支点放置在它的最终位置上。
以本题中的序列为例,我们取初始支点为序列第一个元素 Q。左指针指向序列第二个元素 H,右指针指向序列最后一个元素 X。
首先,从右指针开始向左扫描,找到第一个小于支点的元素 F,将 F 和支点 Q 交换位置,得到序列(F, H, C, Y, P, A, M, S, R, D, Q, X)。此时,左指针仍指向 H,右指针指向元素 X。
接着,从左指针开始向右扫描,找到第一个大于支点的元素 S,将 S 和右指针指向的元素 X 交换位置,得到序列(F, H, C, Y, P, A, M, S, R, D, Q, X)。此时,左指针指向元素 C,右指针指向元素 R。
继续从右指针开始向左扫描,找到第一个小于支点的元素 D,将 D 和支点 Q 交换位置,得到序列(F, H, C, Y, P, A, M, D, R, S, Q, X)。此时,左指针指向元素 C,右指针指向元素 S。
继续从左指针开始向右扫描,找到第一个大于支点的元素 R,将 R 和右指针指向的元素 S 交换位置,得到序列(F, H, C, Y, P, A, M, D, R, S, Q, X)。此时,左指针指向元素 Y,右指针指向元素 Q。
继续从右指针开始向左扫描,找到第一个小于支点的元素 A,将 A 和支点 Q 交换位置,得到序列(F, H, C, A, P, Y, M, D, R, S, Q, X)。此时,左指针指向元素 Y,右指针指向元素 S。
由于左指针和右指针相遇,扫描结束。此时,支点 Q 已经在序列中的正确位置上,且左边的元素均小于 Q,右边的元素均大于 Q。
一趟扫描后的序列为(F, H, C, A, P, Y, M, D, R, S, Q, X)。
阅读全文