在学习编程过程中，会接触很多的排序算法，其中关键字搜索的排序算法中，效率较高是快速排序算法。在参考了很多老师的讲解，查阅了相关的博客后，我对快速排序算法有一些理解，整理后在这里分享给大家，也希望大家能指出不足，给出更为优秀的思想。
=========================分割线===============================
一、基本思想
     一个元素自然有序；局部有序，全局有序。
    快速排序算法采用的是分治策略[sup]1[/sup]，与递归结合，减少了排序过程中的比较次数。
   通过一趟排序，按照某一参考值，将要排序的数据分割为独立的两部分，其中一部分数据比另一部分数据都要小，左边序列数据都要小于右边序列数据。然后再用此方法对两部分数据进行排序，整个过程可以递归进行，直到剩下单个元素，将无序变为有序。[sup]2[/sup]
注1 分治法基本思想
    （1）分解（划分）：将原问题分解为若干个与原问题相似的子问题。
    （2）求解：递归的求解子问题。若子问题的规模足够小，直接求解。
    （3）组合：将每个子问题的解组合成原问题的解。
   
二、 算法的实现步骤
    设需排序的无序区为： A......A[j]
1、基准值的选取
    选择其中的一个值作为基准值pivot。（怎么选择）
2、划分
    通过基准值pivot，将无序区A......A[j]划分为左右两个部分，使左边各元素的值小于pivot，右边各元素的值大于等于pivot。
3、递归求解
    重复（1）、（2）的步骤，分别岁左右两边元素递归的进行快速排序
4、组合
    左右两边分别有序，则整个序列有序。      

三、快速算法过程
    在这里有一篇文章关于快速算法具体的步骤，讲解的通俗易懂，在这里给出链接：http://blog.csdn.net/morewindows/article/details/6684558 《白话经典算法之六 快速算法，快速搞定》

四、基准值的选取
1、基准值是从序列中选取的，但是不同的选择方法对序列的排序效率影响很大
2、设函数：FindPivot() 是求Ai......A[j]的基准值pivot = A[k]的函数，其返回基准元素的下标k.

1. int FindPivot(int i, int j)
   
2. {
   
3.     ......
   
4.     return k ;
   
5. }

复制代码

五、无序区的划分

1. <span style="font-style: normal;"><span style="font-style: normal;">/**
   
2.          * 无序区域的划分，找到划分后区域中基准值所在的位置
   
3.          * @param i 无序区域的最左边下标
   
4.          * @param j 无序区域最右边下标
   
5.          * @param pivot 基准值
   
6.          * @return 划分后基准值所在的位置
   
7.          */
   
8.         private int Partition(int i, int j, int pivot)
   
9.         {
   
10.                 int l;        // 左游标
    
11.                 int r;        // 右游标
    
12.                 do{
    
13.                         for(l = i; arr[l] < pivot; l++);        // 基准值左侧元素均比其小
    
14.                         for(r = j; arr[r] >= pivot; r--);        // 基准值右侧元素均大于等于其
    
15.                         if(l < r)
    
16.                                 swap(arr,l,r);        // 交换左右两侧不满足大小的值
    
17.                 }while(l <= r);        // 当左右游标交叉时，退出
    
18.                
    
19.                 return l;        // 返回分界点处位置
    
20.         }

复制代码

六、快速排序的递归求解

1. /**
   
2.          * 快速排序的递归实现
   
3.          * @param i 需排序区域最左侧位置
   
4.          * @param j 需排序区域最右侧位置
   
5.          */
   
6.         public void QuickSort( int i, int j)
   
7.         {
   
8.                 int pivot;        // 存放基准值       
   
9.                 int selectIndex; // 选择排序前基准值所在位置
   
10.                 int sortIndex;        // 排序后基准值应在位置
    
11.                 selectIndex = FindPivot(i,j);
    
12.                
    
13.                 if(selectIndex != -1)
    
14.                 {
    
15.                         pivot = arr[selectIndex];
    
16.                         //sortIndex = Partition(i,j,pivot);
    
17.                         sortIndex = Partition(selectIndex,j,pivot);        // pivotIndex之前的元素在选择时已经排好序
    
18.                         QuickSort(i, sortIndex-1);
    
19.                         QuickSort(sortIndex, j);               
    
20.                 }
    
21.                
    
22.                 return;
    
23.         }

