LeetCode_Sorting_912. Sort an Array 排序數組【快速排序，堆排序，歸并排序】【java】【中等】

目錄

​​一，題目描述​​

​​英文描述​​

​​中文描述​​

​​示例與說明​​

​​二，解題思路​​

​​快速排序​​

​​堆排序​​

​​歸并排序​​

​​三，AC代碼​​

​​Java​​

​​快速排序（随機哨兵）​​

​​堆排序​​

​​歸并排序​​

​​四，解題過程​​

​​第一博​​

​​第二搏​​

​​第三搏​​

一，題目描述

英文描述

Given an array of integers ​

​nums​

​, sort the array in ascending order.

中文描述

給你一個整數數組 ​

​nums​

​，請你将該數組升序排列。

示例與說明

提示：

1. ​

   ​1 <= nums.length <= 50000​

   ​
2. ​

   ​-50000 <= nums[i] <= 50000​

   ​

二，解題思路

參考​​@力扣官方題解【排序數組】​​

快速排序

普通的快速排序（預設将哨兵設定為第一個或者最後一個元素）會逾時，這裡采用官方題解中的方法，設定随機哨兵pivot。

int index = (int) Math.random() * (l - r) + l;// 生成[l, r)之間的随機數
int pivot = nums[index];      

堆排序

将數組中的元素一個個添加入堆中，執行siftUp操作；

将堆頂元素與堆中末尾元素調換，邊界減一，自上而下調整堆；

當堆中元素為空，數組完成排序。

歸并排序

經典的遞歸思想。

将數組拆成兩部分，這兩部分均調用MergeSort方法，可以看作已經排好序，接下來隻需要進行合并有序數組的操作。

這裡的空間複雜度為O(N)，因為合并有序數組時，額外建立了一塊區域，用來存放合并的結果，最後将結果拷貝至原數組中。（若直接在原數組中進行合并操作，過程較為複雜）

三，AC代碼

Java

快速排序（随機哨兵）

class Solution {
    public void swap (int[] nums, int a, int b) {
        int tem = nums[a];
        nums[a] = nums[b];
        nums[b] = tem;
    }
    public static void quickSort(int[] array, int left, int right) {
        if (right - left < 2) return;
        int index = partation(array, left, right);
        quickSort(array, left, index);
        quickSort(array, index, right);
    }
    public static int partation(int[] array, int left, int right) {
        int index = (int) (Math.random() * (right - left) + left);// ！！！獲得随機哨兵位置
        System.out.println("#" + index);
        int pivot = array[index];// 記錄哨兵值
        swap(array, left, index);// 将哨兵與待排序區間首個元素交換
        index = left;
        for(int i = left + 1; i < right; i++) {
            if (array[i] < pivot) {
                swap(array, ++index, i);
            }
        }
        swap(array, left, index);// 将哨兵與已分區區間的最後一個元素交換
        return index;
    }
    public int[] sortArray(int[] nums) {
        quickSort(nums, 0, nums.length);// 
        return nums;
    }
}      

堆排序

class Solution {
    public void swap (int[] nums, int a, int b) {
        int tem = nums[a];
        nums[a] = nums[b];
        nums[b] = tem;
    }
    public void siftUp (int[] nums, int index) {
        int fatherIndex = (index - 1) / 2;
        while (fatherIndex >= 0 && nums[index] > nums[fatherIndex]) {
            swap(nums, fatherIndex, index);
            index = fatherIndex;
            fatherIndex = (index - 1) / 2;
        }
    }
    public void siftDown (int[] nums, int index, int border) {
        int childIndex = index * 2 + 1;
        while (childIndex < border) {
            if (childIndex + 1 < border && nums[childIndex + 1] > nums[childIndex]) {
                childIndex++;
            }
            if (nums[index] > nums[childIndex]) break;// 該節點大于任意子節點
            swap(nums, index, childIndex);
            index = childIndex;
            childIndex = index * 2 + 1;
        }
    }
    public void heapSort(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            siftUp(nums, i);// 建構大根堆
        }
        for (int i = nums.length - 1; i > 0; i--) {
            swap(nums, 0, i);// 将堆頂元素調整到數組末尾
            siftDown(nums, 0, i);// 自上向下調整堆
        }
    }

    public int[] sortArray(int[] nums) {
        heapSort(nums);
        return nums;
    }
}      

歸并排序

class Solution {
    public static int[] merge(int[] left, int[] right) {
        int[] result = new int[left.length + right.length];
        for (int i = 0, j = 0, index = 0; index < left.length + right.length; index++) {
            if (i >= left.length) {
                result[index] = right[j++];
            } else if (j >= right.length) {
                result[index] = left[i++];
            } else if (left[i] < right[j]) {
                result[index] = left[i++];
            } else {
                result[index] = right[j++];
            }
        }
        return result;
    }
    public static int[] mergeSort(int[] array, int l, int r) {
        if (r - l < 2) return array;
        int mid = (l + r) / 2;
        int[] left = Arrays.copyOfRange(array, l, mid);
        int[] right = Arrays.copyOfRange(array, mid, r);

        return merge(mergeSort(left, 0, left.length), mergeSort(right, 0, right.length));
    }

    public int[] sortArray(int[] nums) {
        mergeSort(nums, 0, nums.length);            // !!!注意邊界
        return nums;
    }
}      

四，解題過程

第一博

設定随機哨兵的快速排序（細節調了将近50min。。。）

第二搏

堆排序，之前實作過類似的結構，這裡比較輕松

第三搏