[已解决]快速排序中的循环疑问

rookie555

#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[i]<pivot)//为什么这里一定得是<，不能是<=
                {
                        i++;
                }
                while(num[j]>pivot)
                {
                        j--;
                }
                if(i<=j)//这里又为什么是<=,不能是<.亲测两个符号都不能更改，不然程序没显示。
                {
                        temp=num[i];
                        num[i]=num[j];
                        num[j]=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[length];
        for(i;i<length;i++)
        {
                scanf("%d",&num[i]);
        }
        quick_sort(num,0,length-1);
        for(i=0;i<length;i++)
        {
                printf("%d ",num[i]);
        }
        printf("\n");
        return 0;
}

最佳答案

月排行榜 / 总排行榜

FK二十一

2022-5-3 10:08:41

第一个问题以1234321为例
如果是num[ i]<= pivot : 易知 pivat = 4 ,这时你发现无论如何 i 都找不到比pivot大的，这是第一个循环溢出。下面num[j] > pivot同理
抽象理解就是i 或者 j 需要把pivot换到属于它的位置而不是忽略它。（当然这样理解也可能不全面）
第二个问题以 321 为例
当交换完变成123，这时有：i = j = 1 , array[ i] = array[j] = pivot = 2。这是你会发现如果是 if (i < j) 则上面两个while循环没有改变 i 和 j，而 if
条件又进不去，陷入了死循环。
上面的分析属于断章取义式的分析，应该还有其它分析方法，但我也还不大清楚。或许你可以只记住我的两个例子，
也可以找到更好的理解方法然后告诉我们。

跳转到最佳答案楼层

FK二十一

第一个问题以1234321为例
如果是num[ i]<= pivot : 易知 pivat = 4 ,这时你发现无论如何 i 都找不到比pivot大的，这是第一个循环溢出。下面num[j] > pivot同理
抽象理解就是i 或者 j 需要把pivot换到属于它的位置而不是忽略它。（当然这样理解也可能不全面）
第二个问题以 321 为例
当交换完变成123，这时有：i = j = 1 , array[ i] = array[j] = pivot = 2。这是你会发现如果是 if (i < j) 则上面两个while循环没有改变 i 和 j，而 if
条件又进不去，陷入了死循环。
上面的分析属于断章取义式的分析，应该还有其它分析方法，但我也还不大清楚。或许你可以只记住我的两个例子，
也可以找到更好的理解方法然后告诉我们。

rookie555

FK二十一 发表于 2022-5-3 10:08
第一个问题以1234321为例
如果是num[ i] pivot同理
抽象理解就是i 或者 j 需要把pivot换到属于它的位置而 ...

第一个我理解了，第二个我还是不是太理解。第二个例子中第一次排完后不是就进入递归了吗，此时应该在第二次调用函数时里新的 i=0；j=1了吧。

FK二十一

rookie555 发表于 2022-5-3 22:53
第一个我理解了，第二个我还是不是太理解。第二个例子中第一次排完后不是就进入递归了吗，此时应该在第二 ...

第一次排完i (0) 和 j (2)中的元素交换，然后i++, j--； 这是i = j = 1

rookie555

FK二十一 发表于 2022-5-4 09:27
第一次排完i (0) 和 j (2)中的元素交换，然后i++, j--； 这是i = j = 1

突然懂了，感谢大佬回答