一、冒泡排序

1.基本概念

冒泡排序是一种简单的排序算法，其基本思想是：在待排序的一组数中，将相邻的两个数进行比较，若前面的数比后面的数大就交换两数，否则不交换；如此下去，直至最终完成排序 。由此可得，在排序过程中，大的数据往下沉，小的数据往上浮，就像气泡一样，于是将这种排序算法形象地称为冒泡排序。

2.算法逻辑

• 依次比较相邻元素，前大后小则交换
• 每轮遍历将最大值排到末尾
• 重复n-1轮完成排序

3.特点

• 时间复杂度

平均时间复杂度	最好情况	最坏情况	稳定性
O(n²)	O(n)	O(n²)	稳定

4.图解

图片来自：https://visualgo.net/en/sorting

5.完整代码

• 基本代码

		// 冒泡排序
        for (int j = 0; j < len - 1; j++) {
            for (int i = 0; i < len - 1; i++) {
                if (arr[i] > arr[i + 1]) {
                	//交换
                    int temp = arr[i];
                    arr[i] = arr[i + 1];
                    arr[i + 1] = temp;
                }
            }
        }
        // 输出排序好的数组
        System.out.print("[");
        for (int i = 0; i < len; i++) {
            System.out.print(" " + arr[i]);
        }
        System.out.println("]");

• 优化代码

        // 冒泡排序
        for (int j = 0; j < len - 1; j++) {
            int n = 0;// 每次开始一轮排序 初始化一个变量 标记后面的循环是否交换数据
            for (int i = 0; i < len - 1-j; i++) {
                if (arr[i] > arr[i + 1]) {
                	//交换
                    int temp = arr[i];
                    arr[i] = arr[i + 1];
                    arr[i + 1] = temp;
                    n++;// 标记是否交换了数据
                }
            }
            // 如果没有发生交换，说明数组已经有序，提前结束
            if(n==1){
                System.out.println("排序完成");
                break;
            }

        }
      // 输出排序好的数组
        System.out.print("[");
        for (int i = 0; i < len; i++) {
            System.out.print(" " + arr[i]);
        }
        System.out.println("]");

二、选择排序

1.基本概念

选择排序法是一种不稳定的排序算法。它的工作原理是每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到全部待排序的数据元素排完。

2.算法逻辑

• 在未排序序列中找到最小元素
• 将选中的最小元素直接放到正确位置
• 重复上述过程直到排序完成

3.特点

• 时间复杂度

平均时间复杂度	最好情况	最坏情况	稳定性
O(n²)	O(n²)	O(n²)	不稳定

4.图解

图片来自：https://visualgo.net/en/sorting

5.完整代码

        //选择排序
        for (int i = 0; i < len - 1; i++) {
            //假设第i位元素为最小元素
            int min = i;
            //遍历未排序数组，依次与假设最小元素比较，选取真正最小元素
            for (int j = i + 1; j < len; j++) {
                if (arr[j] < arr[min]) {
                    min = j;
                }
            }
            // 交换
            int temp = arr[i];
            arr[i] = arr[min];
            arr[min] = temp;
        }
      // 输出排序好的数组
        System.out.print("[");
        for (int i = 0; i < len; i++) {
            System.out.print(" " + arr[i]);
        }
        System.out.println("]");

三、插入排序

1.基本概念

插入排序是一种简单直观的排序算法。它的工作原理是记录需要插入的元素，检查数组列表中的每个元素，将其插入到一个已经排好序的数列中的适当位置，使数列依然有序，当最后一个元素放入合适位置时，该数组排序完毕。

2.算法逻辑

• 将第一个元素视为已排序序列
• 取出下一个元素，在已排序序列中从后向前扫描
• 找到相应位置插入元素
• 重复步骤2-3，直至数组排列完毕

3.特点

• 时间复杂度

平均时间复杂度	最好情况	最坏情况	稳定性
O(n²)	O(n)	O(n²)	稳定

4.图解

图片来自：https://visualgo.net/en/sorting

5.完整代码

        //插入排序
        for (int i = 1; i < len; i++) {
            // 记录当前要插入的元素
            int num = arr[i]; //默认第一个元素为已排序部分
            int j = i - 1;    // 已排序部分的最后一个元素索引

            // 在已排序部分中寻找插入位置
            while (j >= 0 && arr[j] > num) {
                arr[j + 1] = arr[j]; // 元素后移
                j--;
            }

            // 插入元素到正确位置
            arr[j + 1] = num;
        }
        // 输出排序好的数组
        System.out.print("[");
        for (int i = 0; i < len; i++) {
            System.out.print(" " + arr[i]);
        }
        System.out.println("]");