作业帮关于快速排序第一次扫描后的结果关键码序列(Q,H,C,Y,Q,A,M,S,R,D,F,X),若采用以第一个元素为分界元素的快速排序法,则扫描一趟的结果是FHCDQAMQRSYX请问这个结果对吗,能否简单说明一下原因.
来源：学生作业帮助网 编辑：作业帮 时间：2024/04/20 04:03:07
关于快速排序第一次扫描后的结果关键码序列(Q,H,C,Y,Q,A,M,S,R,D,F,X),若采用以第一个元素为分界元素的快速排序法,则扫描一趟的结果是FHCDQAMQRSYX请问这个结果对吗,能否简单说明一下原因.
关于快速排序第一次扫描后的结果
关键码序列(Q,H,C,Y,Q,A,M,S,R,D,F,X),若采用以第一个元素为分界元素的快速排序法,则扫描一趟的结果是FHCDQAMQRSYX
请问这个结果对吗,能否简单说明一下原因.
关于快速排序第一次扫描后的结果关键码序列(Q,H,C,Y,Q,A,M,S,R,D,F,X),若采用以第一个元素为分界元素的快速排序法,则扫描一趟的结果是FHCDQAMQRSYX请问这个结果对吗,能否简单说明一下原因.
假设 i 为从左到右扫描的下标,j 为从右向左扫描的下标,则扫描的代码如下：
int partition(char key[], int left, int right)
{
char &pivot = key[left]; // 第一个元素为分界
int i = left+1, j = right;
while(true) {
/* 向左扫描,找到首个大于 pivot 的关键码 */
while(i < right && key[i] <= pivot)
i++;
/* 向右扫描,找到首个小于等于 pivot 的关键码 */
while(j > left && key[j] > pivot)
j++;
if(i < j)
swap(a[i], a[j]);
else
break;
}
swap(pivot, a[j]); // 交换后 key[left..j-1] <= key[j] < key[j+1..right]
return j;
}
根据以上代码可知,交换的过程为：
Q H C Y Q A M S R D F X
0 1 2 3 4 5 6 7 8 9 10 11
（1）i = 3,j = 10,需要交换,得到 ：
Q H C F Q A M S R D Y X
0 1 2 3 4 5 6 7 8 9 10 11
（2）i = 7,j = 9,需要交换,得到：
Q H C F Q A M D R S Y X
0 1 2 3 4 5 6 7 8 9 10 11
（3）i = 8,j = 7,退出循环,将 pivot 与 key[j] 交换,得到：
D H C F Q A M Q R S Y X
0 1 2 3 4 5 6 7 8 9 10 11
这个结果与你所说的有差异,不知道是不是扫描方法造成的.