NC+LC：数组排序

使用Arrays工具类

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

冒泡排序

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

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;
    }
}

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;
    }
}

插入排序

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

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

参考资料：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;
    }
}

快速排序

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

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

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

双边循环法

思路

• 设置两个指针和，初始分别指向数组头尾
• 从所指元素开始，若大于或等于基准元素pivot，则指针向左移动，若小于pivot则停止移动，转换到对进行操作；
• 将指针所指元素与pivot进行比较，若小于或等于则指针向右移动，若大于则停止移动，将和所指元素进行交换
• 以此类推，当等于时，将所指元素与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;
    }
}

单边循环法

思路

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

复杂度分析

归并排序

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];
        }
    }
}

•  时间复杂度：。

• 空间复杂度：。