利用递归实现快速排序，选定最有一个数为轴，遍历区间内的数值，通过交换使其左小右大（此时轴的位置就是排序后的位置，不论左右如何变换，此位置相对不变，所以可按此理论递归实现排序)。再分别为其左右两侧边的数字找准位置排序完成。 第一步：假设以最后一位作为轴，记为P，0位置记为i, 可能大于s[p]的倒数第二个位置记为j 第二步：循环数组，小于s[p]放到左边，大于s[p]通过和s[j]交换放到右边 for i <=j ; s[i] < s[p]; i++. 移动i的位置到下一次可进行寻找比s[P]小的数的位置 s[i] >= s[p]; swap(i, j—). s[i]不小区s[p]的数值时，交换i和j位置的数字，将i放到倒数第二个大于s[p]的位置上。因此时s[j]已经是大于s[p]的数值了，j需要—，向前移动一位等待再次放置比s[p]大的数值。 i > j; 如果i已经大于j，说明比s[p]小的数值已经全部找到了。此时swap(i,p)。（注：i==p的时候不必交换，为减少代码判断，swap具备了当两个位置相等是，不交换的功能） 第三步: 递归实现其他位置的定位

    image.png

    1. package com.ss.sort;
    3. import java.util.Arrays;
    4. import java.util.concurrent.ThreadLocalRandom;
    6. /**
    7.  * <p>
    8.  * 快速排序
    9.  * </P>
    10.  *
    11.  * @author: zhangss
    12.  * @since: 2022-05-07
    13.  **/
    14. public class QuickSort {
    15.     public static void main(String[] args) {
    16. //        int[] s = {3, 6, 2, 7, 4, 9};
    17.         for (int i = 0; i < 5_0000; i++) {
    18.             int[] s = random(10);
    19.             int[] cs = copy(s);
    20.             quickSort(s,  0,s.length - 1);
    21.             comparator(s, cs);
    22. //            print(cs);
    23. //            print(s);
    24.         }
    25.     }
    27.     /**
    28.      * 单轴快速排序
    29.      * 选定一个轴位置为P, 将<P放到左边， >P放到右边。P位置就排好了
    30.      * 括号括住的地方就是比P小最后一个位置
    31.      * )3, 6, 2, 1, 4, 5
    32.      *  i, -, -, -, j, P
    33.      *
    34.      * s[i]<s[p]; i++
    35.      * 3), 6, 2, 1, 4, 5
    36.      *  -, i, -, -, j, P
    37.      *
    38.      * s[i]>s[p]; swap(i, j--)
    39.      * swap
    40.      * 3), 4, 2, 1, 6, 5
    41.      *  -, i, -, -, j, P
    42.      * j--
    43.      * 3), 4, 2, 1, 6, 5
    44.      *  -, i, -, j, -, P
    45.      *
    46.      *  s[i]<s[p]; i++
    47.      * 3, 4), 2, 1, 6, 5
    48.      *  -, -, i, j, -, P
    49.      *
    50.      *  s[i]<s[p];i++  i和j相等时，还不确定i位置的数是和p位置的大小，所以不需要再比较一次。
    51.      * 3, 4, 2), 1,  6, 5
    52.      * -, -, -, i/j, -, P
    53.      *
    54.      * s[i]<s[p]; i++
    55.      * 3, 4, 2, 1), 6, 5
    56.      * -, -, -, j,  i, P
    57.      *
    58.      * i>j 跳出循环
    59.      *
    60.      * swap[i,p]; 此时i位置左边数小于s[i],右边数大于s[i]
    61.      * 3, 4, 2, 1), 5, 6
    62.      * -, -, -, j,  i, P
    63.      *
    64.      * @param s 随机数组
    65.      * @param L 左侧位置
    66.      * @param R 右侧位置
    67.      */
    68.     public static void quickSort(int[] s, int L, int R){
    69.         if (L >= R || R < 1) {
    70.             return;
    71.         }
    72.         int i = L, j = R-1;
    73.         for (; i <= j; ) {
    74.             if (s[i] < s[R]) {
    75.                 i++;
    76.             } else {
    77.                 swap(s, i, j--);
    78.             }
    79.         }
    80.         swap(s, i, R);
    81. //        print(s);
    82. //        System.out.println("右边有序 i:" + (i+1) + "P:" + R);
    83.         quickSort(s, i+1, R);
    84. //        System.out.println("左边有序 L:" + L + "R:" + (i-1));
    85.         quickSort(s, L, i - 1);
    86.     }
    88.     public static void swap(int[] s, int a, int b){
    89.         if(a == b){
    90.             return;
    91.         }
    92.         int temp = s[a];
    93.         s[a] = s[b];
    94.         s[b] = temp;
    95.     }
    97.     /**
    98.      * 对数器
    99.      * @param s
    100.      * @param cs
    101.      */
    102.     public static void comparator(int[] s, int[] cs){
    103.         Arrays.sort(cs);
    104.         for (int i = 0; i < s.length; i++) {
    105.             if (s[i] != cs[i]) {
    106.                 throw new RuntimeException("错误喽");
    107.             }
    108.         }
    109.     }
    110.     public static int[] copy(int[] s){
    111.         int[] cs = new int[s.length];
    112.         for (int i = 0; i < s.length; i++) {
    113.             cs[i] = s[i];
    114.         }
    115.         return cs;
    116.     }
    117.     public static int[] random(int l){
    118.         int[] s = new int[l];
    119.         for (int i = 0; i < l; i++) {
    120.             s[i] = ThreadLocalRandom.current().nextInt(-100, 100);
    121.         }
    122.         return s;
    123.     }
    124.     public static void print(int[] s){
    125.         System.out.println(Arrays.toString(s));
    126.     }
    127. }