力扣题解

public class Sort {
    private int[] aux;
    public int[] sortArray(int[] nums) {
        // bubbleSort(nums); // 冒泡排序
        // doubleBubbleSort(nums); // 双向冒泡排序
        // selectionSort(nums); // 选择排序
        // insertionSort(nums); // 插入排序
        // shellSort(nums); // 希尔排序
        // aux = new int[nums.length];
        // mergeSort(nums, 0, nums.length - 1); // 归并排序——自顶向下
        // mergeSortBU(nums); // 归并排序——自底向上
        // quickSort(nums, 0, nums.length - 1); // 快速排序
        // heapSort(nums); // 堆排序
        // countSort(nums); // 计数排序
        return nums;
    }
    private void exch(int[] nums, int i, int j) {
        nums[i] = nums[i] + nums[j] - (nums[j] = nums[i]);
    }
    /** 冒泡排序 平均时间复杂度 O(n2) 空间复杂度O(1) 稳定 */
    private void bubbleSort(int[] nums) {
        for (int i = 0; i < nums.length; ++i) {
            for (int j = i + 1; j < nums.length; ++j) {
                if (nums[j] < nums[i]) exch(nums, i, j);
            }
        }
    }
    /** 双向冒泡排序 平均时间复杂度 O(n2) 空间复杂度O(1) 稳定 */
    private void doubleBubbleSort(int[] nums) {
        int lo = 0, hi = nums.length - 1;
        int i;
        while (lo < hi) {
            for (i = lo; i < hi; ++i) if (nums[i + 1] < nums[i]) exch(nums, i, i + 1);
            for (i = hi - 1; i >= lo; --i) if (nums[i + 1] < nums[i]) exch(nums, i, i + 1);
            ++lo;
            --hi;
        }
    }
    /** 选择排序 平均时间复杂度 O(n2) 空间复杂度O(1) 不稳定 */
    // 不稳定举例 58529 -> 28559 两个5的相对位置改变
    private void selectionSort(int[] nums) {
        int min;
        for (int i = 0; i < nums.length; ++i) {
            min = i;
            for (int j = i + 1; j < nums.length; ++j) {
                if (nums[j] < nums[min]) min = j;
            }
            exch(nums, i, min);
        }
    }
    /** 插入排序 平均时间复杂度 O(n2) 空间复杂度O(1) 稳定 */
    private void insertionSort(int[] nums) {
        for (int i = 1; i < nums.length; ++i) {
            for (int j = i; j > 0 && nums[j] < nums[j - 1]; --j) {
                exch(nums, j, j - 1);
            }
        }
    }
    /** 希尔排序 平均时间复杂度 O(n2) 空间复杂度O(1) 稳定 */
    private void shellSort(int[] nums) {
        int h = 1;
        while (h < nums.length / 3) h = h * 3 + 1; // 递增序列（1,4,13,40...）
        while (h >= 1) {
            for (int i = h; i < nums.length; ++i)
                for (int j = i; j >= h && nums[j] < nums[j - h]; j -= h) exch(nums, j - h, j);
            h /= 3;
        }
    }
    /** 归并排序——自底向上 平均时间复杂度 O(nlogn) 空间复杂度O(n) 稳定 */
    private void mergeSortBU(int[] nums) {
        int n = nums.length;
        for (int size = 1; size < n; size *= 2) {
            for (int lo = 0; lo < n - size; lo += size * 2) {
                merge(nums, lo, lo + size - 1, Math.min(lo + 2 * size - 1, n - 1));
            }
        }
    }
    /** 归并排序——自顶向下 平均时间复杂度 O(nlogn) 空间复杂度O(n) 稳定 */
    private void mergeSort(int[] nums, int lo, int hi) {
        if (lo >= hi) return;
        int mid = lo + (hi - lo) / 2;
        mergeSort(nums, lo, mid);
        mergeSort(nums, mid + 1, hi);
        merge(nums, lo, mid, hi);
    }
    private void merge(int[] nums, int lo, int mid, int hi) {
        int i = lo, j = mid + 1;
        arraycopy(nums, lo, aux, lo, hi - lo + 1);
        for (int k = lo; k <= hi; ++k) {
            if (i > mid) nums[k] = aux[j++];
            else if (j > hi) nums[k] = aux[i++];
            else if (aux[i] < aux[j]) nums[k] = aux[i++];
            else nums[k] = aux[j++];
        }
    }
    /** 快速排序 平均时间复杂度 O(nlogn) 空间复杂度 O(1) 不稳定 */
    private void quickSort(int[] nums, int lo, int hi) {
        if (lo >= hi) return;
        int mid = partition(nums, lo, hi);
        quickSort(nums, lo, mid - 1);
        quickSort(nums, mid + 1, hi);
    }
    private int partition(int[] nums, int lo, int hi) {
        int i = lo, j = hi + 1;
        int val = nums[lo];
        while (true) {
            while (nums[++i] < val) if (i == hi) break;
            while (val < nums[--j]) if (j == lo) break;
            if (i >= j) break;
            exch(nums, i, j);
        }
        exch(nums, lo, j);
        return j;
    }
    /** 计数排序 平均时间复杂度 O(k*n) 空间复杂度 O(k) 稳定 */
    private void countSort(int[] nums) {
        int max = -50001, min = 50001;
        for (int val : nums) {
            max = Math.max(val, max);
            min = Math.min(val, min);
        }
        int[] counter = new int[max - min + 1]; // 计数器
        for (int val : nums) {
            ++counter[val - min];
        }
        int idx = 0;
        int cnt;
        for (int val = min; val <= max; ++val) {
            cnt = counter[val - min]; // 重复数
            while (cnt-- > 0) nums[idx++] = val;
        }
    }
    private void heapSort(int[] nums) {
        int n = nums.length;
        for (int i = n / 2; i >= 1; --i) {
            sink(nums, i, n);
        }
        while (n > 1) {
            exch(nums, 1, n--);
            sink(nums, 1, n);
        }
    }
    private void sink(int[] nums, int k, int n) {
        int j;
        while (2 * k <= n) {
            j = 2 * k;
            if (j < n && nums[j] < nums[j + 1]) ++j;
            if (nums[j] <= nums[k]) break;
            exch(nums, k, j);
            k = j;
        }
    }
}

总结

可以去力扣这题练习