NC+LC：数组排序

NC140 排序

LC 912.排序数组：https://leetcode-cn.com/problems/sort-an-array/

使用Arrays工具类

这是最简单的方法，只需一行代码就可解决，但Arrays.sort()使用的并不是单一的排序，而是插入排序，快速排序，归并排序三种排序的组合，会在不同的情况使用不同的排序算法

参考资料：Java的Arrays.sort()方法到底用的什么排序算法

class Solution {
    public int[] sortArray(int[] nums) {
        if(nums.length == 0){
            return nums;
        }
        Arrays.sort(nums);
        return nums;
    }
}

冒泡排序

设置了一个排序标记，可避免对已排序的数组进行重复比较
注意：冒泡排序的时间复杂度为 $O(n^2)$ ，在本道题中使用冒泡排序是会超出时间限制的，但我们还是需要掌握这种方法

import java.util.*;

public class Solution {
    public int[] MySort (int[] arr) {//冒泡排序
        // write code here
        boolean isSorted = true;//排序标记
        for(int i = 0; i<arr.length - 1; i++){
            int temp = 0;
            for(int j = 0; j<arr.length - i - 1; j++){
                if(arr[j] > arr[j+1]){
                    temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                    isSorted = false;//有交换说明还不是有序的
                }
            }
            if(isSorted){//判断是否已有序，若已有序就可以直接退出循环，不用再进行下面的比较
                break;
            }
        }
        return arr;
    }
}

优化

如数组{3,4,2,1,5,6,7,8}这种情况，前半段无序，后半段有序，可以在每一轮排序后，记录下来最后一次元素交换的位置，该位置即为无序数列的边界，再往后就是有序区了，以此减少无谓的比较。

class Solution {
    public int[] sortArray(int[] nums) {
        if(nums.length == 0){
            return nums;
        }
        boolean isSorted = true; //记录当前数组是否有序
        int lastExchangeIndex = 0; //最后一次交换的位置
        int sortBorder = nums.length - 1; //无序边界，每次只需比较到这里
        for(int i = 0; i < nums.length - 1; i++){
            int temp = 0;
            for(int j = 0; j < sortBorder; j++){
                if(nums[j] > nums[j+1]){
                    temp = nums[j];
                    nums[j] = nums[j+1];
                    nums[j+1] = temp;
                    isSorted = false; //有交换说明还不是有序的
                    lastExchangeIndex = j;
                }
            }
            sortBorder = lastExchangeIndex;
            if(isSorted){ //判断是否已有序
                break;
            }
        }
        return nums;
    }
}

复杂度分析

时间复杂度为 $O(n^2)$ ，空间复杂度为 $O(1)$

插入排序

思路

在给定数组上进行移动插入操作，先暂存当前元素，然后循环遍历数组前面的元素，注意边界 $j > 0$ ，若前面的元素大于当前元素，就往右移动（这时当前元素的位置就会被覆盖，前面自然就会空出一个位置），直到找到一个当前元素能够插入的位置

「插入排序」可以提前终止内层循环（体现在 nums[j - 1] > temp 不满足时），在数组「几乎有序」的前提下，「插入排序」的时间复杂度可以达到 $O(N)$

参考资料：https://leetcode-cn.com/problems/sort-an-array/solution/fu-xi-ji-chu-pai-xu-suan-fa-java-by-liweiwei1419/

实现代码

class Solution {
    public int[] sortArray(int[] nums) { //插入排序
        int len = nums.length;   
        for(int i = 1; i < len; i++){
            int temp = nums[i]; //暂存当前元素
            int j = i;
            //循环判断前面的元素，若大于当前元素就往右移，直到找到一个当前元素能够插入的位置
            while(j > 0 && nums[j - 1] > temp){
                nums[j] = nums[j - 1];
                j--;
            }
            nums[j] = temp;
        }
        return nums;
    }
}

复杂度分析

时间复杂度： $O(n^2)$ ，这里 $n$ 是数组的长度；
空间复杂度： $O(1)$ ，使用到常数个临时变量。

快速排序

由冒泡排序演化而来，也是通过比较来交换元素实现排序，使用了分治法，重点是基准元素的选择和元素的交换

基准元素的选择：可以选择数组的第一个元素，或者随机选择一个元素再与第一个元素进行交换，都有可能选择到整个数组的最大值或最小值，无法达到分治的效果，所以最坏时间复杂度是 $O(n^2)$ ；

元素的交换：分为双边循环法和单边循环法

双边循环法

思路

