快速排序

1. 算法思想
快排是基于分治的思想。首先找一个基准值(一般取待排序列的第一个)，然后通过操作把小于等于基准值的元素放到左边(以升序为例);大于等于基准值的元素放到右边。那 么如何进行操作? 首先用指示标志标记首尾两个元素，后面的标记点先从后向前遍历，如果标记点的元素大于等于基准值，那么标记点前移;如果小于就把两个标记点的元素互换位置。前面的标记点从前向后遍历，如果标记点的元素小于等于基准值，标记点就后移;如果大于就把两个标记点的元素换位置。最后两个标记点会重合，排序结束。
  以下面的例子进行说明:(表格较多，偷个懒，把原来整理的截图了QAQ)

快速排序.jpg

2. 算法实现

import java.util.Arrays;

/**
 * @Author: 落脚丶
 * @Date: 2017/10/17
 * @Time: 下午4:12
 */
public class QuickSort {

    public static void main(String[] args) {
        int[] a = new int[]{20,3,5,1,22,15,45,21,19,7,8,15};
        sort(a,0,a.length - 1);
        System.out.println(Arrays.toString(a));
    }
    /**
    * @Date: 2017/10/17
    * @Time: 下午5:12
    * @Method: partition
    * @Return: 一趟排序后，基准点的位置
    * @Description:
     * 对数组进行一次排序，把小于等于基本点元素放到基准点左边，
     * 大于等于基准点的元素放到基准点右边。并返回基准点的索引。
    */
    public static int partition(int []array,int low,int high){
        int key = array[low];
        while (low < high) {
            // 从后向前遍历
            while (array[high] >= key && high > low) {
                high--;
            }
            swap(array, low, high);
            // 从前向后遍历
            while (array[low] <= key && high > low)
            {
                low++;
            }
            swap(array, low, high);
        }
        return high;
    }
    public static void sort(int[] array,int low ,int high){
        if(low>=high){
            return ;
        }
        int index=partition(array,low,high);
        sort(array,low,index-1);
        sort(array,index+1,high);
    }
    /**
    * @Date: 2017/10/17
    * @Time: 下午5:12
    * @Method: swap
    * @Description: 交换两个数组的元素
    */
    public static void swap(int[]a, int b, int c) {
        int tem = a[b];
        a[b] = a[c];
        a[c] = tem;
    }
}

3. 算法复杂度

• 最好情况：O(nlogn)
• 最坏情况：O(n²)
• 平均情况：O(nlogn)