1. package io.github.chenshun00.web.sort;
    3. import java.util.Arrays;
    5. /**
    6.  * @author luobo.cs@raycloud.com
    7.  * @since 2021/8/12 7:09 下午
    8.  */
    9. public class QuickSort {
    11.     public static void main(String[] args) {
    12. //        int[] array = {1, 300, 29, 490, 961, 23, 47, 50, 234, 56, 23, 56, 678, 43, 672, 356, 35, 2, 994, 67, 98, 9, 345, 76, 345, 234, 4, 2, 645, 6, 235, 3, 563};
    13.         int[] array = {100, 9, 190, 361, 2, 7, 5};
    14.         sort(array);
    15.         System.out.println(Arrays.toString(array));
    16.     }
    18.     public static void sort(int[] sourceArray) {
    19.         quickSort(sourceArray, 0, sourceArray.length - 1);
    20.     }
    22.     private static void quickSort(int[] arr, int left, int right) {
    23.         if (right > left) {
    24.             //找到临界点
    25.             int lingJieDian = find(arr, left, right);
    26.             quickSort(arr, left, lingJieDian - 1);
    27.             quickSort(arr, lingJieDian + 1, right);
    28.         }
    29.     }
    31.     /**
    32.      * 目标: 找到中间点
    33.      * <p>
    34.      * 1、明确开始位置(begin)、结束位置(end)、以及开始(start)的标杆数值
    35.      * <code>
    36.      * 1、从开始位置+1开始处理，如果比开始大，就从后开始找比开始位置小的，然后交换. 开始位置+1，后置位置-1。
    37.      * 2、开始位置碰到结束位置的时候，就结束了
    38.      * </code>
    39.      *
    40.      * @param arr   待排序数组
    41.      * @param left  排序开始位置
    42.      * @param right 排序结束位置
    43.      * @return 中间点
    44.      * int[] array = {100, 9, 190, 361, 2, 7, 5};
    45.      * // 100 9 5 7 2 361 190
    46.      */
    47.     private static int find(int[] arr, int left, int right) {
    48.         int end = right;
    49.         int start = arr[left];
    50.         //从开始位置找到结尾
    51.         for (int i = left; i <= end; i++) {
    52.             //当前位置值
    53.             final int currentStart = arr[i];
    54.             //如果大于基点位置
    55.             if (currentStart > start) {
    56.                 //从后往前找
    57.                 for (int r = end; r >= i; r--) {
    58.                     //后边的值
    59.                     final int currentEnd = arr[r];
    60.                     //后边的值小于基点
    61.                     if (currentEnd < start) {
    62.                         //交换
    63.                         swap(arr, i, r);
    64.                         //向后走一下 && 继续从前往后走
    65.                         end--;
    66.                         break;
    67.                     } else {
    68.                         //继续向后走
    69.                         end--;
    70.                     }
    71.                 }
    72.             }
    73.         }
    74.         //这里是核心，交换基点位置. 基点左边的都小于基点 & 基点右边的都大于基点
    75.         swap(arr, left, end);
    76.         return end;
    77.     }
    79.     /**
    80.      * 交换
    81.      *
    82.      * @param array 数组
    83.      * @param a     低位
    84.      * @param b     高位
    85.      */
    86.     public static void swap(int[] array, int a, int b) {
    87.         int temp = array[a];
    88.         array[a] = array[b];
    89.         array[b] = temp;
    90.     }
    91. }