快速排序

基本思想

• 先从数列中取出一个数作为基准数。
• 分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。
• 再对左右区间重复第二步，直到各区间只有一个数。

实现原理

• 选择最左侧元素为基准数pivot，并记录
• 设置两个变量l和r分别指向头尾元素
• 从后向前搜索，直至找到比pivot小的数字，记录当时r值，并将该元素替换到pivot
• 从前向后搜索，直至找到比pivot大的数字，记录当前l值，并将该原子替换到下标为r的位置
• 当l==r时，将pivot赋值到此位置

代码实现

public class Quick_Sort {

    public static void quick_sort(int[] array,int left,int right){
        if (array==null||array.length<=0){
            return;
        }
        if (left<right){
            int l = left;
            int r = right;
            int pivot = array[left];
            while (l<r){
                while(l<r && array[r]>=pivot){
                    r--;
                }
                if (l<r){
                    array[l++]=array[r];
                }
                while (l<r && array[l]<pivot){
                    l++;
                }
                if (l<r) {
                    array[r--] = array[l];
                }
            }
            array[l] = pivot;
            quick_sort(array, left, l-1);
            quick_sort(array, l+1, right);
        }
    }

    public static void main(String[] args) {
        int[] array = {3,44,38,5,47,15,36,26,27,2,46,4,19,50,48};

        quick_sort(array,0,array.length-1);
        System.out.println(Arrays.toString(array));
    }
}