[已解决]C语言第36讲-快速排序 求助

冰激凌太烫

#include <stdio.h>

void quick_sort(int array[],int  left,int right);

void quick_sort(int array[], int  left, int right)
{
        int i = left, j = right;
        int temp;
        int pivot;

        pivot = array[(left + right) / 2];

        while (i <= j)
        {
                //从左到右找到大于等于基准点的数
                while (array[i] < pivot)
                {
                        i++;
                }
                //从右到左找到小于等于基准点的数
                while (array[j] > pivot)
                {
                        j--;
                }
                //如果i <= j，则互换元素
                if (i <= j)                                             //为什么在这一步i，j互换元素后，pivot就会向前移动一位，成为新的pivot？是因为i++和j--嘛？？（有附图）还望各路大神指点一二
                {
                        temp = array[i];
                        array[i] = array[j];
                        array[j] = temp;
                        i++;
                        j--;
                }
        }

        //结束第一趟排序，开始递归
        if(left < j)
        {
                quick_sort(array,left, j);
        }
        if(i < right)
        {
                quick_sort(array, i, right);
        }
}

int main(void)
{
        int array[] = { 12,3,33,23,91,34,8,24,0,61,16 };
        int i, length;

        length = sizeof(array) / sizeof(array[0]);
        quick_sort(array, 0, length - 1);

        printf("排序后的结果是:");
        for (i = 0; i < length; i++)
        {
                printf("%d",array[i]);
                putchar(' ');
        }
       
        return 0;
}

最佳答案

月排行榜 / 总排行榜

耻思lhj

2020-4-16 08:51:28

1，代码就是在数组中间找一个数，赋值pivot。
2，然后从左到右，左边的数一个一个和pivot比，遇到比pivot大的数就停下来，叫a吧。然后执行下面。
3，另一边从右到左，右边的数一个一个与pivot比，遇到比pivot小的数就停下来，与之前上面的数a交换。
4，换完就继续第2步，直到j>i，在这个i和j交叉的位置的左边找不到比pivot大的数，右边找不到比pivot小的数。
然后就分成了两个部分了(一个是都小于pivot的部分，一个是都大于pivot的部分)，在这两个部分里分别调用quick_sort，第一部分又从中间取个值赋值给pivot，第二部分也从中间取个值赋值给pivot（调用了两次函数）。

跳转到最佳答案楼层

耻思lhj

pivot并没有移动，他只是被用来比较而已
他仅仅只是个值而已
互换之后并不会换pivot，只有在j>i也就是下面重新调用的时候会重置pivot

冰激凌太烫

耻思lhj 发表于 2020-4-16 08:37
pivot并没有移动，他只是被用来比较而已
他仅仅只是个值而已

那是在哪行代码进行比较的？

耻思lhj

冰激凌太烫 发表于 2020-4-16 08:38
那是在哪行代码进行比较的？

while（）里面比较的

冰激凌太烫

耻思lhj 发表于 2020-4-16 08:44
while（）里面比较的

但还是没有说pivot会改变的啊，它只是在while循环比较找到基准点，然后再left和right元素互换，不太理解哪行代码把pivot 的元素改变了的

耻思lhj

1，代码就是在数组中间找一个数，赋值pivot。
2，然后从左到右，左边的数一个一个和pivot比，遇到比pivot大的数就停下来，叫a吧。然后执行下面。
3，另一边从右到左，右边的数一个一个与pivot比，遇到比pivot小的数就停下来，与之前上面的数a交换。
4，换完就继续第2步，直到j>i，在这个i和j交叉的位置的左边找不到比pivot大的数，右边找不到比pivot小的数。
然后就分成了两个部分了(一个是都小于pivot的部分，一个是都大于pivot的部分)，在这两个部分里分别调用quick_sort，第一部分又从中间取个值赋值给pivot，第二部分也从中间取个值赋值给pivot（调用了两次函数）。

耻思lhj

冰激凌太烫 发表于 2020-4-16 08:48
但还是没有说pivot会改变的啊，它只是在while循环比较找到基准点，然后再left和right元素互换，不太理解 ...

//结束第一趟排序，开始递归
        if(left < j)
        {
                quick_sort(array,left, j);
        }
        if(i < right)
        {
                quick_sort(array, i, right);
        }

这里就是你要的换pivot的地方

sunrise085

在一次函数调用中，pivot没有变过。一直都是传进来的这个区间的中间下标的那个值。
只是每次while循环都拿它作比较而已。
若说右边不安，只有在再一次调用函数的时候，传递进来的参数array和left、right变了，才会用这个pivot = array[(left + right) / 2]重新计算pivot。
也就是在结束第一趟排序开始递归时，调用了quick_sort函数，在递归中修改了pivot。

sunrise085

耻思lhj 发表于 2020-4-16 08:51
1，代码就是在数组中间找一个数，赋值pivot。
2，然后从左到右，左边的数一个一个和pivot比，遇到比pivot ...

你说的4是不对的，不是说“原来pivot的位置左边找不到比pivot大的数，右边找不到比pivot小的数。”
从左边找大于pivot的数，从右边找小于pivot，当左边找到的下标i大于右边找到的下标j的时候（也就是i和j有交叉了）说明第一趟找完了。

你可以看看他给的这个图，在第一趟中8和3互换了呢。8的下标是5，而pivot的下标是4

耻思lhj

sunrise085 发表于 2020-4-16 09:10
你说的4是不对的，不是说“原来pivot的位置左边找不到比pivot大的数，右边找不到比pivot小的数。”
从左 ...

我在上网课，打的有点急，我刚刚发现了改了

冰激凌太烫

耻思lhj 发表于 2020-4-16 08:51
1，代码就是在数组中间找一个数，赋值pivot。
2，然后从左到右，左边的数一个一个和pivot比，遇到比pivot ...

那请问是不是在整个第一次调用函数中，pivot的元素一直不变，即使当array【left/right】 = piovt时，（也就进行元素互换）。pivot还是最开始的值，直到运行到递归？

冰激凌太烫

sunrise085 发表于 2020-4-16 09:04
在一次函数调用中，pivot没有变过。一直都是传进来的这个区间的中间下标的那个值。
只是每次while循环都拿 ...

我自己想通了 感想大佬又一次出手相救

sunrise085

冰激凌太烫 发表于 2020-4-16 09:39
我自己想通了 感想大佬又一次出手相救

那就给六楼一个最佳吧、鼓励新人