黑马程序员技术交流社区

标题: 关于交换数组中元素位置的一点问题 [打印本页]

作者: 王桂丽 时间: 2012-8-31 00:07
标题: 关于交换数组中元素位置的一点问题
public class QuickSort {
public void quickSort(String[] strDate,int left,int right){
String middle,tempDate;
int i,j;
i=left;
j=right;
middle=strDate[(i+j)/2];
do{
while(strDate[i].compareTo(middle)<0&& i<right)
i++; //找出左边比中间值大的数
while(strDate[j].compareTo(middle)>0&& j>left)
j--; //找出右边比中间值小的数
if(i<=j){ //将左边大的数和右边小的数进行替换
tempDate=strDate[i];
strDate[i]=strDate[j];
strDate[j]=tempDate;
i++;
j--;
}
}while(i<=j); //当两者交错时停止
if(i<right){
quickSort(strDate,i,right);//从
}
if(j>left){
quickSort(strDate,left,j);
}
}
/**
  * @param args
  */
public static void main(String[] args){
String[] strVoid=new String[]{"11","66","22","0","55","22","0","32"};
QuickSort sort=new QuickSort();
sort.quickSort(strVoid,0,strVoid.length-1);
for(int i=0;i<strVoid.length;i++){
System.out.print(strVoid[i]+" ");
}
}

}

疑问：1、如上代码运行时，结果是正确的如图1
i指向的是left，j指向的是right，如果把left和right替换成i和j后
do{
while(strDate[i].compareTo(middle)<0&& i<j)
i++; //找出左边比中间值大的数
while(strDate[j].compareTo(middle)>0&& j>i)
j--; //找出右边比中间值小的数
结果为 0  0  22 11 22  32  55  66
如图2
2、
再将代码下半部分的如果把left和right替换成i和j后，
运行结果为
0  0 22 66  55  22  11  32
如图3
出现这样的结果是为什么呢？

未命名3.jpg (5.08 KB, 下载次数: 13)

未命名1.jpg (5.88 KB, 下载次数: 16)

未命名2.jpg (5.22 KB, 下载次数: 15)

作者: 王金科 时间: 2012-8-31 02:30
把left和right改为i和j后,判断的条件变了,排除来的结果当然就不一样,建议你画一个图,模拟一下这个过程,就直观的理解了

作者: 蓝迪 时间: 2012-8-31 11:37
本帖最后由蓝迪于 2012-8-31 11:42 编辑

do
{
while(strDate[i].compareTo(middle)<0&& i<j)
i++; //找出左边比中间值大的数
while(strDate[j].compareTo(middle)>0&& j>i)
j--;//找出右边比中间值小的数
if(i<=j){ //将左边大的数和右边小的数进行替换
tempDate=strDate[i];
strDate[i]=strDate[j];
strDate[j]=tempDate;
System.out.println(strDate[i]+" "+strDate[j]);
i++;
j--;
}while(i<=j);

复制代码

问题1将do-while循环中left right 改为 i j的解答
compareTo方法 : 是按照字典顺序比较两个字符串
                     比如 a.compareTo(b); 如果a字符在字典中拍在b的前面,返回-1,如果a等于b,返回0,如果a的位置大于b,返回1
所以流程是这样的,程序开始 middle = 0;
当循环第1次,i=0时 strDate=11 ,strDate.compareTo(middle) (11比0大) 返回的是1 ,所以1<0不成立跳出循环
                     j=7 strDate[j]=32  strDate[j].compareTo(middle) (32比0大) 返回的是1 ,所以1>0 且 j>i(7>0) 成立j--(j=6) 继续循环
                     j=6 strDate[j]=0       strDate[j].compareTo(middle) (0等于0) 返回的是0 ,所以0>0 不成立跳出循环
                     if(i<=j)//(0<6)  成立,strDate(11) 与 strDate[j](0) 互换位置
                     现在数组中的位置是 "0","66","22","0","55","22","11","32"
                     然后就是i++(i=1)  j--(j=5)

循环第2次 i=1 strDate=66 大于 middle (0)  返回的是1 条件不成立
                     j=5 strDate[j]=22 大于 middle (0)  返回的是1 条件成立  j--(j=4) 继续循环
                     j=4 strDate[j]=55 大于 middle (0)  返回的是1 条件成立  j--(j=3) 继续循环
                     j=3 strDate[j]=0       strDate[j].compareTo(middle) (0等于0) 返回的是0 ,所以0>0 不成立跳出循环
                     if(i<=j)//(1<3)  成立,strDate(66) 与 strDate[j](0) 互换位置
                     现在数组中的位置是 "0","0","22","66","55","22","11","32"
                     然后就是i++(i=2)  j--(j=2)

循环第3次  因为还在do中,所以即使角标为3的0 已经跟 66互换了 middle 也还是0
                  i=2 strDate=22 大于 middle (0)  返回的是1 条件不成立
                     j=2 strDate[j]=22 大于 middle (0)  返回的是1 条件成立 j--(j=1) 继续循环
                     j=1 strDate[j]=0       strDate[j].compareTo(middle) (0等于0) 返回的是0 ,所以0>0 不成立跳出循环
                     if(i<=j) //(2<=1) 不成立,位置不变化
                     数组位置仍是 "0","0","22","66","55","22","11","32"
                     因为 i>j 所以跳出do-while

                     if(i<right)
                     {
                              quickSort(strDate,i,right);//从
                     }
                     因为 i < 7 所以条件成立,进行递归把i=2 right=7复制进去
                     然后i=2 j=7 重新循环,以此类推
楼主能推出了吗

作者: 蓝迪 时间: 2012-8-31 11:55
第2个疑问
将下半部分代码中left 和 right 都改为 i 和 j,就变成了这样
if(i<j)//原本是i<right
{
quickSort(strDate,i,j);//原本是quickSort(strDate,i,right);
}
if(j>i)原本是j>left
{
quickSort(strDate,i,j);//原本是quickSort(strDate,left,j);
}

因为do-while结束后
数组中元素位置为"0","0","22","66","55","22","11","32"
而i=2 j=1
都不满足两个if中的条件,所以不进行递归,直接就打印数组
所以结果就是 "0","0","22","66","55","22","11","32"
*/

作者: 王桂丽 时间: 2012-8-31 18:19
此问题已解决

欢迎光临黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2