力扣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]

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/sort-an-array
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

首先，我用的是冒泡排序法（目前只知道这种），但是最后一个没通过（数字特别多），有限时间内不能得到结果，代码如下。

class Solution {
    public int[] sortArray(int[] nums) {
        int a = 0;
        for(int i=0;i<nums.length-1;i++){
            //一共进行num.length次循环排序
            boolean b=false;//这里用bool值以便减少不必要的循环次数
            for(int j=0;j<nums.length-1-i;j++){
            //每次排序都会把最大值移动到最右端，所以下一次右边的都不用排序，进行nums.length-1-i轮循环
                if(nums[j+1]<nums[j]){
                    a=nums[j];
                    nums[j]=nums[j+1];
                    nums[j+1]=a;
                    b=true;
                }
            //进行大小值换位
            }
            if(b==false){
                break;
            }
            //用bool值来判断此轮循环是否有必要，没必要则跳出循环
        }
        
        return nums;
    }
}

在题解中了解到了选择排序法，但是试过这种方法还是过不了，时间太久，感觉和冒泡排序法有相似之处，代码如下。

class Solution {


    // 选择排序：每一轮选择最小元素交换到未排定部分的开头

    public int[] sortArray(int[] nums) {
        int len = nums.length;
        // 循环不变量：[0, i) 有序，且该区间里所有元素就是最终排定的样子
        for (int i = 0; i < len - 1; i++) {
            // 选择区间 [i, len - 1] 里最小的元素的索引，交换到下标 i
            int minIndex = i;
            for (int j = i + 1; j < len; j++) {
                if (nums[j] < nums[minIndex]) {
                    minIndex = j;
                }
            }
            swap(nums, i, minIndex);
        }
        return nums;
    }

    private void swap(int[] nums, int index1, int index2) {
        int temp = nums[index1];
        nums[index1] = nums[index2];
        nums[index2] = temp;
    }
    //交换元素的函数
    




}

然后又了解了插入排序法

优化：「将一个数字插入一个有序的数组」这一步，可以不使用逐步交换，使用先赋值给「临时变量」，然后「适当的元素」后移，空出一个位置，最后把「临时变量」赋值给这个空位的策略

public class Solution {

    // 插入排序：稳定排序，在接近有序的情况下，表现优异

    public int[] sortArray(int[] nums) {
        int len = nums.length;
        // 循环不变量：将 nums[i] 插入到区间 [0, i) 使之成为有序数组
        for (int i = 1; i < len; i++) {
            // 从第二个元素开始，先暂存这个元素，然后之前元素逐个后移，留出空位
            int temp = nums[i];
            int j = i;
            // 注意边界 j > 0 并且当前面的元素比后面的元素（暂存元素）大时，此元素后面的整个数列向后移一位
            while (j > 0 && nums[j - 1] > temp) {
                nums[j] = nums[j - 1];
                j--;
            }
            nums[j] = temp;//此时j为后半部分向后移的数列首个元素下标
        }
        return nums;
    }
}