题解 | #排序#

import java.util.*;


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

    //冒泡排序
    public int[] bubbleSort (int[] arr) {
        int len = arr.length;
        for (int i = 1; i < len; i++) {
            for (int j = 0; j < len - i; j++) {
                if (arr[j] > arr[j + 1]) {
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
        return arr;
    }
    //选择排序
    public int[] selectSort(int[] arr) {
        int len = arr.length;
        for (int i = 0; i < len; i++) {
            int k = i;
            for (int j = i + 1; j < len; j++) {
                if (arr[j] < arr[k]) {
                    k = j;
                }
            }
            swap(arr, i, k);
        }
        return arr;
    }

    //直接插入排序
    public int[] insertSort(int[] arr) {
        int len = arr.length;
        for (int i = 1; i < len; i++) {
            int temp = arr[i], j = i;
            while (j > 0 &&
                    temp < arr[j - 1]) { //当j-1>=0且待插入元素小于j位的前一位元素时
                arr[j] = arr[j - 1]; //前一位元素后移
                j--;
            }
            arr[j] = temp;
        }
        return arr;
    }

    //快速排序
    public int[] quickSort(int[] arr, int left, int right) {
        if (left < right) {
            int pos = partition(arr,left,right);
            quickSort(arr, left, pos - 1);
            quickSort(arr, pos + 1, right);
        }
        return arr;
    }
    //分区
    public int partition(int[] arr, int left, int right) {
        Random r = new Random();
        int p = (int) r.nextDouble() * (right - left) +
                left; //随机一个在[left,right]间的数
        swap(arr, p, left);
        int baseNum = arr[left];
        while (left < right) {
            while (left < right && arr[right] > baseNum) right--;
            while (left < right && arr[left] < baseNum) left++;
            if(left < right) swap(arr,left,right);
        }
        arr[left] = baseNum;
        return left;
    }

    
    public void swap(int[] A, int i, int j) {
        int temp = A[i];
        A[i] = A[j];
        A[j] = temp;
    }
}