快速排序的些许总结(JAVA)

前言

---

最近不太忙，有空oj上刷刷水题，遇到几道排序题目，鄙人习惯用java语言，也深知很多直接用java封装好的sort函数能够直接解决问题。但所谓饮水思源，项目之外，还是应该多多关注众多排序算法的内部细节。就先总结平均效率最高的快速排序算法吧。

特点

---

平均效率最高，但不稳定。平均时间复杂度o(nlogn),最坏时间复杂度o(n^2)。

思路（升序）

---

快速排序基于比较和分治，核心是先让一个元素找准其位置，使其左边的元素都不比它大，右边的元素都不比它小。然后再使其左边集合和右边集合都递归下去，直到最终有序。

方法

---

1. 选取一个基准（参照物），默认选择第一个元素（当然选择其他元素也可以）。并确定两个游标，左游标和右游标。
2. 右游标从右到左扫描，若发现一个小于基准的元素，停止扫描，将该元素赋值到基准位置，同时新的基准位置调整到该元素原来位置。倘若没发现，则当左右游标重合时停止扫描。
3. 左游标从左向右扫描，若发现一个大于基准的元素，停止扫描，将该元素赋值到基准位置，同时新的基准位置调整到该元素原来位置。倘若没发现，则当左右游标重合时停止扫描。
4. 2和3一直进行，直到左右游标重合，即基准已找到其位置，将基准值赋值到游标重合位置。
5. 虽然已经确定了基准的位置，但总体来看并不一定是有序的，则还需要对其左边集合和右边集合分别进行排序，使用递归即可。

例子

---

代码实现

public static void quickSort(int a[],int l, int r) {
        if(l < r) {
            int s = a[l]; //基准
            int i = l; //左游标
            int j = r; //右游标
            while(i < j) {
                //从右向左扫描，当左右游标重合或者扫描到小于基准的值时扫描停止
                while(i < j && a[j] > s) {
                    j--;
                }
                //将小于基准的值赋值到基准位，右游标位置为新的基准位
                a[i] = a[j];
                //从左向右扫描，当左右游标重合或者扫描到大于基准的值时扫描停止
                while(i < j && a[i] < s) {
                    i++;
                }
                //将大于基准的值赋值到基准位，左游标位置为新的基准位
                a[j] = a[i];
            }
            //左右游标重合，基准值的最终位确定
            a[j] = s;
            //对左边部分递归
            quickSort(a,l,i-1);
            //对右边部分递归
            quickSort(a,j+1,r);
        }
    }

这是升序的实现，如要排成降序，可在扫描时改变判断方向，即从右到左找大于基准的，从左到右找小于基准的。很容易实现，这里就不多说了。

结语

根据快速排序的算法可以知道，快速排序并非在任何情况都是最优的，比如说当集合是有序的时候，基准选到了最大或者最小的元素，这样每次只能定一个元素的位置，就等于冒泡排序了，时间复杂度变成了o(n^2)。不过绝大数情形，快速排序是优于其他排序的。