1 题目

排序数组

2 解

2.1 我的解

2.1.1 归并排序

  • 时间复杂度: O(nlogn)

     1
     2
     3
     4
     5
     6
     7
     8
     9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    
    class Solution {
    public int[] sortArray(int[] nums) {
        mergerSort(nums, 0, nums.length - 1);
        return nums;
    }
        
    public void mergerSort(int[] nums, int low, int high) {
        if (low == high) return;
        int mid = (low + high) / 2;
        mergerSort(nums, low, mid);
        mergerSort(nums, mid + 1, high);
        merge(nums, low, mid, high);
    }
        
    // 从小到大排序
    private void merge(int[] nums, int low, int mid, int high) {
        int[] tmpArray = new int[high - low + 1];
        int tmpArrayIndex = 0;
        int lowEndIndex = mid + 1;
        int highEndIndex = high + 1;
        int leftIndex = low;
        int rightIndex = mid + 1;
        while (leftIndex != lowEndIndex || rightIndex != highEndIndex) {
            if (leftIndex <= mid && rightIndex <= high) {
                if (nums[leftIndex] < nums[rightIndex]) {
                    tmpArray[tmpArrayIndex++] = nums[leftIndex++];
                } else {
                    tmpArray[tmpArrayIndex++] = nums[rightIndex++];
                }
            } else if (leftIndex != lowEndIndex) {
                tmpArray[tmpArrayIndex++] = nums[leftIndex++];
            } else if (rightIndex != highEndIndex){
                tmpArray[tmpArrayIndex++] = nums[rightIndex++];
            }
        }
            
        for (tmpArrayIndex = 0; tmpArrayIndex < tmpArray.length; tmpArrayIndex++) {
            nums[low++] = tmpArray[tmpArrayIndex];
        }
    }
    }