前言

相信很多搞计算机的朋友都听说过一句话：

程序=数据结构+算法

自己的一些体会是，其实出来工作之后，很少会用到太复杂的算法，基本上都是业务逻辑的编写为主。 退一万步来讲，即使有用到，也有相应的工具库帮你实现好，非常方便^_^。 所以，算法这些东西，通常是学了又忘，忘了又学。

算法虽然不会用到，或者说，不用自己实现。但是了解其原理，还是对我们解决问题有帮助，也是编程能力的一种素养吧。

快速排序思路

开篇，先来一发狠的，说说快速排序。 这个是各种排序算法当中，比较常用的吧。看名字就知道它很牛？快速排序，意思就是它的速度非常快，时间复杂度是O(nlogn)。

下面我们一起看看它的算法过程:

0.有一个乱序数组arr 1.选择arr第一个元素arr[0],作为基准元素x，并在数组的头尾设置两个指针i, j 2.首先看j, j不断往前移动(j--), 直到找到第一个比x小的元素，交换i和j的位置，i向后移动(i++) 3.然后，再看i,i不断往后移动(i++), 直到找到第一个比x大的元素，交换i和j的位置，j向前移动(j--) 4.重复2和3，直到i和j重合(i == j) 5.此时，i的位置就是基准元素x的位置了 6.然后，再将i的前后两部分，再执行一次1,2,3,4,5的流程。直到不能再执行

例子

下面我们用一个例子，来看看一趟快排的执行过程

我们假设，有数组 a = [27, 31, 15, 28, 43, 15, 04]

然后，只要把i前面，和j后面的两组元素，分别再执行快速排序流程，直到不能再执行(i > j)，此时数组a就是一个有序数组了。

从上面的过程，我们可以发现，快速排序，使用了分治法的思想，分而治之。把一个数组分成两部分，再分别进行排序。

实现

有同学要喷了？你bibi了这么多？代码写了多少？ Ok. Talk is cheap, Show me the Code.

附上java版代码实现

public static void qsort(int[] a, int l, int r){
    if(l >= r){
        return;
    }

    int x = a[l];
    int i = l;
    int j = r;

    while(i < j){
        while(i < j && a[j] >= x){
            j--;
        }
        if(i < j){
            a[i++] = a[j];
        }

        while(i < j && a[i] <= x){
            i++;
        }
        if(i < j){
            a[j--] = a[i];
        }
    }

    a[i] = x;

    if(l < i - 1){
        qsort(a, l, i - 1);
    }
    if(j + 1 < r){
        qsort(a, j + 1, r);
    }
}