复制代码

七、快速排序的完整代码
     基准值选取：无序序列中最先找到两个不同元素中较大值

1. package com.itheima;
   
2. 
   
3. /**
   
4. * 快速排序法对数组进行排序
   
5. * @author Fourier
   
6. */
   
7. public class QuickSortDemo {
   
8.         
   
9.         private int[] arr;
   
10.         
    
11.         public QuickSortDemo(int[] arr)
    
12.         {
    
13.                 this.arr = arr;
    
14.         }
    
15.         
    
16.         /**
    
17.          * 基准值的选取。从序列中最先找到两个不同元素中的较大者.
    
18.          * @param arr 待查找数组
    
19.          * @param i 待查找数组开始位置
    
20.          * @param j 待查找数组末尾位置
    
21.          * @return 两个不同元素中的最大者的下标;如果所有元素值相同，则返回-1
    
22.          */
    
23.         private int FindPivot(int i, int j)
    
24.         {
    
25.                 int firstValue = arr[i];
    
26.                 int k = 0;
    
27.                 // 从第i+1个元素开始，向右寻找最近的两个不相等的元素，返回较大值的下标
    
28.                 for(k = i+1; k<= j ; k++)
    
29.                 {
    
30.                         if(arr[k] > firstValue)
    
31.                         {
    
32.                                 return k;
    
33.                         }else if(arr[k] < firstValue)
    
34.                                 return i;
    
35.                 }
    
36.                 // 当序列中所有元素值相同时，返回-1
    
37.                 return -1;
    
38.         }
    
39.         
    
40.         /**
    
41.          * 交换两个元素的值
    
42.          * @param arr
    
43.          * @param i
    
44.          * @param j
    
45.          */
    
46.         private void swap(int[] arr, int i, int j)
    
47.         {
    
48.                 int temp;
    
49.                 temp = arr[i];
    
50.                 arr[i] = arr[j];
    
51.                 arr[j] = temp;
    
52.                
    
53.                 return;
    
54.         }
    
55.         
    
56.         /**
    
57.          * 无序区域的划分，找到划分后区域中基准值所在的位置
    
58.          * @param i 无序区域的最左边下标
    
59.          * @param j 无序区域最右边下标
    
60.          * @param pivot 基准值
    
61.          * @return 划分后基准值所在的位置
    
62.          */
    
63.         private int Partition(int i, int j, int pivot)
    
64.         {
    
65.                 int l;        // 左游标
    
66.                 int r;        // 右游标
    
67.                 do{
    
68.                         for(l = i; arr[l] < pivot; l++);        // 基准值左侧元素均比其小
    
69.                         for(r = j; arr[r] >= pivot; r--);        // 基准值右侧元素均大于等于其
    
70.                         if(l < r)
    
71.                                 swap(arr,l,r);        // 交换左右两侧不满足大小的值
    
72.                 }while(l <= r);        // 当左右游标交叉时，退出
    
73.                
    
74.                 return l;        // 返回分界点处位置
    
75.         }
    
76.         
    
77.         /**
    
78.          * 快速排序的递归实现
    
79.          * @param i 需排序区域最左侧位置
    
80.          * @param j 需排序区域最右侧位置
    
81.          */
    
82.         public void QuickSort( int i, int j)
    
83.         {
    
84.                 int pivot;        // 存放基准值        
    
85.                 int selectIndex; // 选择排序前基准值所在位置
    
86.                 int sortIndex;        // 排序后基准值应在位置
    
87.                 selectIndex = FindPivot(i,j);
    
88.                
    
89.                 if(selectIndex != -1)
    
90.                 {
    
91.                         pivot = arr[selectIndex];
    
92.                         //sortIndex = Partition(i,j,pivot);
    
93.                         sortIndex = Partition(selectIndex,j,pivot);        // pivotIndex之前的元素在选择时已经排好序
    
94.                         QuickSort(i, sortIndex-1);
    
95.                         QuickSort(sortIndex, j);               
    
96.                 }
    
97.                
    
98.                 return;
    
99.         }
    
100.         
     
101.         /**
     
102.          * 显示数组中元素
     
103.          */
     
104.         public void show()
     
105.         {
     
106.                 System.out.print("[");
     
107.                 for(int i = 0; i < arr.length-1; i++)
     
108.                 {
     
109.                         System.out.print(arr[i]+",");
     
110.                 }
     
111.                 System.out.println(arr[arr.length-1]+"]");
     
112.                
     
113.                 return;
     
114.         }
     
115.         
     
116.         public static void main(String[] args) {
     
117.                
     
118.                 int [] arr = {4,4,4,1,7,3,6,9,2,8,6,9,2,3,4,7,2,8};
     
119.                                 
     
120.                 QuickSortDemo qsd = new QuickSortDemo(arr);
     
121.                 System.out.println("==============快速排序前===============");
     
122.                 qsd.show();
     
123.                 qsd.QuickSort(0, arr.length-1);
     
124.                 System.out.println("==============快速排序后===============");
     
125.                 qsd.show();
     
126.                
     
127.                 return;
     
128.         }
     
129. }
     
