快速排序算法的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

1.算法步骤 该方法的基本思想是：

1．先从数列中取出一个数作为基准数（一般是数组的第一个元素）。 2．分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。 3．再对左右区间重复第二步，直到各区间只有一个数。

以一个数组作为示例，取区间第一个数为基准数。

初始时，i = 0; j = 9; X = a[i] = 72

由于已经将 a[0] 中的数保存到 X 中，可以理解成在数组 a[0] 上挖了个坑，可以将其它数据填充到这来。

从j开始向前找一个比X小或等于X的数。当j=8，符合条件，将a[8]挖出再填到上一个坑a[0]中。a[0]=a[8]; i++; 这样一个坑a[0]就被搞定了，但又形成了一个新坑a[8]，这怎么办了？简单，再找数字来填a[8]这个坑。这次从i开始向后找一个大于X的数，当i=3，符合条件，将a[3]挖出再填到上一个坑中a[8]=a[3]; j--;

数组变为：

i = 3; j = 7; X=72 再重复上面的步骤，先从后向前找，再从前向后找。

从j开始向前找，当j=5，符合条件，将a[5]挖出填到上一个坑中，a[3] = a[5]; i++;

从i开始向后找，当i=5时，由于i==j退出。

此时，i = j = 5，而a[5]刚好又是上次挖的坑，因此将X填入a[5]。

数组变为：

可以看出a[5]前面的数字都小于它，a[5]后面的数字都大于它。因此再对a[0…4]和a[6…9]这二个子区间重复上述步骤就可以了。

2.代码实现

public static void quickSort(int[] arr, int leftIndex, int rightIndex){
    int i, j;  //寻迹节点
    int pivot; //基准数
    int temp; //用于交换的中间变量 
    if(leftIndex >= rightIndex)
        return;
    pivot = arr[leftIndex];
    i = leftIndex;
    j = rightIndex;
    while (i != j){
        while (arr[j] >= pivot && i < j)
        j--;
        while (arr[i] <= pivot && i < j)
        i++;

        if(i < j){
        temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
        }
    }
    //将基准数归位
    arr[leftIndex] = arr[i];
    arr[i] = pivot;
    //一分为二，进行递归
    quickSort(arr, leftIndex, i - 1);
    quickSort(arr, i + 1, rightIndex);

}

public static void main(String[] args) {
    int[] arr = {12,8,8,34,56,10,2,77,33};

    quickSort(arr,0,arr.length-1);

    for(int n:arr){
        System.out.print(n+"  ");
    }
}

3.小结 快速排序由于排序效率在同为O(N*logN)的几种排序方法中效率较高，因此经常被采用，再加上快速排序思想----分治法也确实实用，因此很多软件公司的笔试面试，包括像腾讯，微软等知名IT公司都喜欢考这个，还有大大小的程序方面的考试如软考，考研中也常常出现快速排序的身影。