排序算法

912. 排序数组

给你一个整数数组 nums，请你将该数组升序排列。

示例 1：

输入：nums = [5,2,3,1]
输出：[1,2,3,5]

示例 2：

输入：nums = [5,1,1,2,0,0]
输出：[0,0,1,1,2,5]

提示：

• 1 <= nums.length <= 5 * 104
• -5 * 104 <= nums[i] <= 5 * 104

快速排序

class Solution {
    public int[] sortArray(int[] nums) {
        quickSort(nums, 0, nums.length-1);
        return nums;
    }

    public int Partition(int[] nums , int left , int right){
        int pivot = nums[left]; 
        //填坑法，先将left取出来，然后用右边小于piovt的数填左边，再用左边大于pivot的数填右边
        //left和right相遇时，剩下的坑就是pivot的位置
        while(left < right){
            while(left < right && nums[right] >= pivot) right--;
                nums[left] = nums[right];
            while(left < right && nums[left] <= pivot) left++;
                nums[right] = nums[left];
        }
        nums[left] = pivot; //确定中枢最终位置
        return left;
    }

    public void quickSort(int[] nums, int left, int right){
        if(left < right){
            int pivot = Partition(nums, left, right);
            quickSort(nums, left, pivot-1);
            quickSort(nums, pivot+1, right);
        }
    }
}

时间复杂度：确定中枢的时间复杂度为O(n)，基于随机选取主元的快速排序时间复杂度为期望 O(nlog⁡n)，最坏的情况即数组有序的情况下时间复杂度为O(n^2)

空间复杂度：O(h)，其中h 为快速排序递归调用的层数。最坏情况下，即数组有序的情况下，需 O(n)的空间，最优情况下每次都平衡，此时整个递归树高度为logn，空间复杂度为 O(log⁡n)

堆排序

class Solution {
    public int[] sortArray(int[] nums) {
        heapSort(nums, nums.length);
        return nums;
    }


    public void adjustHeap(int[] nums, int k, int len){//从下标k调整堆
        while(2 * k + 1 <= len-1){
            int i = 2 * k + 1; //i为k结点的左孩子
            if(i < len-1 && nums[i] < nums[i+1]){//右孩子比左孩子大
                i++;
            }
            if(nums[k] < nums[i]){//待调整结点比孩子小，交换
                swap(nums, k, i);
                k = i; //待调整元素变为i结点
            }else{//该节点已经满足大顶堆要求
                 break;
            }
        }
    }
    public void buildHeap(int[] nums, int len){//建立大顶堆
        for(int i = len/2-1 ; i >= 0; i--){
            adjustHeap(nums, i, len);
        }
    }

    public void heapSort(int[] nums, int len){ //对下标0-len的元素进行堆排序
        buildHeap(nums, len); //建立数组的大顶堆
        for(int i = 0 ; i < nums.length; i++){
            System.out.println(nums[i]);
        }
        for(int i = len-1; i > 0; i--){//i指向堆最后一个元素
            swap(nums, 0, i);
            adjustHeap(nums, 0, i); //从根节点开始调整堆，调整范围为长度len--
        }
    }
    
    public void swap(int[] nums, int i, int j){ //交换元素
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

时间复杂度：$O(nlog⁡n)$。初始化建堆的时间复杂度为 $O(n)$，建完堆以后需要进行 n−1次调整，一次调整的时间复杂度为 $O(log⁡n)$，那么n−1次调整即需要 $O(nlog⁡n)$的时间复杂度。因此，总时间复杂度为 $O(n+nlog⁡n)=O(nlog⁡n)$

空间复杂度：O(1)，只需要常数的空间存放若干变量。

归并排序

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) / 2;
            mergeSort(nums, left, mid);
            mergeSort(nums, mid + 1, right);

       
            int[] temp = new int[right - left + 1];
            int i = left;
            int j = mid + 1;
            int k = 0;
            while (i <= mid && j <= right) {
                if (nums[i] <= nums[j]) {//两个有序段两两比较，小的放入排好的数组
                    temp[k++] = nums[i++];
                } else {
                    temp[k++] = nums[j++];
                }
            }
            //将剩余元素复制到排好的数组
            while (i <= mid) temp[k++] = nums[i++];
            while (j <= right) temp[k++] = nums[j++];
            System.arraycopy(temp, 0, nums, left, right-left+1);
        }
    }

}

时间复杂度：O(nlog⁡n)。归并排序每次都将当前待排序的序列折半成两个子序列递归调用，然后再合并两个有序的子序列，而每次合并两个有序的子序列需要 O(n)，所以我们可以列出归并排序运行时间 T(n)的递归表达式：T(n)=2T(2/n)+O(n)

空间复杂度：O(n)。我们需要额外 O(n)空间的 tmp数组

冒泡排序（超时）

class Solution {
    public int[] sortArray(int[] nums) {
        bubbleSort(nums, nums.length);
        return nums;
    }

    public void bubbleSort(int[] nums, int len){
        boolean flag = false;//记录一趟排序有没有发生交换
        int i = 0; //i表示0-i-1下标的元素已经有序
        while(i < len){
            for(int j = len-1; j > i ; j--){
                if(nums[j] < nums[j-1]){//后一个元素比前一个大，交换
                    swap(nums, j, j-1);
                    flag = true; 
                }
            }
            if(!flag) break; //没有发生交换，已经有序
            i++;
        }
    }

     private void swap(int[] nums, int index1, int index2) {
        int temp = nums[index1];
        nums[index1] = nums[index2];
        nums[index2] = temp;
    }

}

时间复杂度：$O(n^2)$

空间复杂度：$O(1)$