排序算法之快速排序

快速排序的执行流程:
快速排序和其它排序的执行流程不太一样，我们需要以下几步:

首先从序列中选择一个轴点元素(pivot)

• 假设每次选择0位置的元素为轴点元素，也就是索引为0的元素为轴点元素
  (比如下面这个序列，{6,11,8,2,9,4,1,5,7,10,3}我们选择6这个元素为轴点
  元素，一旦把它定义为轴点元素之后，又怎么做呢？)

然后利用轴点元素pivot将序列分成两个子序列

• 将小于pivot的元素放在pivot的前面(左侧)
• 将大于pivot的元素放在pivot的后面(右侧)
• (也就是说通过这个6把这个序列分隔成两个子序列，如果是等于pivot的元素放在哪一边都行，既然6是我们的轴点元素，它要将我们的序列分成两个子序列，如果是小于6的就放在6的左边，如果是大于6的就放在6的右边，如果是等于6放左放右都可以，如果我们是用6去进行分隔上面的数组会变成:{3,5,1,2 8,7,10,11}
  首先pivot指向的是array[0]。也就是pivot = 6;首先是end–;然后end指向了3。因为array[end]<pivot，所以这个时候3应该换到数组的左边来，
  也就是array[0] = array[end] = 3; 这个时候数组就变成了{3,11,8,2,9,4,1,5,7,10,3}这个时候begin也得begin++ 因为begin必须要指向未进行快排的值然后因为右边的数组放到左边，所以现在交换移动的方向，这个时候比较array[begin]和pivot的值
  因为array[begin]==array[1]=11>pivot，因为这个值比轴点元素大，所以直接交换array[end] = array[begin] = 11这个时候数组就变成了{3,11,8,2,9,4,1,5,7,10,11}。然后交换移动方向 先end-- 然后再比较array[end]和pivot，因为pivot<array[end]=10，所以继续执行end–,继续end向前

最后递归的对子序列进行上面的操作

package com.lut.recursion;

import java.util.Arrays;

public class QuickSort {

    public static void sort(int begin,int end,int [] arr){
        if(end - begin<2) return;
        int mid = pivotIndex(begin,end,arr);
        sort(begin,mid,arr);
        sort(mid+1,end,arr);
    }

    private static int pivotIndex(int begin, int end, int[] arr) {
        int pivot = arr[begin];

        while (end>begin){
            while (end>begin){
                if(pivot>arr[end]){
                    arr[begin++] = arr[end];
                    break;
                }else{
                    end--;
                }
            }

            while (end>begin){
                if(pivot<arr[begin]){
                    arr[end--] = arr[begin];
                    break;
                }else{
                    begin++;
                }
            }
        }
        arr[begin] = pivot;
        return begin;
    }

    public static void main(String[] args) {
        int[] array = {5, 2, 9, 1, 5, 6};
        sort( 0, array.length - 1,array);

        System.out.println("Sorted array: " + Arrays.toString(array));
    }
}