题解 | #排序#

import java.util.*;


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


    public void quickSort(int[] arr) {
        quickSort(arr, 0, arr.length - 1);
    }

    private void quickSort(int[] arr, int l, int r) {
        if (l < r) {
            int middle = partition(arr, l, r);
            quickSort(arr, l, middle - 1);
            quickSort(arr, middle + 1, r);
        }
    }

    private int partition(int[] arr, int l, int r) {
        int tmp = arr[l];
        while (l < r) {
            while (l < r && arr[r] >= tmp) {
                r--;
            }
            arr[l] = arr[r];
            while (l < r && arr[l] <= tmp) {
                l++;
            }
            arr[r] = arr[l];
        }
        arr[l] = tmp;
        return l;
    }

    public void bubbleSort(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n - i - 1; j++) {
                if (arr[j] > arr[j + 1]) {
                    int tmp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = tmp;
                }
            }
        }
    }

    /**
    * ***********************************************************
     */
    public void heapSort(int[] arr) {
        // 初始建堆
        for (int i = arr.length / 2 - 1; i >= 0; i--) {
            adjustHeap(arr, i, arr.length);
        }
        for (int j = arr.length - 1; j > 0; j--) {
            int temp = arr[j];
            arr[j] = arr[0];
            arr[0] = temp;
            adjustHeap(arr, 0, j);
        }
    }

    private void adjustHeap(int[] arr, int i, int length) {
        int tmp = arr[i];
        for (int k = 2 * i + 1; k < length; k = 2 * k + 1) {
            if (k + 1 < length && arr[k] < arr[k + 1]) {
                k++;
            }

            if (arr[k] > tmp) {
                arr[i] = arr[k];
                i = k;
            } else {
                break;
            }
        }
        arr[i] = tmp;
    }


}