今天复习了一下快排，感觉还是挺多收货的.

快排的思想

快速排序是C.R.A.Hoare于1962年提出的一种划分交换排序。它采用了一种分治的策略，通常称其为分治法(Divide-and-ConquerMethod)。

该方法的基本思想是：

1．先从数列中取出一个数作为基准数pivot。

2．分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。

3．再对左右区间重复第二步，直到各区间只有一个数。

解法

根据以上的介绍，我写了最基础的快排（升序），即用最左边的元素作为pivot。在oj上过不了。

private static void quicksortbasic(int[] put, int left, int right){
    if(put == null || put.length < 2 || left >= right)return;
    int i = left, j = right;
    int pivot = put[left];
    while(i != j)
    {	
        //从右往左，找到比pivot小的第一个元素
        while(i < j && put[j] >= pivot){
            j--;
        }
        //从左往右，找到比pivot大的第一个元素
        while(i < j && put[i] <= pivot){
            i++;
        }
        //如果存在这样的两个元素，则交换
        if(i < j){
            swap(put,i,j);
            i++;
            j--;
        }
    }
    //最后交换left和结束处的位置,即有几个比left小的
    swap(put,left,i);
    quicksortbasic(put, left, i - 1);
    quicksortbasic(put, i + 1, right);
}

挖坑法：

private static void wakengfa(int[] put, int left, int right){
        if(put == null || put.length < 2 || left >= right)return;
        int i = left, j = right;
    	//如果想用中间的点作为pivot
    	//swap(put,(left+right)/2,left);
    	//对left处挖坑
        int pivot = put[left];
        while(i < j){
            //从右往左，找到比pivot小的第一个元素
            while(i < j && put[j] >= pivot){
                j--;
            }
            //如果有这样的j，则用新找到的j填坑
            if(i < j){
                put[i] = put[j];
                i++;
            }
            //从左往右，找到比pivot大的第一个元素
            while(i < j && put[i] <= pivot){
                i++;
            }
            //如果有这样的i，则填上j的坑
            if(i < j){
                put[j] = put[i];
                j--;
            }
        }
    	//最后有i个比pivot小的元素。在put[i]处加入pivot      
        put[i] = pivot;
        wakengfa(put, left, i - 1);
        wakengfa(put, i + 1, right);
    }

对挖坑填数进行总结

1．i =L; j = R; 将基准数挖出形成第一个坑a[i]。

2．j—由后向前找比它小的数，找到后挖出此数填前一个坑a[i]中。

3．i++由前向后找比它大的数，找到后也挖出此数填到前一个坑a[j]中。

4．再重复执行2，3二步，直到i==j，将基准数填入a[i]中。

在挖坑法中，考虑到已经排序好的逆序数组（降序数组）会造成递归栈溢出的可能

{9，8，7，6，5，4，3，2，1，0}

第一次“填坑” 会变成 {0，8，7，6，5，4，3，2，1，0}

第一次结束：{0，8，7，6，5，4，3，2，1，9}

递归开始：

{0，8，7，6，5，4，3，2，1} {9}

可以想见当数组长度很长的时候，是有可能会溢出的。因此一般会选择中间点或者是中位数作为pivot，保证递归两边数量差不多，效率最高。

别的版本

附上快排另一个版本，和挖坑法类似，但是比挖坑法难理解.

private static void quicksortmiddle(int[] put, int left, int right){
     if(right <= left) return;
     int i = left, j = right;
     int pivot = put[(right +left)/2];
     while(i <= j)
     {
         while(i <= j && put[i] < pivot){
             i++;
         }
         while(i <= j && put[j] > pivot){
             j--;
         }
         if(i <= j){
             swap(put,i++,j--);
         }
     }
    quicksortmiddle(put, left, j);
    quicksortmiddle(put, i, right);
}

附上swap和调用代码

public static void quickSortenter(int[] put){
        wakengfa(put,0,put.length - 1);
    }
public static void swap(int[] input, int a, int b){
        int temp = input[a];
        input[a] = input[b];
        input[b] = temp;
    }

Main函数

int a[] = {3,2,1,4,5,6};
        int b[] = {};
        quickSortenter(a);
        selectSort(b);
        for (int element:
             a) {
            System.out.print(element + " ");
        }

reference：

https://blog.csdn.net/morewindows/article/details/6684558

测试oj：

http://www.lintcode.com/zh-cn/problem/sort-integers-ii/#

你好

quick sort

快排的思想

解法

挖坑法：

别的版本