11 | 排序（上）：为什么插入排序比冒泡排序更受欢迎

作者：鲁米

2023-12-04
北京
本文字数：3297 字
阅读完需：约 11 分钟

如何分析一个“排序算法”？

排序算法是对一组数据按照某种规则进行有序排列的算法。在选择合适的排序算法时，需要考虑算法的时间复杂度、空间复杂度、稳定性以及适用场景等因素。以下是分析排序算法时需要考虑的关键点：

1. 时间复杂度

时间复杂度是评估算法执行效率的重要指标。常见的时间复杂度有 O(n^2)、O(n log n)、O(n) 等。不同的排序算法在不同情况下有不同的时间复杂度。

最好情况、平均情况和最坏情况： 一些排序算法在最好、平均和最坏情况下的时间复杂度可能不同，需要根据实际应用场景选择合适的算法。

2. 空间复杂度

空间复杂度是指算法在执行过程中所需的额外空间。原地排序算法在排序过程中不需要额外的空间，而一些算法可能需要额外的空间。

3. 稳定性

稳定性是指排序算法在排序过程中是否保持相同元素的相对顺序不变。在某些应用场景中，需要保持相同元素的相对顺序，这时稳定性就成为一个重要的考虑因素。

4. 适用场景

不同的排序算法适用于不同的场景。例如，快速排序适用于大规模数据的排序，冒泡排序适用于小规模数据的排序。选择合适的算法可以提高排序的效率。

5. 实现细节

具体实现细节包括算法的编程复杂度、代码可读性等。清晰简洁的实现有助于代码的维护和调试。

6. 排序稳定性举例

以下是几种常见排序算法的特点：

