蓝桥杯备考随手记: 常用的三种排序算法（冒泡排序、插入排序、选择排序）

1. 冒泡排序（Bubble Sort）

冒泡排序是一种简单直观的排序算法，在待排序序列中不断地交换相邻两个元素的位置，通过多次遍历，将最大（或最小）的元素逐渐向右（或左）移动到正确的位置，直到整个序列有序。

冒泡排序的基本思想如下：

从序列的第一个元素开始，比较相邻两个元素的大小。
如果前一个元素大于后一个元素，则交换它们的位置，将较大的元素向右移动。
继续比较下一个相邻的元素，重复上述步骤，直到遍历到序列的最后一个元素。
重复以上步骤，直至整个序列有序。

给定数组 A=[64,34,25,12,22,11,90]，冒泡排序的过程如下：

第一轮：
- 比较 64 和 34，交换位置，数组变为 [34,64,25,12,22,11,90]。
- 继续比较 64 和 25，交换位置，数组变为 [34,25,64,12,22,11,90]。
- 继续比较 64 和 12，交换位置，数组变为 [34,25,12,64,22,11,90]。
- 继续比较 64 和 22，交换位置，数组变为 [34,25,12,22,64,11,90]。
- 继续比较 64 和 11，交换位置，数组变为 [34,25,12,22,11,64,90]。
- 最后比较 64 和 90，不交换位置。
- 第一轮结束，最大值 90 已经排在最后。
第二轮：
- 比较 34 和 25，交换位置，数组变为 [25,34,12,22,11,64,90]。
- 继续比较 34 和 12，交换位置，数组变为 [25,12,34,22,11,64,90]。
- 继续比较 34 和 22，交换位置，数组变为 [25,12,22,34,11,64,90]。
- 继续比较 34 和 11，交换位置，数组变为 [25,12,22,11,34,64,90]。
- 最后比较 34 和 64，不交换位置。
- 第二轮结束。
依此类推，直到数组完全排序。

冒泡排序的时间复杂度为O(n^2)，其中n表示待排序序列的长度。冒泡排序是稳定的，因为相同元素的相对顺序不会发生改变。

2. 插入排序（Insertion Sort）

插入排序是一种简单且直观的排序算法，将待排序序列分为已排序和未排序两部分，每次从未排序的部分中取出一个元素插入到已排序的正确位置，直到整个序列有序。

插入排序的基本思想如下：

从待排序序列中选择一个元素，将其插入到已排序序列的合适位置上。
从已排序序列的末尾开始，将比当前元素大的元素向右移动，腾出插入位置。
将当前元素插入到合适的位置上，使已排序序列依然有序。
重复以上步骤，直到未排序序列中的所有元素都插入到已排序序列中。

给定数组 A=[64,34,25,12,22,11,90]，插入排序的过程如下：

第一轮：
- 将第二个元素 34 插入到已排序子数组 [64] 的合适位置，数组变为 [34,64,25,12,22,11,90]。
第二轮：
- 将第三个元素 25 插入到已排序子数组 [34,64] 的合适位置，数组变为 [25,34,64,12,22,11,90]。
依此类推，直到数组完全排序。

插入排序的时间复杂度为O(n^2)，其中n表示待排序序列的长度。插入排序是稳定的，因为相同元素的相对顺序不会发生改变。

3. 选择排序（Selection Sort）

选择排序是一种简单直观的排序算法，每次从待排序序列中选择最小（或最大）的元素，放到已排序序列的末尾，直到整个序列有序。

选择排序的基本思想如下：

将待排序序列分为已排序和未排序两部分，初始时已排序序列为空。
从未排序序列中选择最小（或最大）的元素，将其与未排序序列的第一个元素交换位置，即将最小（或最大）的元素放到已排序序列的末尾。
将已排序序列的末尾后移一位，将未排序序列缩小一个元素。
重复以上步骤，直到未排序序列中的所有元素都被加入到已排序序列中。

给定数组 A=[64,34,25,12,22,11,90]，选择排序的过程如下：

第一轮：
- 从数组中选择最小值 11，与第一个元素 64 交换位置，数组变为 [11,34,25,12,22,64,90]。
第二轮：
- 从第二个元素开始的子数组中选择最小值 12，与第二个元素 34 交换位置，数组变为 [11,12,25,34,22,64,90]。
依此类推，直到数组完全排序。

选择排序的时间复杂度为O(n^2)，其中n表示待排序序列的长度。选择排序是不稳定的，因为相同元素的相对顺序可能会发生改变。

4. Java 代码实现

冒泡排序：

public class BubbleSort {
    // 冒泡排序方法
    public static void bubbleSort(int[] arr) {
        int n = arr.length;
        // 外层循环控制比较轮数
        for (int i = 0; i < n - 1; i++) {
            // 内层循环执行相邻元素比较并交换
            for (int j = 0; j < n - i - 1; j++) {
                // 如果前一个元素大于后一个元素，则交换它们
                if (arr[j] > arr[j + 1]) {
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
    }

    public static void main(String[] args) {
        int[] arr = {64, 34, 25, 12, 22, 11, 90};
        // 调用冒泡排序方法对数组进行排序
        bubbleSort(arr);
        System.out.println("冒泡排序后的数组：");
        // 输出排序后的数组
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

插入排序：

public class InsertionSort {
    // 插入排序方法
    public static void insertionSort(int[] arr) {
        int n = arr.length;
        // 从第二个元素开始遍历数组
        for (int i = 1; i < n; i++) {
            int key = arr[i];
            int j = i - 1;
            // 将当前元素插入到已排序序列的合适位置
            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j];
                j--;
            }
            arr[j + 1] = key;
        }
    }

    public static void main(String[] args) {
        int[] arr = {64, 34, 25, 12, 22, 11, 90};
        // 调用插入排序方法对数组进行排序
        insertionSort(arr);
        System.out.println("插入排序后的数组：");
        // 输出排序后的数组
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

选择排序：

public class SelectionSort {
    // 选择排序方法
    public static void selectionSort(int[] arr) {
        int n = arr.length;
        // 外层循环控制当前轮次需要找到的最小元素的位置
        for (int i = 0; i < n - 1; i++) {
            int minIndex = i;
            // 内层循环找到未排序部分的最小元素的索引
            for (int j = i + 1; j < n; j++) {
                if (arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }
            // 将找到的最小元素与当前位置交换
            int temp = arr[minIndex];
            arr[minIndex] = arr[i];
            arr[i] = temp;
        }
    }

    public static void main(String[] args) {
        int[] arr = {64, 34, 25, 12, 22, 11, 90};
        // 调用选择排序方法对数组进行排序
        selectionSort(arr);
        System.out.println("选择排序后的数组：");
        // 输出排序后的数组
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}

在选择三种排序算法时，一般的算法优先选择顺序是：

插入排序（Insertion Sort）：效率高，特别适合部分有序的数组。
选择排序（Selection Sort）：性能一般，介于冒泡排序和插入排序之间。
冒泡排序（Bubble Sort）：效率较低，不推荐在大规模数据集上使用。

原文链接：https://blog.csdn.net/DaPiCaoMin/article/details/137397769

蓝桥杯备考随手记: 常用的三种排序算法（冒泡排序、插入排序、选择排序）

1. 冒泡排序（Bubble Sort）

2. 插入排序（Insertion Sort）

3. 选择排序（Selection Sort）

4. Java 代码实现

相关推荐