设置两个指针 $left$ 和 $right$ ，初始分别指向数组头尾
从 $right$ 所指元素开始，若大于或等于基准元素pivot，则指针 $right$ 向左移动，若小于pivot则停止移动，转换到对 $left$ 进行操作；
将指针 $left$ 所指元素与pivot进行比较，若小于或等于则指针向右移动，若大于则停止移动，将 $left$ 和 $right$ 所指元素进行交换
以此类推，当 $left$ 等于 $right$ 时，将 $left$ 所指元素与pivot进行交换，以此完成了一次分治。

实现代码

class Solution {
    public int[] sortArray(int[] nums) {
        if(nums.length == 0){
            return nums;
        }
        quickSort(nums, 0, nums.length - 1);
        return nums;
    }
    public void quickSort(int[] nums, int start, int end){ //快速排序
        if(start >= end){
            return;
        }
        int i = new Random().nextInt(end - start + 1) + start; //随机选择一个位置
        swap(nums, i, start); //将其与开始位置进行元素交换
        int pivot = nums[start]; //确定基准元素
        int left = start;
        int right = end;
        while(left != right){
            while(left < right && nums[right] > pivot){
                right--;
            }
            while(left < right && nums[left] <= pivot){
                left++;
            }
            if(left < right){
                swap(nums, left, right);
            }
        }
        nums[start] = nums[left];
        nums[left] = pivot;
        int pivotIndex = left; //获得基准元素下标
        quickSort(nums, start, pivotIndex-1); //对左边再进行分治
        quickSort(nums, pivotIndex+1, end); //对有边再进行分治
    }
    public void swap(int[] nums, int i, int j) { //交换元素
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

单边循环法

思路

设置一个 $mark$ 指针指向数组起始位置，这个 $mark$ 指针代表小于基准元素的区域边界
遍历数组与基准元素pivot进行比较，若大于则继续遍历，若小于则需要做两件事：
第一， $mark$ 指针右移1位，因为小于pivot的区域边界增大了1；
第二，让最新遍历到的元素和 $mark$ 指针所在位置的元素交换位置，因为最新遍历的元素归属于小于pivot的区域
以此类推直到遍历到最后一个元素，最后将 $mark$ 所指元素与pivot进行交换，以此完成了以此分治。

实现代码

//单边循环法
public int partition(int[] arr,int startIndex,int endIndex){//分治
        int pivot = arr[startIndex];
        int mark = startIndex;
        for(int i = startIndex+1; i<=endIndex; i++){
            if(arr[i] < pivot){
                mark++;
                int tmp = arr[i];
                arr[i] = arr[mark];
                arr[mark] = tmp;
            }
        }
        arr[startIndex] = arr[mark];
        arr[mark] = pivot;
        return mark;
 }

复杂度分析

时间复杂度为 $O(nlogn)$ ，空间复杂度为 $O(logn)$

归并排序

思路

两个核心操作是分治和将两个有序序列合并成一个有序序列（无论这个序列是顺序存储还是链式存储），即（递归+合并）

实现代码

class Solution {
    int[] tmp; //保存合并排序的结果
    public int[] sortArray(int[] nums) {
        tmp = new int[nums.length];
        mergeSort(nums, 0, nums.length - 1);
        return nums;
    }
    public void mergeSort(int[] nums, int l, int r){ //归并排序
        //递归分治
        if(l >= r){
            return;
        }
        int mid = (l + r) / 2;
        mergeSort(nums, l, mid);
        mergeSort(nums, mid+1, r);
        //将左右两边进行有序合并
        int left = l;
        int right = mid + 1;
        int index = 0;
        while(left <= mid && right <= r){
            if(nums[left] < nums[right]){
                tmp[index++] = nums[left++];
            }else{
                tmp[index++] = nums[right++];
            }
        }
        while(left <= mid){
            tmp[index++] = nums[left++];
        }
        while(right <= r){
            tmp[index++] = nums[right++];
        }
        //将该区间的排序结果重新赋给nums
        for (int k = 0; k < r - l + 1; k++) {
            nums[k + l] = tmp[k];
        }
    }
}

复杂度分析

时间复杂度： $O(nlog⁡n)$ 。

由于归并排序每次都将当前待排序的序列折半成两个子序列递归调用，然后再合并两个有序的子序列，而每次合并两个有序的子序列需要 $O(n)$ 的时间复杂度，所以我们可以列出归并排序运行时间 $T(n)$ 的递归表达式： $T(n)=2T(\frac{n}{2})+O(n)$ ，根据主定理我们可以得出归并排序的时间复杂度为 $O(nlog⁡n)$ 。

空间复杂度： $O(n)$ 。

我们需要额外 $O(n)$ 空间的 $tmp$ 数组，且归并排序递归调用的层数最深为 $log_2 n$ ，所以我们还需要额外的 $O(log⁡n)$ 的栈空间，所需的空间复杂度即为 $O(n+log⁡n)=O(n)$ 。