冒泡排序（Bubble Sort）： 稳定，原地排序。

  public class BubbleSort {        public static void bubbleSort(int[] array) {          int n = array.length;            for (int i = 0; i < n - 1; i++) {              for (int j = 0; j < n - i - 1; j++) {                  // 如果当前元素大于下一个元素，则交换它们                  if (array[j] > array[j + 1]) {                      // 交换array[j]和array[j + 1]                      int temp = array[j];                      array[j] = array[j + 1];                      array[j + 1] = temp;                  }              }          }      }        public static void printArray(int[] array) {          for (int num : array) {              System.out.print(num + " ");          }          System.out.println();      }        public static void main(String[] args) {          int[] array = {64, 34, 25, 12, 22, 11, 90};            System.out.println("未排序数组：");          printArray(array);            bubbleSort(array);            System.out.println("冒泡排序后的数组：");          printArray(array);      }  }

复制代码

插入排序（Insertion Sort）： 稳定，原地排序。

  public class InsertionSort {        public static void insertionSort(int[] array) {          int n = array.length;            for (int i = 1; i < n; i++) {              int currentElement = array[i];              int j = i - 1;                // 移动已排序部分中的元素，找到适当的位置插入当前元素              while (j >= 0 && array[j] > currentElement) {                  array[j + 1] = array[j];                  j--;              }                // 插入当前元素到正确的位置              array[j + 1] = currentElement;          }      }        public static void printArray(int[] array) {          for (int num : array) {              System.out.print(num + " ");          }          System.out.println();      }        public static void main(String[] args) {          int[] array = {12, 11, 13, 5, 6};            System.out.println("未排序数组：");          printArray(array);            insertionSort(array);            System.out.println("插入排序后的数组：");          printArray(array);      }  }

复制代码

选择排序（Selection Sort）： 不稳定，原地排序。

  public class SelectionSort {        public static void selectionSort(int[] array) {          int n = array.length;            // 遍历数组          for (int i = 0; i < n - 1; i++) {              // 找到未排序部分的最小元素的索引              int minIndex = i;              for (int j = i + 1; j < n; j++) {                  if (array[j] < array[minIndex]) {                      minIndex = j;                  }              }                // 将找到的最小元素与未排序部分的第一个元素交换位置              int temp = array[minIndex];              array[minIndex] = array[i];              array[i] = temp;          }      }        public static void printArray(int[] array) {          for (int num : array) {              System.out.print(num + " ");          }          System.out.println();      }        public static void main(String[] args) {          int[] array = {64, 25, 12, 22, 11};            System.out.println("未排序数组：");          printArray(array);            selectionSort(array);            System.out.println("简单选择排序后的数组：");          printArray(array);      }  }

复制代码

问题区

我们讲过，特定算法是依赖特定的数据结构的。我们今天讲的几种排序算法，都是基于数组实现的。如果数据存储在链表中，这三种排序算法还能工作吗？如果能，那相应的时间、空间复杂度又是多少呢？

冒泡排序和插入排序在最坏情况下的时间复杂度都为 O(n^2)，但插入排序相对更受欢迎的原因有几点：

性能差异： 尽管时间复杂度相同，但插入排序通常在实际执行中比冒泡排序表现更好，因为插入排序每次只需在已排序部分进行线性搜索并找到合适位置，而冒泡排序需要进行多次交换操作。
稳定性： 插入排序是稳定的，相等元素的相对顺序在排序前后保持不变。在某些场景下，稳定性是排序算法的重要考虑因素，而冒泡排序在最坏情况下可能打破相等元素的相对顺序。
提前终止： 插入排序在部分已经有序的情况下表现更好。如果输入数据大部分已经有序，插入排序只需做很少的比较和移动操作，而冒泡排序在这种情况下仍然需要进行多次冒泡。
代码实现简单： 插入排序的实现相对简单，代码量较小，易于理解和维护。冒泡排序的实现相对更复杂，因为它需要进行多次元素交换。

对于链表上的排序算法，这三种排序的适应性和复杂度如下：

冒泡排序在链表上的复杂度：

时间复杂度： O(n^2)。由于链表上的随机访问不如数组高效，冒泡排序在链表上的性能相对较差。
空间复杂度： O(1)。冒泡排序是原地排序算法，不需要额外的空间。

插入排序在链表上的复杂度：

时间复杂度： O(n^2)。在最坏情况下，插入排序需要将每个元素插入到有序链表中，导致总体时间复杂度为 O(n^2)。
空间复杂度： O(1)。插入排序也是原地排序算法，只需要常数级别的额外空间。

选择排序在链表上的复杂度：

时间复杂度： O(n^2)。与冒泡排序类似，选择排序在链表上的性能相对较差。
空间复杂度： O(1)。选择排序也是原地排序算法，不需要额外的空间。

为什么插入排序比冒泡排序更受欢迎？

性能差异： 尽管插入排序和冒泡排序在最坏情况下的时间复杂度都是 O(n^2)，但在实际执行中，插入排序通常表现更好。这是因为插入排序每次只需在已排序部分进行线性搜索并找到合适位置，而冒泡排序需要进行多次交换操作，导致性能差异。
稳定性： 插入排序是稳定的，即相等元素的相对顺序在排序前后保持不变。在某些场景下，稳定性是排序算法的重要考虑因素，而冒泡排序在最坏情况下可能打破相等元素的相对顺序。
提前终止： 插入排序在部分已经有序的情况下表现更好。如果输入数据大部分已经有序，插入排序只需做很少的比较和移动操作，而冒泡排序在这种情况下仍然需要进行多次冒泡。
代码实现简单： 插入排序的实现相对简单，代码量较小，易于理解和维护。冒泡排序的实现相对更复杂，因为它需要进行多次元素交换。

发布于: 刚刚阅读数: 5

原文链接:【http://xie.infoq.cn/article/ed8d99a0668103fb7807c0636】。

鲁米

关注

生活黑客35 2019-06-11 加入

起点不重要，迭代很重要，就需要保持充分的开放和积累；而信息越充分，结果越可靠，又要求随时调整、不断逼近真相。

发布

暂无评论

创作场景

11 | 排序（上）：为什么插入排序比冒泡排序更受欢迎

如何分析一个“排序算法”？

1. 时间复杂度

2. 空间复杂度

3. 稳定性

4. 适用场景

5. 实现细节

6. 排序稳定性举例

问题区

鲁米

评论