快速排序中的循环疑问
#include <stdio.h>void quick_sort(int num[],int left,int right);
void quick_sort(int num[],int left,int right)
{
int temp;
int i=left;
int j=right;
int pivot;
pivot=(num[(left+right)/2]);
while(i<=j)
{
while(num<pivot)//为什么这里一定得是<，不能是<=
{
i++;
}
while(num>pivot)
{
j--;
}
if(i<=j)//这里又为什么是<=,不能是<.亲测两个符号都不能更改，不然程序没显示。
{
temp=num;
num=num;
num=temp;
i++;
j--;
}
}
if(j>left)
{
quick_sort(num,left,j);
}
if(i<right)
{
quick_sort(num,i,right);
}
}
int main()
{
int i=0;
int length;
scanf("%d",&length);
int num;
for(i;i<length;i++)
{
scanf("%d",&num);
}
quick_sort(num,0,length-1);
for(i=0;i<length;i++)
{
printf("%d ",num);
}
printf("\n");
return 0;
} 本帖最后由 FK二十一 于 2022-5-3 10:12 编辑
第一个问题以1234321为例
如果是num[ i]<= pivot : 易知 pivat = 4 ,这时你发现无论如何 i 都找不到比pivot大的，这是第一个循环溢出。下面num > pivot同理
抽象理解就是i 或者 j 需要把pivot换到属于它的位置而不是忽略它。（当然这样理解也可能不全面）
第二个问题以 321 为例
当交换完变成123，这时有：i = j = 1 , array[ i] = array = pivot = 2。这是你会发现如果是 if (i < j) 则上面两个while循环没有改变 i 和 j，而 if
条件又进不去，陷入了死循环。
上面的分析属于断章取义式的分析，应该还有其它分析方法，但我也还不大清楚。或许你可以只记住我的两个例子，
也可以找到更好的理解方法然后告诉我们。
FK二十一 发表于 2022-5-3 10:08
第一个问题以1234321为例
如果是num[ i] pivot同理
抽象理解就是i 或者 j 需要把pivot换到属于它的位置而 ...
第一个我理解了，第二个我还是不是太理解。第二个例子中第一次排完后不是就进入递归了吗，此时应该在第二次调用函数时里新的 i=0；j=1了吧。 rookie555 发表于 2022-5-3 22:53
第一个我理解了，第二个我还是不是太理解。第二个例子中第一次排完后不是就进入递归了吗，此时应该在第二 ...
第一次排完i (0) 和 j (2)中的元素交换，然后i++, j--； 这是i = j = 1 FK二十一 发表于 2022-5-4 09:27
第一次排完i (0) 和 j (2)中的元素交换，然后i++, j--； 这是i = j = 1
突然懂了，感谢大佬回答{:5_106:}
页:
[1]