【JavaSE专栏31】数组排序的三剑客：冒泡排序、选择排序和插入排序

- 日理万妓 2023-10-13 13:23 30阅读 0赞

> **作者主页**：[Designer 小郑][Designer]  
> **作者简介**：Java全栈软件工程师一枚，来自浙江宁波，负责开发管理公司OA项目，专注软件前后端开发（Vue、SpringBoot和微信小程序）、系统定制、远程技术指导。CSDN学院、蓝桥云课认证讲师，全栈领域优质创作者。热爱技术、专注业务、开放合作、乐于分享，期待你我共同成长！  
> **主打方向**：Vue、SpringBoot、微信小程序

本文对 Java 中冒泡排序、选择排序和插入排序进行了介绍，并给出了样例代码。

#### 目录 ####

*  一、冒泡排序
 *  二、选择排序
 *  三、插入排序
 *  四、总结

--------------------

## 一、冒泡排序 ##

![在这里插入图片描述][58fa62651b4b4022b275cc64e9951594.png_pic_center]

**冒泡排序是一种简单的排序算法，通过重复比较相邻的元素并交换位置，使得较大的元素逐渐 `冒泡` 到数组的末尾**。

以下是 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]) {
        
                        // 交换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 i = 0; i < arr.length; i++) {
        
                System.out.print(arr[i] + " ");
            }
        }
    }

该代码首先定义了一个`bubbleSort`方法，接受一个整型数组作为参数，并对该数组进行冒泡排序。

然后在`main`方法中，创建一个示例数组并调用`bubbleSort`方法进行排序，最后输出排序后的数组。

--------------------

## 二、选择排序 ##

![在这里插入图片描述][6792dc18fa64433c81917f7ef823302a.png_pic_center]

**选择排序是一种简单直观的排序算法**，它的基本思想是将待排序的序列分成已排序和未排序两部分，每次从未排序的部分中选择最小（或最大）的元素，将其放到已排序部分的末尾，直到所有元素都排序完成。

以下是使用Java实现选择排序的代码：

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;
                    }
                }
                swap(arr, i, minIndex);
            }
        }
    
        private static void swap(int[] arr, int i, int j) {
        
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    
        public static void main(String[] args) {
        
            int[] arr = {
        64, 25, 12, 22, 11};
            selectionSort(arr);
            System.out.println("排序后的数组：");
            for (int num : arr) {
        
                System.out.print(num + " ");
            }
        }
    }

该代码会输出以下结果：

排序后的数组：
    11 12 22 25 64

--------------------

## 三、插入排序 ##

![在这里插入图片描述][7625059060ac4fbfbc2846767fefe36b.png_pic_center]

在计算机科学中，排序是将一组元素按照特定的规则重新排列的过程。

**排序算法可以按照不同的规则来排序**，例如按照数字大小、字母顺序等。

排序算法的应用非常广泛，可以用于数据处理、搜索算法优化等领域。

以下是一个使用 Java 实现的插入排序代码样例。

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 = j - 1;
                }
                arr[j + 1] = key;
            }
        }
      
        public static void main(String[] args) {
        
            int[] arr = {
         12, 11, 13, 5, 6 };
      
            System.out.println("排序前的数组：");
            for (int num : arr) {
        
                System.out.print(num + " ");
            }
      
            insertionSort(arr);
      
            System.out.println("
    排序后的数组：");
            for (int num : arr) {
        
                System.out.print(num + " ");
            }
        }
    }

以上代码使用**插入排序算法**对一个整数数组进行排序。

**插入排序的基本思想是将数组分为已排序和未排序两部分，每次从未排序部分取出一个元素，在已排序部分找到合适的位置插入，重复这个步骤直到整个数组有序**。

插入排序的应用场景包括但不限于以下三类。

1.  **对小规模数据进行排序**，因为插入排序的时间复杂度为  O ( n 2 ) O(n^2) O(n2)，对于大规模数据效率较低。
2.  **部分数据已经有序或接近有序**，插入排序对此类数据的排序效果较好。
3.  **稳定性要求较高的场景**，插入排序是一种稳定的排序算法，即相等元素的相对位置不会改变。

> 提示：实际使用时应根据具体场景选择更适合的排序算法。

--------------------

## 四、总结 ##

本文对 Java 中冒泡排序、选择排序和插入排序进行了介绍，并给出了样例代码。在下一篇博客中，将讲解 Java 中函数定义、调用和主函数的语法。

![在这里插入图片描述][3a01dc60e62c415b812015851343f1c0.png_pic_center]

[Designer]: https://blog.csdn.net/qq_41464123
[58fa62651b4b4022b275cc64e9951594.png_pic_center]: https://img-blog.csdnimg.cn/58fa62651b4b4022b275cc64e9951594.png#pic_center
[6792dc18fa64433c81917f7ef823302a.png_pic_center]: https://img-blog.csdnimg.cn/6792dc18fa64433c81917f7ef823302a.png#pic_center
[7625059060ac4fbfbc2846767fefe36b.png_pic_center]: https://img-blog.csdnimg.cn/7625059060ac4fbfbc2846767fefe36b.png#pic_center
[3a01dc60e62c415b812015851343f1c0.png_pic_center]: https://img-blog.csdnimg.cn/3a01dc60e62c415b812015851343f1c0.png#pic_center