快速排序原理：分治法，快速排序在每一轮挑选一个基准元素，比它大的在一边，比它小的在另一变，拆解成两部分。双边循环法和单边循环法实现。

    1. package com.algorithm.sort;
    3. import java.util.Arrays;
    5. /**
    6.  * 快速排序原理：分治法，快速排序也属于交换排序，快速排序在每一轮挑选一个基准元素，并让其他比它大的元素移动到数列一边，比它小的元素移动到数列
    7.  * 的另一边，从而把数列拆解成两个部分。基准元素、比基准元素大的元素、比基准元素小的元素 这种思路叫分治法
    8.  * <p>
    9.  * 双边循环法：left 和 right 左右两个指针分别指向数列的最左和最右，从right指针开始>=基准元素 向左移动，< 基准元素right停止移动 进行数据交换，
    10.  * 切换到left指针，如果 <= 基准元素 left指针向右移动，否则left指针停止移动 进行数据交换。
    11.  * 如果left和right 两个指针重合则将该位置的数据和基准元素进行交换。 实现了左右两侧 分治
    12.  */
    13. public class FastSort {
    14.     public static void main(String[] args) {
    15.         int[] arr = new int[]{4, 4, 6, 5, 3, 2, 8, 1};
    16.         FastSort.quickSort(arr, 0, arr.length - 1);
    17.         System.out.println(Arrays.toString(arr));
    18.     }
    20.     /**
    21.      * 单边循环分治法
    22.      * 1. 选定基准元素
    23.      * 2. mark 指针表示小于基准元素的区域边界
    24.      * 如果遍历的元素大于基准元素，继续向后遍历。
    25.      * 如果遍历的元素小于基准元素，把mark指针右移动一位，因为小于基准元素的区域增大了；遍历到的元素和mark指针所在的位置进行交换，遍历到的元素
    26.      * 归属于小于基准元素的区域。
    27.      * 最后将基准元素和mark指针所在的位置进行交换，实现了分治
    28.      *
    29.      * @param arr
    30.      * @param startIndex
    31.      * @param endIndex
    32.      */
    33.     private static int partition2(int[] arr, int startIndex, int endIndex) {
    34.         int pivot = arr[startIndex];
    35.         int mark = startIndex;
    36.         for (int i = startIndex + 1; i <= endIndex; i++) {
    37.             if (arr[i] < pivot){
    38.                 mark++;
    39.                 int temp = arr[mark];
    40.                 arr[mark] = arr[i];
    41.                 arr[i] = temp;
    42.             }
    43.         }
    44.         //基准元素和mark位置交换
    45.         arr[startIndex] = arr[mark];
    46.         arr[mark] = pivot;
    47.         return mark;
    48.     }
    50.     public static void quickSort(int[] arr, int startIndex, int endIndex) {
    51.         if (startIndex >= endIndex) return;
    52.         //得到基准元素的位置
    53.         int pivotIndex = partition2(arr, startIndex, endIndex);
    54.         //根据基准元素分成两部分进行递归排序
    55.         //小于基准元素的 进行分治排序
    56.         quickSort(arr, startIndex, pivotIndex - 1);
    58.         //大于基准元素的 进行分治排序
    59.         quickSort(arr, pivotIndex + 1, endIndex);
    60.     }
    62.     /**
    63.      * 分治：双边循环法
    64.      *
    65.      * @param arr
    66.      * @param startIndex
    67.      * @param endIndex
    68.      * @return
    69.      */
    70.     private static int partition(int[] arr, int startIndex, int endIndex) {
    71.         int pivot = arr[startIndex];
    72.         int left = startIndex;
    73.         int right = endIndex;
    74.         while (left != right) {
    75.             //控制right指针比较并左移动
    76.             while (left < right && arr[right] > pivot) {
    77.                 right--;
    78.             }
    79.             while (left < right && arr[left] <= pivot) {
    80.                 left++;
    81.             }
    82.             //交换元素
    83.             if (left < right) {
    84.                 int p = arr[left];
    85.                 arr[left] = arr[right];
    86.                 arr[right] = p;
    87.             }
    88.         }
    89.         //指针发生重合
    90.         arr[startIndex] = arr[left];
    91.         arr[left] = pivot;
    92.         //一轮循环结束 返回基准元素的位置
    93.         return left;
    94.     }
    95. }