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

悠悠 2021-06-12 20:36 450阅读 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;
        }
    }