简单排序算法

冒泡排序

冒泡排序是一种交换类排序算法。它的核心思想是通过重复走访要排序的数列，依次比较相邻的两个元素。如果它们的顺序错误（比如前面的比后面的大），就交换过来。就像水底的气泡一样，越大的元素会经由交换慢慢 “浮” 到数列的顶端。冒泡排序虽然在处理大规模乱序数据时效率较低，但它具有实现简单、不占额外内存且保持顺序稳定的优点。它是理解算法思维、循环控制逻辑以及 “空间换时间” 优化理念的最佳入门案例。

冒泡排序演示
当前状态: 准备就绪 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
 * 冒泡排序
 * 时间复杂度：O(n^2)
 * 稳定性：稳定
 */
public static void bubbleSort(Comparable[] array) {
    for (int i = array.length-1; i > 0; i--) {
        boolean needNext = false;
        for (int j = 0; j < i; j++) {
            if (array[j].compareTo(array[j+1]) > 0) { // 比较
                needNext = true;
                swap(array, j, j+1); // 交换
            }
        }
        if (!needNext) { // 如果不存在交换，则算法结束
            break;
        }
    }
}

可以做的两个优化点：

  • 标志位优化（NeedNext）：记录当前轮次是否发生了交换。若未交换，说明数组已有序，直接提前终止。
  • 记录最后交换位置：进一步精确下一轮扫描的范围（请读者自行实现试试 ^_^）。


选择排序

排序的原理：

  1. 每一次遍历的过程中，都假定第一个索引处的元素是最小值，和其他索引处的值依次比较，如果当前索引处的值大于其他某个索引处的值，则假定其他某个索引处的值为最小值，最后可以找到最小值所在的索引。
  2. 交换第一个索引处和最小值所在的索引处的值。

一般情况下，选择排序比冒泡排序的交换次数更少。在冒泡排序中，为了把最大的数挪到末尾，可能需要一路交换十几次。而在选择排序中，无论数组多乱，每一轮内层循环只为了寻找那个“天选之子”的索引，最后只动手交换一次。但排序算法是不稳定的，本质上是因为长距离的交换可能会破坏相同元素的相对顺序。举个栗子：假设数组是 {5, 5, 2}（为了区分，我们叫它们 5a, 5b,2）。

  1. 第一轮扫描，发现最小值是 2。
  2. 2 与第一个位置的 5a 交换。
  3. 数组变成了 {2, 5b, 5a}。


选择排序演示
当前状态: 准备就绪 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
 * 选择排序
 * 时间复杂度：O(n^2)
 * 稳定性：不稳定
 */
public static void selectSort(Comparable[] array) {
    for (int i = 0; i < array.length-1; i++) {
        int selectIndex = i;
        for (int j = i+1; j < array.length; j++) {
            if (array[j].compareTo(array[selectIndex]) < 0) { // 比较
                selectIndex = j;
            }
        }
        if (selectIndex != i) {
            swap(array, selectIndex, i); // 交换
        }
    }
}


插入排序

插入排序是 O(n^2)​ 家族中最有 “人情味” 的一个。它非常像我们玩扑克牌时整理手牌的过程：右手抓起一张新牌，然后在左手已排好序的牌堆中，从右往左摸索，直到找到它的位置并插进去。排序原理如下：

  1. 把所有的元素分成两组，已经排好序的和未排序的；
  2. 找到未排序的第一个元素，向已经排序的组中进行插入；
  3. 倒序遍历已经排序的元素，依次和待插入的元素进行比较，直到找到一个元素小于等于待插入的元素，那么就把这个元素放到这个位置，其他的元素向后移一位。

虽然它的平均时间复杂度也是 O(n^2)，但在实际应用中，它往往比冒泡和选择排序表现得更好。

  • 适应性：如果数组本身已经接近有序，插入排序的效率极高。在最好情况下，它只需要 O(n) 时间。
  • 稳定性：”if (array[j] < array[j-1])” 保证只有在严格小于时才交换，相等元素不会变位置，因此它是稳定的。
  • 在线算法：它可以在接收新数据的同时进行排序，不需要等所有数据到齐。
插入排序演示
当前状态: 准备就绪 
1
2
3
4
5
6
7
8
9
10
11
12
/**
 * 插入排序
 * 时间复杂度：O(n^2)
 * 稳定性：稳定
 */
public static void insertSort(int[] array) {
    for (int i = 1; i < array.length; i++) {
        for (int j = i; j > 0 && array[j] < array[j-1]; j--) {
            swap(array, j, j-1);
        }
    }
}

我们注意到，在 Java 的 Arrays.sort() 或者其他语言的底层库中，针对小规模数据（比如 n \< 47），往往会优先选择插入排序而不是快速排序。原因就在于插入排序代码极其简单，没有递归开销，且对于接近有序的数据有几乎 O(n)​ 的表现，这在处理小规模数据时比快速排序更稳。


标题：
简单排序算法
作者：
kinglyjn
声明：
引用 本文 请务必注明出处，原创不易，感谢尊重。