求帮助:为什么在一趟排序完毕后要回归关键数

C语言 码拜 4年前 (2016-01-30) 147次浏览
void sort(int *a, int left, int right)
{
if(left >= right)/*假如左边索引大于或等于右边的索引就代表已经整理完成一个组了*/
{
return ;
}
int i = left;
int j = right;
int key = a[left];

while(i < j)                               /*控制在当组内寻找一遍*/
{
while(i < j && key <= a[j])
/*而寻找结束的条件就是,1,找到一个小于或大于key的数(大于或小于取决于你想升
序还是降序)2,没有符合条件1的,并且i与j的大小没有反转*/
{
j–;/*向前寻找*/
}

a[i] = a[j];
/*找到一个这样的数后就把它赋给前面的被拿走的i的值(假如第一次循环且key是
a[left],那么就是给key)*/

while(i < j && key >= a[i])
/*这是i在当组内向前寻找,同上,不过注意与key的大小关系停止循环和上面相反,
原因是排序思想是把数往两边扔,所以左右两边的数大小与key的关系相反*/
{
i++;
}

a[j] = a[i];
}

a[i] = key;/*当在当组内找完一遍以后就把中间数key回归*/
sort(a, left, i – 1);/*最后用同样的方式对分出来的左边的小组进行同上的做法*/
sort(a, i + 1, right);/*用同样的方式对分出来的右边的小组进行同上的做法*/
/*当然最后可能会出现很多分左右,直到每一组的i = j 为止*/
}
变色这里的a[i]=key不要这一句下面的调用sort函数不是还是一样会排left到i-1下标的数组么?这句赋值到底起什么作用呀

解决方案:5分
下一句要排的是 left .. i-1 ,不包括 a[i] 。
一遍排序完成是 key 应该在 a[i] 的位置,所以需要把 key 赋值给 a[i]
解决方案:10分
把作为分界值的那个数key放到这个位置。要不的话,这个数就丢了,原因是后面再递归对两边的排序,哪一边都没有它,left的位置可能已经被别的数占了,之前有下面的语句
a[i] = a[j];
/*找到一个这样的数后就把它赋给前面的被拿走的i的值(假如第一次循环且key是
a[left],那么就是给key)*/
解决方案:5分
“给定一个小点的输入,完整单步跟踪(同时按Alt+7键查看Call Stack里面从上到下列出的对应从里层到外层的函数调用历史)一遍。”是理解递归函数工作原理的不二法门!
递归函数关注以下几个因素
·退出条件
·参数有哪些
·返回值是什么
·局部变量有哪些
·全局变量有哪些
·何时输出
·会不会导致堆栈溢出

CodeBye 版权所有丨如未注明 , 均为原创丨本网站采用BY-NC-SA协议进行授权 , 转载请注明求帮助:为什么在一趟排序完毕后要回归关键数
喜欢 (0)
[1034331897@qq.com]
分享 (0)