快速排序--单边循环法

4, 7, 3, 5, 6, 2, 8, 1

standardValue=4, mark=0 

4, 3, 2, 1, 6, 7, 8, 5 

1, 3, 2, 4, 6, 7, 8, 5 

package com.xgcd.lab.sort;

import java.util.Arrays;

/**
 * @description: 快速排序
 * @author: liangyadong
 * @date: 2021/6/29 23:24
 */
public class QuickSort {

    public static void quickSort(int[] arr, int starTindex, int endIndeX) {
        // 递归结束条件
        if (starTindex >= endIndeX) {
            return;
        }

        // 1.得到基准元素位置
        int standardIndex = partition(arr, starTindex, endIndeX);

        // 2.根据基准元素,分成两个部分进行递归排序
        quickSort(arr, starTindex, standardIndex - 1);
        quickSort(arr, starTindex + 1, endIndeX);

    }

    /**
     * 分治(单边循环法)
     *
     * @param arr        待交换的数组
     * @param starTindex 起始下标
     * @param endIndex   结束下标
     * @return 基准元素的位置
     */
    private static int partition(int[] arr, int starTindex, int endIndeX) {
        // 取第一位元素作为基准元素
        int standardValue = arr[starTindex];
        // 指针指向数列的起始位置,mark代表小于基准元素的区域边界
        int mark = starTindex;

        // 遍历数组,如果遍历到的元素小于基准元素: 1. 2.
        for (int i = starTindex + 1; i <= endIndex; i++) {
            if (arr[i] < standardvalue) {
                // 1.指针右移一位
                mark++;
                // 2.并将当前遍历到的元素和指针所指元素交换
                int temp = arr[i];
                arr[i] = arr[mark];
                arr[mark] = temp;
            }
        }

        // 遍历结束,将基准元素和指针指向的元素交换,这一轮宣告结束
        arr[starTindex] = arr[mark];
        arr[mark] = standardValue;
        return mark;
    }

    public static void main(String[] args) {
        int[] arr = new int[]{4, 7, 3, 5, 6, 2, 8, 1};
        quickSort(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr));
    }
}