关于快速排序第一次扫描后的结果关键码序列(Q,H,C,Y,Q,A,M,S,R,D,F,X),若采用以第一个元素为分界元素的快速排序法,则扫描一趟的结果是FHCDQAMQRSYX请问这个结果对吗,能否简单说明一下原因.
来源:学生作业帮助网 编辑:作业帮 时间:2024/10/04 04:40:28
关于快速排序第一次扫描后的结果关键码序列(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
这个结果与你所说的有差异,不知道是不是扫描方法造成的.