快速排序求解。解决思路

2013-11-03

快速排序求解。。变成菜鸟，看不懂一段精妙的排序，求各路大神指点，解释。。void QSort( int l, int r, int b[]

快速排序求解。。
变成菜鸟，看不懂一段精妙的排序，求各路大神指点，解释。。

void QSort( int l, int r, int b[] ){
     int i= l, j= r, x= b[i];
     if( l>= r ) return;
      while( i!= j ){
         while( b[j]>x && j>i )    j--;
         if( i< j )    b[i++]= b[j];  // 这里为什么这样？主要是这里想不明白，为什么没有交换呢？
         while( b[i]<x && j>i )    i++;
             if( i< j )    b[j--]=b[i];
     }
     b[i]= x;
     QSort(l,j-1,b);
     QSort(i+1,r,b);
}

[解决办法]

引用:

变成菜鸟，看不懂一段精妙的排序，求各路大神指点，解释。。

void QSort( int l, int r, int b[] ){
     int i= l, j= r, x= b[i];
     if( l>= r ) return;
      while( i!= j ){
         while( b[j]>x && j>i )    j--;
         if( i< j )    b[i++]= b[j];  // 这里为什么这样？主要是这里想不明白，为什么没有交换呢？
         while( b[i]<x && j>i )    i++;
             if( i< j )    b[j--]=b[i];
     }
     b[i]= x;
     QSort(l,j-1,b);
     QSort(i+1,r,b);
}

因为他把排列好的数据放到了b[i++]里面，然后下面的循环b[j--]把数据倒腾回来。所以你看不到交换，就是因为交换在两次while中完成。
[解决办法]

引用:

变成菜鸟，看不懂一段精妙的排序，求各路大神指点，解释。。

void QSort( int l, int r, int b[] ){
     int i= l, j= r, x= b[i];
     if( l>= r ) return;
      while( i!= j ){
         while( b[j]>x && j>i )    j--;
         if( i< j )    b[i++]= b[j];  // 这里为什么这样？主要是这里想不明白，为什么没有交换呢？
         while( b[i]<x && j>i )    i++;
             if( i< j )    b[j--]=b[i];
     }
     b[i]= x;
     QSort(l,j-1,b);
     QSort(i+1,r,b);
}

我给你加了个颜色
[解决办法]
你看的这个是那本黄色的复旦出的数据结构吧，当年我的教材也是这本。快速排序有个很简洁的概括：左右开攻。那句话实际就是把左边的元素放到右边这次遍历它应该放到的地方。
[解决办法]
b[i] 存储到了x，不需要交换
[解决办法]
举个例子，滑块拼图知道吧，比如9块拼图放在一个框内，让你通过移动把拼图还原。开始先取出一块，这样多出了一个位置，然后就可以对剩下的拼图移动调整了，等你还原了，最后再把这个移出来的拼图放回去。

这道题其实和这拼图的原理差不多。b[i]就是那个空出来的位置，直接覆盖掉就好了，不需要交换。你一定要交换应该也可以。
[解决办法]
“给定一个小点的输入，完整单步跟踪(同时按Alt+7键查看Call Stack里面从上到下列出的对应从里层到外层的函数调用历史)一遍。”是理解递归函数工作原理的不二法门！
递归函数关注以下几个因素
·退出条件
·参数有哪些
·返回值是什么
·局部变量有哪些
·全局变量有哪些
·何时输出
·会不会导致堆栈溢出

热点排行

C++

快速排序 求解。解决思路

快速排序求解。解决思路