C语言第36讲-快速排序 求助
#include <stdio.h>void quick_sort(int array[],intleft,int right);
void quick_sort(int array[], intleft, int right)
{
int i = left, j = right;
int temp;
int pivot;
pivot = array[(left + right) / 2];
while (i <= j)
{
//从左到右找到大于等于基准点的数
while (array < pivot)
{
i++;
}
//从右到左找到小于等于基准点的数
while (array > pivot)
{
j--;
}
//如果i <= j，则互换元素
if (i <= j) //为什么在这一步i，j互换元素后，pivot就会向前移动一位，成为新的pivot？是因为i++和j--嘛？？（有附图）还望各路大神指点一二
{
temp = array;
array = array;
array = 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);
quick_sort(array, 0, length - 1);
printf("排序后的结果是:");
for (i = 0; i < length; i++)
{
printf("%d",array);
putchar(' ');
}
return 0;
} 本帖最后由 耻思lhj 于 2020-4-16 08:43 编辑
pivot并没有移动，他只是被用来比较而已
他仅仅只是个值而已
互换之后并不会换pivot，只有在j>i也就是下面重新调用的时候会重置pivot 耻思lhj 发表于 2020-4-16 08:37
pivot并没有移动，他只是被用来比较而已
他仅仅只是个值而已
那是在哪行代码进行比较的？ 冰激凌太烫 发表于 2020-4-16 08:38
那是在哪行代码进行比较的？
while（）里面比较的 耻思lhj 发表于 2020-4-16 08:44
while（）里面比较的
但还是没有说pivot会改变的啊，它只是在while循环比较找到基准点，然后再left和right元素互换，不太理解哪行代码把pivot 的元素改变了的 本帖最后由 耻思lhj 于 2020-4-16 09:17 编辑
1，代码就是在数组中间找一个数，赋值pivot。
2，然后从左到右，左边的数一个一个和pivot比，遇到比pivot大的数就停下来，叫a吧。然后执行下面。
3，另一边从右到左，右边的数一个一个与pivot比，遇到比pivot小的数就停下来，与之前上面的数a交换。
4，换完就继续第2步，直到j>i，在这个i和j交叉的位置的左边找不到比pivot大的数，右边找不到比pivot小的数。
然后就分成了两个部分了(一个是都小于pivot的部分，一个是都大于pivot的部分)，在这两个部分里分别调用quick_sort，第一部分又从中间取个值赋值给pivot，第二部分也从中间取个值赋值给pivot（调用了两次函数）。 冰激凌太烫 发表于 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的地方 在一次函数调用中，pivot没有变过。一直都是传进来的这个区间的中间下标的那个值。
只是每次while循环都拿它作比较而已。
若说右边不安，只有在再一次调用函数的时候，传递进来的参数array和left、right变了，才会用这个pivot = array[(left + right) / 2]重新计算pivot。
也就是在结束第一趟排序开始递归时，调用了quick_sort函数，在递归中修改了pivot。 耻思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 sunrise085 发表于 2020-4-16 09:10
你说的4是不对的，不是说“原来pivot的位置左边找不到比pivot大的数，右边找不到比pivot小的数。”
从左 ...
我在上网课，打的有点急，我刚刚发现了改了{:5_109:} 耻思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循环都拿 ...
{:10_298:} 我自己想通了 感想大佬又一次出手相救 冰激凌太烫 发表于 2020-4-16 09:39
我自己想通了 感想大佬又一次出手相救
那就给六楼一个最佳吧、鼓励新人
页:
[1]