快速排序的基本思想：

         通过一趟排序将待排序记录分割成独立的两部分，其中一部分记录的关键字均比另一部分关键字小，则分别对这两部分继续进行排序，直到整个序列有序

把整个序列看做一个数组，把第零个位置看做中轴，和最后一个比，如果比它小交换，比它大不做任何处理；交换了以后再和小的那端比比它小不交，换，比他大交换。这样循环往复，一趟排序完成，左边就是比中轴小的，右边就是比中轴大的，然后再用分治法，分别对这两个独立的数组进行排序。   

1. public int getMiddle(Integer[] list, int low, int high) {  
   
2.         int tmp = list[low];    //数组的第一个作为中轴  
   
3.         while (low < high) {  
   
4.             while (low < high && list[high] > tmp) {  
   
5.                 high--;  
   
6.             }  
   
7.             list[low] = list[high];   //比中轴小的记录移到低端  
   
8.             while (low < high && list[low] < tmp) {  
   
9.                 low++;  
   
10.             }  
    
11.             list[high] = list[low];   //比中轴大的记录移到高端  
    
12.         }  
    
13.         list[low] = tmp;              //中轴记录到尾  
    
14.         return low;                   //返回中轴的位置  
    
15.     }  

复制代码

递归形式的分治排序算法：

1. public void _quickSort(Integer[] list, int low, int high) {  
   
2.         if (low < high) {  
   
3.             int middle = getMiddle(list, low, high);  //将list数组进行一分为二  
   
4.             _quickSort(list, low, middle - 1);        //对低字表进行递归排序  
   
5.             _quickSort(list, middle + 1, high);       //对高字表进行递归排序  
   
6.         }  
   
7.     }  

复制代码

看了很久，对基本思想有所理解，但其中代码第13行 list[low] = tmp;  //中轴记录到尾  ，这句代码没看懂，什么叫中轴记录到尾，请高手能给详细解释一下……谢谢！！

list[low] = tmp;  
把中间的值赋给list[low] ，已便下次循环时用（因为前面已经把大于tmp放在了高端，小的放在了底端）

int tmp = list[low];    //数组的第一个作为中轴  
        while (low < high) {  
            while (low < high && list[high] > tmp) {  
                high--;  
            }  
            list[low] = list[high];   //比中轴小的记录移到低端  
            while (low < high && list[low] < tmp) {  
                low++;  
            }  
            list[high] = list[low];   //比中轴大的记录移到高端  
        }  
        list[low] = tmp;              //中轴记录到尾  
把标红的这四个拿出来对比一下，楼主看下是不是很眼熟啊？
int test=a
a=b
b=test
和这个玩意是不是很像？其实他们功能确实差不多！设立了一个临时变量作为储存区，然后帮助另外的变量进行位置交换运算。
在这个排序中也是这样的。
int tmp = list[low] 这一句意思是声明了一个变量，将这个数组中第一个元素的值临时存放起来了。这样一来，这个元素所在的位置就变成了一个可以用来使用的空位。
while (low < high && list[high] > tmp) {  
                high--;  
            }  
            list[low] = list[high];   //比中轴小的记录移到低端  
            while (low < high && list[low] < tmp) {  
                low++;  
            }  
            list[high] = list[low];   //比中轴大的记录移到高端  
接下来的这些循环代码，其作用就是对数组中其他元素进行简单的左右分类。
具体来说其进行情况就是这样的：
【空（4）】（1号元素被tmp）储存中【6】【3】【1】【7】【5】【2】【9】tmp=4
然后比较，尾部的9比号4的值要大，所以不动。指针从倒数第一个位置跳到了倒数第二个位置。
倒数第二个元素2，比4小。所以将他存储到最左的第一个位置。数组就变成了
【2】【6】【3】【1】【7】【5】【空（2）】（新的可存数位置。）【9】tmp=4
然后指针又从第一个跳到第二个元素6，这个元素比tmp中存着的4要大，所以要向右放。
【2】【（空）6】【3】【1】【7】【5】【6】【9】tmp=4
然后继续这个过程，倒数第三个元素5比4大，不用考虑，7也是。然后到了1，比4小，要进行换位。
【2】【1】【3】【（空）1】【7】【5】【6】【9】tmp=4
然后3比4要小，不用动了，那么这个数据的简单二分就完成了，最后是不是得把4扔回那个空位中呢？

所以
list[low] = tmp;              //中轴记录到尾  

这一步。
【2】【1】【3】【4】【7】【5】【6】【9】tmp=4这个过程就完成了。接下来会以4为中间，两边的部分继续重复上述排序过程，直到整个数列排序完成。

kuroro自走核炮 发表于 2014-4-18 17:49
int tmp = list[low];    //数组的第一个作为中轴  
        while (low < high) {  
            while (l ...

谢谢大神，弄懂了！！回答的超赞！！:handshake

这样写的递归会死掉。