LeetCode - 912. Sort an Array

原题链接：https://leetcode.com/problems/sort-an-array/
难度：medium

通过刷leetcode来复习下排序算法，首先是快速排序：

class Solution {
    public List<Integer> sortArray(int[] nums) {
        
        quickSort(nums, 0, nums.length -1);
        
        List<Integer> result = new ArrayList();
        for(int n : nums) {
            result.add(n);
        }
        return result;   
    }
    
    private void quickSort(int[] nums, int s, int e) {
        if(s >= e) return;
        
        int i = s;
        int j = e;
        while(i < j) {
            
            while(i < j && nums[j] >= nums[s]) j --;
            while(i < j && nums[i] <= nums[s]) i ++;
            
            if(i < j) {
                // swap i and j
                nums[i] = nums[i] + nums[j];
                nums[j] = nums[i] - nums[j];
                nums[i] = nums[i] - nums[j];
                
            }
            
        }
        if(i != s) {
            // swap the pilot and i
            nums[i] = nums[i] + nums[s];
            nums[s] = nums[i] - nums[s];
            nums[i] = nums[i] - nums[s];
        }
        
        if(i - 1 > s)
            quickSort(nums, s, i - 1);
        if(i + 1 < e)
            quickSort(nums, i + 1, e);
    }
}

堆排序，升序本来应该是大根堆的，但是为了返回，小根队在排序过程中就能拿到结果

class Solution {
    public List<Integer> sortArray(int[] nums) {
        List<Integer> result = new ArrayList();
        for(int i = nums.length / 2 - 1; i >= 0; i --) {
            heapify(nums, i, nums.length);
        }
        for (int i = nums.length - 1; i > 0; i--) {
            result.add(nums[0]);
            swap(nums, 0, i);
            heapify(nums, 0, i);
        }
        result.add(nums[0]);
        return result;   
    }
    
    private void heapify(int[] nums, int idx, int length) {
        int left = idx * 2 + 1;
        int right = idx * 2 + 2;
        int smallest = idx;
        
        if(left < length && nums[smallest] > nums[left]) {
            smallest = left;
        } 
        if(right < length && nums[smallest] > nums[right]) {
            smallest = right;
        }
        
        if(smallest != idx) {
            swap(nums, idx, smallest);
            heapify(nums, smallest, length);
        }
        
    }
    
    private void swap(int[] nums, int from, int to) {
        nums[from] = nums[from] + nums[to];
        nums[to] = nums[from] - nums[to];
        nums[from] = nums[from] - nums[to];
    }
}

归并排序

class Solution {
    public List<Integer> sortArray(int[] nums) {
        
        int[] temp = new int[nums.length];
        mergeSort(nums, 0, nums.length - 1, temp);
        List<Integer> result = new ArrayList<>();
        for(int i : temp) {
            result.add(i);
        }
        return result;   
    }
    
    private void mergeSort(int[] a, int l, int r, int[] temp) {

        if(l >= r) {
          return;
        }

        int divide = (l + r) / 2;
        mergeSort(a, l, divide, temp);
        mergeSort(a, divide + 1, r, temp);
        merge(a, l, divide, r, temp);
    }
    
    private void merge(int[] a, int l, int m, int r, int[]temp) {
        int i = l, j = m + 1, k = l;
        for (; i <= m & j <= r; k ++) {
          if(a[i] <= a[j]) {
            temp[k] = a[i ++];
          } else {
            temp[k] = a[j ++];
          }
        }
        while(i <= m) {
          temp[k ++] = a[i ++];
        }

        while(j <= r) {
          temp[k ++] = a[j ++];
        }

        for(i = l; i <= r; i ++) {
          a[i] = temp[i];
        }
    }
    
}