Boom LeetCode入门（一）复杂度&简单排序算法

发表于 2022-05-04 更新于 2022-05-05 分类于 Boom LeetCode 阅读次数：

前言

BoomLeetCode系列笔记为学习左神视频一周刷爆LeetCode所总结笔记，一共38p，计划每天刷1p，笔记更新进度会比较慢

瑞思拜左神~

文章时间复杂度均按最坏情况下计算

时间复杂度

这部分对于有编程基础的来说不是问题，大体上快速过一遍，先以选择排序中的计算方式给出时间复杂度概念

全部笔记已上传github：

简单排序算法

关于排序算法，另一篇文章请教我学数据结构（一）排序有介绍过，温故知新，看完左神视频后又有了一些新的理解，所以选择再完整记录一次

选择排序

时间复杂度的介绍中大体讲解了选择排序流程，即对于长度为N的数组。从数组下标0开始，寻找当前数组中0-N减1的最小数，放在数组下标0的位置，继续从下标1开始，寻找数组1-N减1的最小数，放在数组下标1的位置。即每一轮查找都有一个数放入最终所在位置。

基于以上思路，编码实现选择排序算法

package p1.sort;

import java.util.Scanner;

public class Code01_SelectionSort {

    public static void main(String[] args) {
//        输入数据处理
        Scanner sc = new Scanner(System.in);
        System.out.println("请输入排序数字个数==========>");
        int n = sc.nextInt();
        int[] nums = new int[n];
        System.out.println("请输入数据============>");
        for (int i = 0; i < n; i++) {
            nums[i]= sc.nextInt();
        }
        selectionSort(nums);
        for (int num : nums) {
            System.out.print(num + " ");
        }

    }

    //选择排序主体
    public static void selectionSort(int[] nums){
        if(nums == null || nums.length < 2){
            return;
        }
        for(int i = 0; i < nums.length - 1; i++){
            int minIndex = i;
            for(int j = i + 1; j < nums.length; j++){
                minIndex = nums[j] < nums[minIndex] ? j : minIndex;
            }
            if(minIndex != i){
                swap(nums, i, minIndex);
            }
        }
    }

    //数组位置交换
    public static void swap(int[] nums, int i, int j){
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }


}

时间复杂度

额外空间复杂度O(1)

冒泡排序

冒泡排序大体思路如下：

实现代码：

package p1.sort;

import java.util.Scanner;

//冒泡排序
public class Code02_BubbleSort {

    //Main处理输入输出
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.println("请输入排序数字个数==========>");
        int n = sc.nextInt();
        int[] nums = new int[n];
        System.out.println("请输入数据============>");
        for (int i = 0; i < n; i++) {
            nums[i]= sc.nextInt();
        }
        bubbleSort(nums);
        for (int num : nums) {
            System.out.print(num + " ");
        }
    }

    //冒泡排序核心思路
    public static void bubbleSort(int[] nums){
        if(nums == null || nums.length < 2){
            return;
        }
        for(int i = nums.length - 1; i>0; i--){
            for(int j = 0; j < i; j++){
                if(nums[j] > nums[j+1]){
                    swap(nums, j);
                }
            }
        }
    }

    //交换数组前后位置数据
//    public static void swap(int[] nums, int i){
//        int temp = nums[i+1];
//        nums[i+1] = nums[i];
//        nums[i] = temp;
//    }
    //异或运算交换元素位置,不推荐使用
    public static void swap(int[] nums, int i){
        nums[i] = nums[i] ^ nums[i + 1];
        nums[i + 1] = nums[i + 1] ^ nums[i];
        nums[i] = nums[i] ^ nums[i + 1];
    }
}

时间复杂度

额外空间复杂度O(1)

其中对于异或运算实现数组元素交换，其原理为：

插入排序

插入排序思路如↓

实现代码：

package p1.sort;

import java.util.Scanner;

public class Code03_InsertionSort {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.println("请输入排序数字个数==========>");
        int n = sc.nextInt();
        int[] nums = new int[n];
        System.out.println("请输入数据============>");
        for (int i = 0; i < n; i++) {
            nums[i]= sc.nextInt();
        }
        insertionSort(nums);
        for (int num : nums) {
            System.out.print(num + " ");
        }
    }

    // 插入排序核心思路
    private static void insertionSort(int[] nums) {
        if(nums == null || nums.length < 2){
            return;
        }
        for (int i = 1; i < nums.length; i++) {
            for(int j = i; j > 0; j--){
                if(nums[j-1] < nums[j]){
                    break;
                }
                swap(nums, j);
            }
        }
    }

    private static void swap(int[] nums, int j) {
        int temp = nums[j];
        nums[j] = nums[j - 1];
        nums[j - 1] = temp;
    }
}