快速排序

1. 快速排序

 
/**
 * 快速排序
 * O(nlogN) 、O(n^2)、O(nlogN)
 * 空间复杂度 O(logN)
 * 快速排序是一种高效的排序算法，采用分治法（Divide and Conquer）策略。其核心思想是：
 * 选择一个基准元素（pivot）。
 * 将数组分为两部分：小于基准的元素和大于基准的元素。
 * 递归地对两部分进行排序。
 * @param arr
 */
public static void quickSort(int[] arr, int left, int right) {
    if(left >= right){
        return;
    }
    //// 找到分区点，将数组分为两部分
    int partionIndex = partition(arr, left, right);
    quickSort(arr, left, partionIndex - 1);
    quickSort(arr, partionIndex + 1, right);
}

public static int partition(int[] arr, int left, int right){

    int pivot = arr[right];
    //i 用于跟踪小于基准元素（pivot）的元素的最后一个位置
    //初始时，i = low - 1 表示还没有任何元素被确认为小于基准元素
    int i = left - 1;
    //遍历数组从 j = left 到 j = right - 1
    for(int j = left; j < right; j++){
        if (arr[j] < pivot){
            //当找到一个元素 arr[j] 小于基准元素时，i 增加一，表示多了一个小于基准的元素，并交换 arr[i] 和 arr[j]。
            i++;
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }

    int temp = arr[i + 1];
    arr[i + 1] = arr[right]; // pivot
    arr[right] = temp;
    return i + 1;
}