【算法训练-排序算法 一】【手撕排序】快速排序、堆排序、归并排序

import java.util.*;
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param n int整型 the n
     * @return int整型
     */
    public int[] sortArray(int[] nums) {
        return quikSort(nums, 0, nums.length - 1);
    }
    // 对数组进行快速排序
    private int[] quikSort(int[] nums, int start, int end) {
        int privot;
        if (start < end) {
            // 1 获取数组基准值元素位置
            privot = partition(nums, start, end);
            // 2 分治：左半边元素快排
            quikSort(nums, start, privot - 1);
            // 3 分治：右半边元素快排
            quikSort(nums, privot + 1, end);
        }
        return nums;
    }
    // 单次归位基准值方法
    private int partition(int[] nums, int start, int end) {
        // 0 随机选择基准数大小，并与最左侧位置交换
        int randomValueIndex = new Random().nextInt(end - start + 1) + start;
        swap(nums, start, randomValueIndex);
        // 1 数组左边第一个为基准值，双指针分别执行开始和结束
        int privot = nums[start];
        int i = start;
        int j = end;
        // 2 开始交互，直到ij碰面，顺排
        while (i < j) {
            // 2-1 从右边开始找，如果值一直大于基准值则一直循环，直到找到小于基准值的元素，终止
            // 需要注意，满足条件情况下，因为基准值在最左边，最后要与j交换，所以j停止元素一定要小于基准值，所以优先满足j的条件，j要先走
            while (i < j && nums[j] >= privot) {
                j--;
            }
            // 2-2 从左边开始找，如果值一直小于基准值则一直循环，直到找到大于基准值的元素，终止
            while (i < j && nums[i] <= privot) {
                i++;
            }
            // 2-3 找到要交换的元素，且依然满足i<j的条件，交换
            if (i < j) {
                swap(nums, i, j);
            }
        }
        // 3 i和j碰面，说明该交换的元素已经交换完了，最后交换基准值与碰面的值
        swap(nums, start, j);
        // 4 返回基准值的当前位置，需要按此位置分割
        return j;
    }
    // 元素交换方法
    private void swap(int[] numbers, int i, int j) {
        int temp = numbers[i];
        numbers[i] = numbers[j];
        numbers[j] = temp;
    }
}

int randomValueIndex = new Random().nextInt(end - start + 1) + start; 
swap(partNums, start, randomValueIndex);

import java.util.*;
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param n int整型 the n
     * @return int整型
     */
    public int[] sortArray(int[] nums) {
        mergeSort(nums, 0, nums.length - 1);
        return nums;
    }
    // 对数组进行递归的归并排序
    private void mergeSort(int[] nums, int left, int right) {
        // 1 与快排不同的是，分割点直接选择中间位置
        int middle = left + (right - left) / 2;
        // 2 只要start<end，就一直进行归并
        if (left < right) {
            // 2-1 先分别归并左右两边，左右两边有序了，则最终有序
            mergeSort(nums, left, middle);
            mergeSort(nums, middle + 1, right);
            // 2-2 最后合并左右两边有序数组
            merge(nums, left, middle, right);
        }
    }
    // 单次划分的归并
    private void merge(int[] nums, int left, int middle, int right) {
        // 1 设置归并临时结果集,大小为归并后的总长度
        int[] result = new int[right - left + 1];
        // 2 定义两个排序数组的指针和结果集指针
        int i = left;
        int j = middle + 1;
        int k = 0;
        // 3 开始比较已排序集合值并将结果加入结果集
        while (i <= middle && j <= right) {
            if (nums[i] < nums[j]) {
                result[k++] = nums[i++];
            } else {
                result[k++] = nums[j++];
            }
        }
        // 4 如果有一个已经用完了，补充另一个排序数组
        while (i <= middle) {
            result[k++] = nums[i++];
        }
        while (j <= right) {
            result[k++] = nums[j++];
        }
        // 5 需要把这一段合并后已排序结果合并到整体nums的分段上
        for (int index = 0; index < result.length; index++) {
            nums[left + index] = result[index];
        }
    }
}

import java.util.*;
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param n int整型 the n
     * @return int整型
     */
    public int[] sortArray(int[] nums) {
        heapSort(nums);
        return nums;
    }
    // 1 堆排序函数
    private void heapSort(int[] nums) {
        // 1 构建大顶堆，此时数组0的位置即为堆顶元素，也就是数组最大值
        int heapSize = nums.length;
        buildMaxHeap(nums, heapSize);
        // 2 将堆顶元素与数组末尾元素交换
        for (int i = nums.length - 1; i >= 1; i--) {
            // 2-1 交换末尾元素与堆顶元素
            swap(nums, i, 0);
            // 2-2 缩小堆的生成范围，不包含末尾元素，因为末尾元素已调整完
            heapSize--;
            // 2-3 因为将一个末尾元素放到了堆顶，且其不一定是剩余元素中最大的，所以需要重新进行堆调整
            heapify(nums, 0, heapSize);
        }
    }
    // 2 构建大顶堆函数
    private void buildMaxHeap(int[] nums, int heapSize) {
        for (int i = heapSize / 2; i >= 0; i--) {
            heapify(nums, i, heapSize);
        }
    }
    // 3 堆调整函数
    private void heapify(int[] nums, int i, int heapsize) {
        // 逐层的进行元素调整:这里包含=号是因为要允许存在只有左节点的情况
        while (2 * i + 1 <= nums.length) {
            // 1 确定节点的左右节点位置
            int leftChild = 2 * i;
            int rightChild = 2 * i + 1;
            int maxPos = 0;
            // 2 当前层：进行堆调整，获取(当前、左子节点、右子节点)中值最大的索引，与堆顶进行交换
            maxPos = i;
            if (leftChild < heapsize && nums[i] < nums[leftChild]  ) {
                maxPos = leftChild;
            }
            if ( rightChild < heapsize && nums[maxPos] < nums[rightChild] ) {
                maxPos = rightChild;
            }
            // 3 如果maxPos不是i，则交换
            if (i != maxPos) {
                swap(nums, i, maxPos);
                // 继续下沉进行堆调整
                i = maxPos;
            } else {
                break;
            }
        }
    }
    // 4元素交换方法
    private void swap(int[] numbers, int i, int j) {
        int temp = numbers[i];
        numbers[i] = numbers[j];
        numbers[j] = temp;
    }
}