排序算法复习之一趟快速排序算法：为什么说关键字所占的位置是多余的

思路：

         49  38   65  97 76 13 27

先说自己的想法：

 

首先看38，发现38比49小，所以换位：

 

        38 49 65  97 76 13 27 

 

这个时候发现65，按理说应该把65放最后面，或者说与27交换位置，变为：

 

        38  49 27 97 76 13 65

 

这个时候，发现27，27比49小，所以交换位置为：

 

       38 27 49  97 76 13 65

 

这个时候发现97，我们换97与后面比49小的。

 

       38  27 49 13 76 97 65

这个时候发现13，我们换：

 

        38 27 13 49 76 97 65

 

后面没有比49 小的了。终止。

 

我们发现：

         每次我们总是从前面找一个比49大的，，从后面找一个比49小的，然后调换他们的位置。

         

         我们发现：这个49所占的位置，是多余的，这个位置可以用来进行交换高低位：

 

再次变为如下过程：

 

        49 38 65 97 76 13 27

 

先从后往前找：

 

        找到一个27，比49 小，序列变为：

 

        27 38 65 97 76 13 27

 

然后从前往后找：

 

       找到一个65，比49大，这个时候把最后一个变为65：

 

       27 38 65 97 76 13 65

 

关键之处就在于：黄色字所表示的地方正是原来49所占的位置。

 

再从后往前找。。再找一个比49小的，那就是13：

 

      变为：

 

         27 38 13 97 76 13 65

 

再从前往后找：

 

         找到97比49大，那么，变为：

 

         27 38 13 97 76 97 65

 

再从后往前找，一直找到橙色97为止：也就是low的指向：

 

直到 low=high

       这就是快速排序一趟，这个时候我们将橙色97置为49，函数返回它的位置作为分割点。设为partitio

 

(low,partition-1) 和 (partition,high)两个区间。