130.         

复制代码

八。参考资料
       《白话经典算法之六 快速排序 快速搞定》 http://blog.csdn.net/morewindows/article/details/6684558
注2《数据结构与算法》  张岩 哈尔滨工业大学
      《数据结构：思想与实现》  俞勇 上海交通大学
      《快速排序算法 C语言实现》 http://blog.chinaunix.net/uid-26404477-id-3329885.html

楼主理解的好深刻啊！！赞

楼主好厉害

过来学习一下

杨凯瑞 发表于 2015-6-16 07:38
楼主理解的好深刻啊！！赞

也是各位老师的思想，我进行了总结

给点正能量 发表于 2015-6-16 08:43
楼主好厉害

我也是边看必学，还是新手。

meng12 发表于 2015-6-16 09:36
过来学习一下

:handshake互相学习

楼主牛！向你学习！

看你给的链接的那个懂了，可是看你的后，我又懵圈了，你的和那个链接的是一样的吗？感觉你的好复杂~

学习了....................

hellotaomi 发表于 2015-6-16 15:03
看你给的链接的那个懂了，可是看你的后，我又懵圈了，你的和那个链接的是一样的吗？感觉你的好复杂~{:5_289 ...

    基本思想是一样的，基本步骤也是一样的，都是要经过基准值的选取、分割、递归排序的重复进行，直至不能再对无序区分割，也就是分割到单个元素是递归终止条件。
    我这里，基准值选取、分割、递归排序这三步都是在独立的函数中完成的，那么三个函数之间就会多一些参数的传递。而在连接中，是整合到一个函数中，省略了中间的传递参数。而且在链接的代码里，不容易观察出递归终止条件，它里面是（l >= r）为递归结束条件，但是同时在内部进行左右数据分割互换时候，也是用的（l >= r）作为此次数据呼互换的完成条件，两者会很容易混淆。我特意把两者判断条件进行了分离，这样就更容易了解什么时候可以交换数据，什么时候结束递归。
    在链接中的代码块里，还有一点小问题，就是进行数据互换时候，会出现左右游标不同步的问题，你可以自己分析，试着找出来并改正。

水壶vs兔子 发表于 2015-6-16 11:21
楼主牛！向你学习！

我也是新手，多多互相学习

hellotaomi 发表于 2015-6-16 15:03
看你给的链接的那个懂了，可是看你的后，我又懵圈了，你的和那个链接的是一样的吗？感觉你的好复杂~{:5_289 ...

我是指链接的里面的代码有些问题，即白话算法里面作者给出的代码。我给出的代码还可以继续优化。

感谢分享！！

学习一下  

原来排序算法还有这么多，我刚开始接触没多久，想要先加入基础班，看来还得努力呀

感谢楼主分享

我是隔壁老王呀 发表于 2015-6-16 16:53
基本思想是一样的，基本步骤也是一样的，都是要经过基准值的选取、分割、递归排序的重复进行，直至不 ...

哈哈，还是很谢谢楼主的分享，根据你的分享我最后也自己做出来了，谢谢啦

给楼主赞个

学习了