快速排序

快速排序使用分治法策略来把一个序列分为较小和较大的2个子序列，然后递归地排序两个子序列。

步骤为：

挑选基准值：从数列中挑出一个元素，称为“基准”（pivot），
分割：重新排序数列，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面（与基准值相等的数可以到任何一边）。在这个分割结束之后，对基准值的排序就已经完成，
递归排序子序列：递归地将小于基准值元素的子序列和大于基准值元素的子序列排序。
递归到最底部的判断条件是数列的大小是零或一，此时该数列显然已经有序。

选取基准值有数种具体方法，此选取方法对排序的时间性能有决定性影响。

通常明显比其他算法更快，因为它的内部循环可以在大部分的架构上很有效率地达成。

JAVA代码实现:

public class QuickSort {
    /*
    算法思路：
        1）从数组中选取一个数字作为分界值
        2）对数组进行遍历，大于分界值的 右边去，小于分界值左边
        3)遍历+递归
     */
    public static void quickSort(int[] arr, int low, int height) {
        // 如果low大于等于high，表示区间内少于两个元素，不需要排序
        if (low < height) {
            // partitioning index，取得划分后的基准元素的位置
            int pivot =partition(arr, low, height);
 
            // 递归排序基准值左边的子数组
            quickSort(arr, low, pivot - 1);
 
            //递归排序基准值右边的子数组
            quickSort(arr, pivot + 1, height);
        }
 
    }
 
    // low和high参数表示当前正在处理的数组段的起始索引(low)和结束索索(high)
    private static int partition(int[] arr, int low, int high) {
        // 选择最后一个元素作为基准值
        int pivot = arr[high];
        // i是小于基准值部分的最后一个元素的索引
        int i = low - 1;
        for (int j = low; j < high; j++) {
            // 比基准值小的元素
            if (arr[j] < pivot) {
                i++;
                // arr[i] 和 arr[j] 交换位置
                changePosition(arr, i, j);
            }
        }
        // 将基凔值换到中间，即大于基准值的元素和小于基准值的元素的分界线
        int temp = arr[i + 1];
        arr[i + 1] = arr[high];
        arr[high] = temp;
        return i + 1; // 返回基准值新的位置
 
    }
 
    public static void changePosition(int[] arr, int left, int right) {
        int temp = arr[left];
        arr[left] = arr[right];
        arr[right] = temp;
    }
 
    // 用于调用的快速排序方法，供外部使用，使得调用者不需要指定数组的起始索引和结束索引
    public static void sort(int[] arr) {
        quickSort(arr, 0, arr.length - 1);
    }
 
    // 主方法，用于测试
    public static void main(String[] args) {
        int[] array = {10, 7, 8, 9, 1, 5};
        sort(array); // 排序数组
 
        // 打印排序后的数组
        for (int value : array) {
            System.out.print(value + " ");
        }
    }
 
}