1.给你一个整数数组 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]
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/sort-an-array
题解来源：
作者：bryansun2020
链接：https://leetcode-cn.com/problems/sort-an-array/solution/shi-er-chong-pai-xu-suan-fa-bao-ni-man-yi-dai-gift/
来源：力扣（LeetCode）
方法一：冒泡排序
冒泡排序是从左到右依次比较相邻的两个元素，如果前一个元素比较大，就把前一个元素和后一个交换位置，遍历数组之后保证最后一个元素相对于前面的永远是最大的。然后让最后一个保持不变，重新遍历前n-1个元素，保证第n-1个元素在前n-1个元素里面是最大的。依此规律直到第2个元素是前2个元素里面最大的，排序就结束了。因为这个排序的过程很像冒泡泡，找到最大的元素不停的移动到最后端，所以这个排序算法就叫冒泡排序。（时间n方，空间1，稳定）

private void bubbleSort(int[] nums) {
    for (int i = nums.length - 1; i >= 1; i--) { // 冒泡得到n-1个最大值
        for (int j = 1; j <= i; j++) {
            if (nums[j-1]>nums[j])
                swap(nums, j, j-1);           // 交换得到较大值
        }
    }
}

方法二：选择排序
选择排序的思路比较简单，先找到前n个元素中最大的值，然后和最后一个元素交换，这样保证最后一个元素一定是最大的，然后找到前n-1个元素中的最大值，和第n-1个元素进行交换，然后找到前n-2个元素中最大值，和第n-2个元素交换，依次类推到第2个元素，这样就得到了最后的排序数组。（时间n方，空间1，不稳定）

private void selectionSort(int[] nums) {
    for (int i = nums.length - 1; i > 0; i--) {
        int maxIndex = 0;         // 最大元素的位置
        for (int j = 0; j <= i; j++) {
            if (nums[maxIndex]<nums[j]) {
                maxIndex = j;
            }
        }
        swap(nums, maxIndex, i);   // 把这个最大的元素移到最后
    }
}

方法三：插入排序
插入排序的核心思想是遍历整个数组，保持当前元素左侧始终是排序后的数组，然后将当前元素插入到前面排序完成的数组的对应的位置，使其保持排序状态。有点动态规划的感觉，类似于先把前i-1个元素排序完成，再插入第i个元素，构成i个元素的有序数组。（最好情况时间是n其余情况n方，空间1，稳定）

private void insertionSort(int[] nums) {
    for (int i = 1; i < nums.length; i++) {   // 从第二个元素开始遍历
        int j = i;
        while (j>0&&nums[j]<nums[j-1]) {     // 将当前元素移动到合适的位置
            swap(nums, j, j-1);
            j--;
        }
    }
}

方法四：希尔排序
希尔排序可以看作是一个冒泡排序或者插入排序的变形。希尔排序在每次的排序的时候都把数组拆分成若干个序列，一个序列的相邻的元素索引相隔的固定的距离gap，每一轮对这些序列进行冒泡或者插入排序，然后再缩小gap得到新的序列一一排序，直到gap为0
比如对于数组[5,2,4,3,1,2]，第一轮gap=3拆分成[5,3]、[2,1]和[4,2]三个数组进行插入排序得到[3,1,2,5,2,4]；第二轮gap=1，拆分成[3,2,2]和[1,5,4]进行插入排序得到[2,1,2,4,3,5]；最后gap=0，全局插入排序得到[1,2,2,3,4,5]。（时间介于n方和n4/3之间，不稳定，空间为1）

private void shellSor2(int[] nums) {
    int gap = nums.length >> 1;
    while (gap > 0) {
        for (int i = 0; i < gap; i++) {                        // 对每个子序列进行排序
            for (int j = i+gap; j < nums.length; j+=gap) {     // 插入排序的部分
                int temp = j;
                while (temp > i && nums[temp] < nums[temp-gap]) {
                    swap(nums, temp, temp-gap);
                    temp -= gap;
                }
            }
        }
        gap >>= 1;
    }
}

方法五：归并排序
归并排序是典型的使用分治思想（divide-and-conquer）解决问题的案例。在排序的过程中，把原来的数组变成左右两个数组，然后分别进行排序，当左右的子数组排序完毕之后，再合并这两个子数组形成一个新的排序数组。整个过程递归进行，当只剩下一个元素或者没有元素的时候就直接返回。（时间是ologn，空间是n，稳定算法）

private void mergeSort(int[] nums, int left, int right) {  // 需要左右边界确定排序范围
    if (left >= right) return;
    int mid = (left+right) / 2;

    mergeSort(nums, left, mid);                           // 先对左右子数组进行排序
    mergeSort(nums, mid+1, right);

    int[] temp = new int[right-left+1];                   // 临时数组存放合并结果
    int i=left,j=mid+1;
    int cur = 0;
    while (i<=mid&&j<=right) {                            // 开始合并数组
        if (nums[i]<=nums[j]) temp[cur] = nums[i++];
        else temp[cur] = nums[j++];
        cur++;
    }
    while (i<=mid) temp[cur++] = nums[i++];
    while (j<=right) temp[cur++] = nums[j++];

    for (int k = 0; k < temp.length; k++) {             // 合并数组完成，拷贝到原来的数组中
        nums[left+k] = temp[k];
    }
}

方法六：快速排序
其核心的思路是取第一个元素（或者最后一个元素）作为分界点，把整个数组分成左右两侧，左边的元素小于或者等于分界点元素，而右边的元素大于分界点元素，然后把分界点移到中间位置，对左右子数组分别进行递归，最后就能得到一个排序完成的数组。当子数组只有一个或者没有元素的时候就结束这个递归过程。（时间nlogn，空间logn,不稳定）

private void quickSort(int[] nums, int left, int right) {
    if (left >= right) return;
    int lo = left+1;               // 小于分界点元素的最右侧的指针
    int hi = right;                // 大于分界点元素的最左侧的指针
    while (lo<=hi) {
        if (nums[lo]>nums[left]) { // 交换元素确保左侧指针指向元素小于分界点元素
            swap(nums, lo, hi);
            hi--;
        } else {
            lo++;
        }
    }
    lo--;                          // 回到小于分界点元素数组的最右侧
    swap(nums, left, lo);          // 将分界点元素移到左侧数组最右侧
    quickSort2(nums, left, lo-1);
    quickSort2(nums, lo+1, right);
}