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

    1. 冒泡排序（Bubble Sort）

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

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

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

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

    1. 第一轮：

      • 比较 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  已经排在最后。

    2. 第二轮：

      • 比较 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，不交换位置。
      • 第二轮结束。

    3. 依此类推，直到数组完全排序。

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

    2. 插入排序（Insertion Sort）

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

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

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

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

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

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

    3. 选择排序（Selection Sort）

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

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

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

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

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

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

    4. 使用 Java 代码实现

    1. 冒泡排序 ： 
      1. public class BubbleSort {
      2.     // 冒泡排序方法
      3.     public static void bubbleSort(int[] arr) {
      4.         int n = arr.length;
      5.         // 外层循环控制比较轮数
      6.         for (int i = 0; i < n - 1; i++) {
      7.             // 内层循环执行相邻元素比较并交换
      8.             for (int j = 0; j < n - i - 1; j++) {
      9.                 // 如果前一个元素大于后一个元素，则交换它们
      10.                 if (arr[j] > arr[j + 1]) {
      11.                     int temp = arr[j];
      12.                     arr[j] = arr[j + 1];
      13.                     arr[j + 1] = temp;
      14.                 }
      15.             }
      16.         }
      17.     }
      18.  
      19.     public static void main(String[] args) {
      20.         int[] arr = {64, 34, 25, 12, 22, 11, 90};
      21.         // 调用冒泡排序方法对数组进行排序
      22.         bubbleSort(arr);
      23.         System.out.println("冒泡排序后的数组：");
      24.         // 输出排序后的数组
      25.         for (int num : arr) {
      26.             System.out.print(num + " ");
      27.         }
      28.     }
      29. }
    2. 插入排序 ： 
      1. public class InsertionSort {
      2.     // 插入排序方法
      3.     public static void insertionSort(int[] arr) {
      4.         int n = arr.length;
      5.         // 从第二个元素开始遍历数组
      6.         for (int i = 1; i < n; i++) {
      7.             int key = arr[i];
      8.             int j = i - 1;
      9.             // 将当前元素插入到已排序序列的合适位置
      10.             while (j >= 0 && arr[j] > key) {
      11.                 arr[j + 1] = arr[j];
      12.                 j--;
      13.             }
      14.             arr[j + 1] = key;
      15.         }
      16.     }
      17.  
      18.     public static void main(String[] args) {
      19.         int[] arr = {64, 34, 25, 12, 22, 11, 90};
      20.         // 调用插入排序方法对数组进行排序
      21.         insertionSort(arr);
      22.         System.out.println("插入排序后的数组：");
      23.         // 输出排序后的数组
      24.         for (int num : arr) {
      25.             System.out.print(num + " ");
      26.         }
      27.     }
      28. }
    3. 选择排序 ： 
      1. public class SelectionSort {
      2.     // 选择排序方法
      3.     public static void selectionSort(int[] arr) {
      4.         int n = arr.length;
      5.         // 外层循环控制当前轮次需要找到的最小元素的位置
      6.         for (int i = 0; i < n - 1; i++) {
      7.             int minIndex = i;
      8.             // 内层循环找到未排序部分的最小元素的索引
      9.             for (int j = i + 1; j < n; j++) {
      10.                 if (arr[j] < arr[minIndex]) {
      11.                     minIndex = j;
      12.                 }
      13.             }
      14.             // 将找到的最小元素与当前位置交换
      15.             int temp = arr[minIndex];
      16.             arr[minIndex] = arr[i];
      17.             arr[i] = temp;
      18.         }
      19.     }
      20.  
      21.     public static void main(String[] args) {
      22.         int[] arr = {64, 34, 25, 12, 22, 11, 90};
      23.         // 调用选择排序方法对数组进行排序
      24.         selectionSort(arr);
      25.         System.out.println("选择排序后的数组：");
      26.         // 输出排序后的数组
      27.         for (int num : arr) {
      28.             System.out.print(num + " ");
      29.         }
      30.     }
      31. }

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

    1. 插入排序（Insertion Sort）：效率高，特别适合部分有序的数组。
    2. 选择排序（Selection Sort）：性能一般，介于冒泡排序和插入排序之间。
    3. 冒泡排序（Bubble Sort）：效率较低，不推荐在大规模数据集上使用。
  • 相关阅读:
    java计算机毕业设计校园环境保护监督系统源代码+系统+数据库+lw文档
    ES6面向对象
    mysql性能分析
    leetcode&lintcode分类刷题：图论（三、多源最小距离问题）
    Rust Vs Go:从头构建一个web服务
    MyBatis基本操作及SpringBoot单元测试
    PyTorch深度学习实战（11）——卷积神经网络
    WindowsAPI 进程和线程相关说明
    服用5年份筑基丹 - Vue篇
    第10章 MySQL（一）
  • 原文地址：https://blog.csdn.net/DaPiCaoMin/article/details/137397769