梦回基础排序算法 冒泡 选择 插入

冒泡排序、选择排序和插入排序的时间复杂度都是: O(n^2)

冒泡排序

思路:

1. 把最大值丢到最右边, 次大值丢到次右边...
2. 第一次是全数组(length-1)比较, 才能保证最右边是最大的,第二次只需进行(length-2)次比较, 将次大的放到从右往左第二个位置, 以此类推
3. 外层for循环条件为i=1,i<nums.length, 从1开始是因为总共只需进行length-1次循环, i<nums.length表示将length-1个元素丢到右边即可完成排序
4. 内层循环每一次都从j=0开始, 进行 (数组长度-i) 次运算, i为已经在最右边排好序的元素个数, 比较nums[j]和nums[j+1], 将较大者一路交换抛到(length-i)的地方

java代码实现:

    public int[] bubbleSort(int[] nums){
            for (int i = 1; i < nums.length; i++) {
            // 新增变量，表示数组没有进行交换，也就是数据已经排序，若未发生交换直接break
            boolean hasChanged = false;

            for (int j = 0; j < nums.length - i; j++) {
                if (nums[j] > nums[j + 1]) {
                    int tmp = nums[j];
                    nums[j] = nums[j + 1];
                    nums[j + 1] = tmp;

                    hasChanged = true;
                }
            }

            if (!hasChanged) {
                break;
            }
        }
        return nums;
    }

选择排序

思路:

1. 选择排序和冒泡排序相反, 冒泡排序是把最大值丢到右边, 而选择排序是把最小值丢到最左边, 次小值丢到次左边...
2. 第一次是全数组(length-1)比较, 才能保证最左边是最小的,第二次只需进行(length-2)次比较, 将次小的放到从左往右第二个位置, 以此类推
3. 外层for循环条件为i=0,i<nums.length-1, 因为总共只需进行length-1次循环, 也就是将length-1个元素丢到左边即可完成排序
4. 内层循环每一次都从 j=i+1 开始, 前i个已经排好序了, 一直到 j<nums.length, 新增变量min表示最小值的索引位置, 比较nums[j]和nums[min], 最后nums[min]和nums[i]交换

java代码实现:

public int[] selectionSort(int[] nums) {
        // 总共要经过 N-1 轮比较
        for (int i = 0; i < nums.length - 1; i++) {
            int min = i;

            // 每轮需要比较的次数 N-i
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[j] < nums[min]) {
                    // 记录目前能找到的最小值元素的下标
                    min = j;
                }
            }

            // 将找到的最小值和i位置所在的值进行交换
            if (i != min) {
                int tmp = nums[i];
                nums[i] = nums[min];
                nums[min] = tmp;
            }

        }
        return nums;
    }

插入排序

思路:

1. 新增两个变量, tmp用来记录nums[i], j用来记录nums[i]要插入的位置
2. 从左往右循环, 对于元素nums[i], 从i开始, 从右往左一直找到nums[i]要插入的位置(使用while条件), 并且一路做右移一个位置的操作;
3. 找到要插入的位置j, 直接赋值为最初的nums[i]即tmp

特性: 因为i左边的元素都做了右移操作, 所以从i开始的左边都是排好序的

java代码实现:

    public int[] insertSort(int[] nums) {
        // 从下标为1的元素开始选择合适的位置插入，因为下标为0的只有一个元素，默认是有序的
        for (int i = 1; i < nums.length; i++) {
            // 记录nums[i], 这是要处理的数据
            int tmp = nums[i];

            int j = i;
            // 如果arr[j]比tmp大,则将arr[j]右移一位
            while (j > 0 && tmp < nums[j - 1]) {
                nums[j] = nums[j - 1];
                j--;
            }

            // j发生了变化, 说明数组有部分数据发生了向右移动一位的动作, 将tmp插入数组右移让出来的位置
            if (j != i) {
                nums[j] = tmp;
            }
        }
        return nums;
    }