题解 | #排序#

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 将给定数组排序
     * @param arr int整型一维数组 待排序的数组
     * @return int整型一维数组
     */
    public int[] MySort (int[] arr) {
        //return bubbleSort1(arr);
        //return bubbleSort2(arr);
        //return bubbleSort3(arr);
        //return insertSort(arr);
        //return mergeSort(arr);
        return quickSort(arr);
    }
    private void swap(int[] arr, int i, int j) {
        int t = arr[i];
        arr[i] = arr[j];
        arr[j] = t;
    }
// ====== 冒泡排序 ======
    private int[] bubbleSort1(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[j] < arr[i]) {
                    swap(arr, i, j);
                }
            }
        }
        return arr;
    }
    private int[] bubbleSort2(int[] arr) {
        for (int i = arr.length - 1; i > 0; i--) {
            for (int j = 0; j < i; j++) {
                if (arr[j] > arr[j + 1]) {
                    swap(arr, j, j + 1);
                }
            }
        }
        return arr;
    }
    // 最优版本
    private int[] bubbleSort3(int[] arr) {
        for (int i = arr.length - 1; i > 0; i--) {
            boolean flag = false;
            for (int j = 0; j < i; j++) {
                if (arr[j] > arr[j + 1]) {
                    swap(arr, j, j + 1);
                    flag = true;
                }
            }
            if (!flag)break;
        }
        return arr;
    }
// ===== 插入排序 =====
    private int[] insertSort(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            int insertVal = arr[i];
            int index = i - 1;
            while (index >= 0 && insertVal < arr[index]) {
                arr[index + 1] = arr[index];
                index--;
            }
            if (index + 1 != i) {
                arr[index + 1] = insertVal;
            }
        }
        return arr;
    }
// ===== 选择排序 =====
    private int[] selectSort(int[] arr) {
        for (int i = 0; i < arr.length - 1; i++) {
            int minIndex = i;
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }
            if (minIndex == i)continue;
            swap(arr, minIndex, i);
        }
        return arr;
    }
// ===== 归并排序 =====
    private int[] mergeSort(int[] arr) {
        if (arr == null || arr.length <= 1)return arr;
        int[] temp = new int[arr.length];
        mergeSortPart(arr, 0, arr.length - 1, temp);
        return arr;
    }
    // 分区
    private void mergeSortPart(int[] arr, int left, int right, int[] temp) {
        if (left >= right)return;
        int mid = left + (right - left) / 2; // 从中间对半分
        mergeSortPart(arr, left, mid, temp);
        mergeSortPart(arr, mid + 1, right, temp);
        if (arr[mid] <= arr[mid + 1])return; // 已经有序，不用再合并
        merge(arr, left, mid, right, temp);
    }
    // 合并两个分区
    private void merge(int[] arr, int left, int mid, int right, int[] temp) {
        int i = left, j = mid + 1, k = 0;
        while (i <= mid && j <= right) {
            if (arr[i] <= arr[j]) {
                temp[k++] = arr[i++];
            } else {
                temp[k++] = arr[j++];
            }
        }
        while (i <= mid) {
            temp[k++] = arr[i++];
        }
        while (j <= right) {
            temp[k++] = arr[j++];
        }
        System.arraycopy(temp, 0, arr, left,
                         k); // 注意要从arr的left下标位置开始拷贝
    }
// ===== 快速排序 =====
    private int[] quickSort(int[] arr) {
        quickSort(arr, 0, arr.length - 1);
        return arr;
    }
    private void quickSort(int[] arr, int low, int high) {
        if (low < high) {
            int pos = partiation(arr, low, high);
            quickSort(arr, low, pos - 1);
            quickSort(arr, pos + 1, high);
        }
    }
    private int partiation(int[] arr, int low, int high) {
        int pv = arr[low];
        int i = low + 1, j = high;
        // 保证基准元素左侧的元素都比他小，右侧的元素都比他大
        while (i <= j) {
            while (i <= j && arr[i] < pv) {
                i++;
            }
            while (i <= j && arr[j] > pv) {
                j--;
            }
            if (i <= j) {
                swap(arr, i, j);
                i++;
                j--;
            }
        }
        // 将基准元素放在正确的位置
        swap(arr, low, j);
        return j;
    }
}