题解 | #排序#

import java.util.*;
import java.util.Arrays;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 将给定数组排序
     * @param arr int整型一维数组 待排序的数组
     * @return int整型一维数组
     */
    //
    public int[] MySort (int[] arr) {
        // write code here
        if (arr.length < 2) return arr;
        quickSort(arr, 0, arr.length - 1);
        return arr;

    }
    private void quickSort(int[] array, int low, int high) {

        //快排子区间越往下划分，越趋近于有序，考虑使用简单插入排序可以优化性能
        // 如果数组区间长度小于500采用插入排序
        if (high - low <= 500) {
            insertSort(array);
            return;
        }
        //随机选择一个数作为枢轴
        Random random = new Random();
        int index = random.nextInt(array.length);
        int pivot = array[index];
        array[index] = array[low];//low位置为无效数据
        int cur_low = low;
        int cur_high = high;
        while (cur_low < cur_high) {
            while (cur_low < cur_high && array[cur_high] >= pivot) {
                cur_high--;
            }
            if (cur_low < cur_high) { //已经找到
                array[cur_low] = array[cur_high];
                cur_low++;//减少重复比较
            }
            while (cur_low < cur_high && array[cur_low] <= pivot) {
                cur_low++;
            }
            if (cur_low < cur_high) {
                array[cur_high] = array[cur_low];
                cur_high--;//减少重复比较
            }
        }
        array[cur_low] = pivot;
        quickSort(array, low, cur_low - 1);
        quickSort(array, cur_low + 1, high);


    }
    public static void insertSort(int[] arr) {
        int i, j;
        //4,2,1,7,8
        for (i = 1; i < arr.length; i++) {
            if (arr[i - 1] > arr[i]) {
                //temp=2
                int temp = arr[i];//设置哨兵
                //必须要保证数组下标>=0,才for循环
                for (j = i - 1; j >= 0 && arr[j] > temp ; j--) {
                    arr[j + 1] = arr[j]; //arr[1]=4
                }
                //j=-1
                arr[j + 1] = temp; //arr[0]=2
                //2 4 1 7 8
            }
        }
    }
}