LeetCode ： 912. Sort an Array 排序堆排快排归并-蒲公英云

LeetCode ： 912. Sort an Array 排序堆排快排归并

悠悠 2021-06-12 20:36 553阅读 0赞

试题
Given an array of integers nums, sort the array in ascending order.

Example 1:

Input: [5,2,3,1]
Output: [1,2,3,5]
Example 2:

Input: [5,1,1,2,0,0]
Output: [0,0,1,1,2,5]

代码

堆排：
class Solution {
    public int[] sortArray(int[] nums) {
        buildHeap(nums);
        heapSort(nums);
        return nums;
    }
    public void heapSort(int[] nums){
        int size = nums.length;
        for(int i = size - 1; i > 0; i--){
            swap(nums, i, 0);
            heapify(nums, 0, i);
        }
    }
    public void buildHeap(int[] nums){
        int size = nums.length;
        for(int i = size / 2 - 1; i >= 0; i--){
            heapify(nums, i, size);
        }
    }
    public void heapify(int[] nums, int i, int size){
        int left = 2 * i + 1;
        int right = 2 * i + 2;
        int largest = i;
        if(left < size && nums[left] > nums[largest]) largest = left;
        if(right < size && nums[right] > nums[largest]) largest = right;
        if(largest != i){
            swap(nums, i, largest);
            heapify(nums, largest, size);
        }
        return;
    }
    public void swap(int[] nums, int i, int j){
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
        return;
    }
}
快排：
class Solution {
    public int[] sortArray(int[] nums) {
        quickSort(nums, 0, nums.length - 1);
        return nums;
    }
    public void quickSort(int[] nums, int left, int right){
        if(left < right){
            int mid = partition(nums, left, right);
            quickSort(nums, left, mid-1);
            quickSort(nums, mid+1, right);
        }
        return;
    }
    public int partition(int[] nums, int left, int right){
        int pivot = nums[left];
        int start = left, end = right;
        while(start < end){
            while(start < end && nums[end] >= pivot) end--;
            while(start < end && nums[start] <= pivot) start++;
            if(start < end){
                swap(nums, start, end);
            }
        }
        swap(nums, left, end);
        return end;
    }
    public void swap(int[] nums, int i, int j){
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
        return;
    }
}
# 归并：
class Solution {
    public int[] sortArray(int[] nums) {
        mergeSort(nums, 0, nums.length - 1);
        return nums;
    }
    public void mergeSort(int[] nums, int left, int right){
        if(left < right){
            int mid = left + (right - left) / 2;
            mergeSort(nums, left, mid);
            mergeSort(nums, mid+1, right);
            merge(nums, left, right, mid);
        }
        return;
    }
    public void merge(int[] nums, int left, int right, int mid){
        int[] temp = new int[nums.length];
        int first = left, second = mid + 1;
        int index = left;
        while(first <= mid && second <= right){
            if(nums[first] <= nums[second]){
                temp[index++] = nums[first++];
            }else{
                temp[index++] = nums[second++];
            }
        }
        while(first <= mid){
            temp[index++] = nums[first++];
        }
        while(second <= right){
            temp[index++] = nums[second++];
        }
        for(int i = left; i <= right; i++){
            nums[i] = temp[i];
        }
        return;
    }
    public void swap(int[] nums, int i, int j){
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
        return;
    }
}