排序算法---快速排序（Quick Sort）

快速排序和冒泡排序类似，都是基于交换的思想，快速排序对冒泡排序进行了优化，从而更加快速高效（从名字就可以看出应该很牛批...）

---

算法基本思想：

1. 首先选取一个基准值，然后根据这个基准将数组分为了左右两部分
2. 将这左右两个部分中的数据，和基准值做比较，大于基准值的放在右边，小于基准值的放在左边
3. 此时对于基准值而言，已经 “排序 ” 完成，即“比我小的全在我左边，比我大的全在我右边”
4. 然后再对左右两部循环进行同样的操作（递归），最后整个数组的排序就完成了。

示意图

代码实现：

import java.util.Arrays;

/**
 * Created by noonbiteun
 * Date: 2017/7/31
 */
public class QuickSort {
    public static void sort(int[] arr, int left, int right) {
        int base = arr[(left + right) / 2];//基准数
        int lt = left;//左端索引
        int rt = right;//右端索引
        int tmp;//数据暂存，交换时使用
        while (lt < rt) {
            while (arr[lt] < base) {
                //左索引往后移，直到找到不小于base的数才停下来
                lt++;
            }
            while (arr[rt] > base) {
                //右索引往前移，直到找到比不大于base的数才停下来
                rt--;
            }
            if (lt <= rt) {
                //交换此时两个索引所指的数
                tmp = arr[lt];
                arr[lt] = arr[rt];
                arr[rt] = tmp;
                //索引更新
                lt++;
                rt--;
            }
        }
        if (lt == rt) {
            lt++;
            rt--;
        }
        if (left < rt) {
            //递归，排左索引前面的数
            sort(arr, left, --lt);
        }
        if (right > lt) {
            //递归，排右索引后面的数
            sort(arr, ++rt, right);
        }
    }

    public static void main(String[] args) {
        int[] arr = new int[15];
        //初始化数组
        for (int i = 0; i < 15; i++) {
            arr[i] = (int) (Math.random() * (100 + 1));
        }
        System.out.println("排序前数据： "+ Arrays.toString(arr));
        QuickSort.sort(arr, 0, arr.length - 1);
        System.out.println("排序后数据： "+ Arrays.toString(arr));
    }
}

输出结果：

运行结果