插入排序 (Insertion Sort)

插入排序演示动画

伪代码

算法 6：插入排序伪代码

算法分析

  • 最佳情况 (Best case)：列表已经有序。此时，只需进行 $(n - 1)$ 次比较，无需移动元素。时间复杂度为 $O(n)$。
  • 最坏情况 (Worst case)：列表是逆序的。每一次迭代都需要将当前元素一直向前移动到列表的最前端。
    • 第 1 次迭代：最多 1 次比较。
    • 第 2 次迭代：最多 2 次比较。
    • …
    • 最后一次迭代：最多 $(n - 1)$ 次比较。
    • 总比较次数为：$$\sum_{i=1}^{n-1}i=\frac{n(n-1)}{2}$$
  • 最坏情况时间复杂度：$O(n^2)$。
  • 平均情况 (Average case)：尽管分析更为复杂，但平均时间复杂度仍为 $O(n^2)$。
  • 实际应用考量：插入排序具有天然的自适应性 (adaptive)；在实际应用中，对于规模较小或已经具有一定顺序（部分有序）的列表，其性能表现非常优秀。

代码示例

代码示例 13：Java 语言实现的整数插入排序
1
2
3
4
5
6
7
8
9
10
11
12
public static void insertionSort (int array []) {
  int value ;
  for (int i =1; i < array . length ; i ++) {
    value = array [ i ];
    int j = i ;
      while ( j > 0 && array [j -1] > value ) {
      array [ j ] = array [j -1];
      j--;
    }
    array [ j ] = value ;
  }
}
代码示例 14：C 语言实现的整数插入排序
1
2
3
4
5
6
7
8
9
10
11
12
void insertionSort (int * array , int size ) {
  int value ;
  for (int i =1; i < size ; i ++) {
    value = array [ i ];
    int j = i ;
    while ( j > 0 && array [j -1] > value ) {
      array [ j ] = array [j -1];
      j--;
    }
    array [ j ] = value ;
  }
}

译者注： 原英文博客在插入排序的代码示例后，错误地混入了归并排序（Merge Sort）的代码及调用示例。为保持技术文章的严谨性，译文在此处将保留这部分内容，但会明确标注其为归并排序，并修正 C 语言代码中的语法错误。

附录：归并排序（Merge Sort）代码示例

归并排序函数 mergeSort 的调用示例：
1
2
3
int * a = (int *) malloc ( sizeof (int) * n ) ;
/* ... 初始化数组 a ... */
mergeSort (a , 0 , n -1) ; // 假设存在 mergeSort 函数
代码示例 21：C 语言实现的整数归并操作（Merge）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
/* 注意：此代码使用 C99 特性（变长数组），非严格 ANSI C */
void merge (int * array , int left , int mid , int right )
{
  /* 用于存储新排序部分的临时数组 */
  int tempArray [ right - left +1];
  int pos = 0, lpos = left , rpos = mid + 1; // 修正了原文中 'pos =' 的错误
  
  while ( lpos <= mid && rpos <= right ) {
    if( array [ lpos ] < array [ rpos ]) {
      tempArray [ pos ++] = array [ lpos ++];
    } else {
      tempArray [ pos ++] = array [ rpos ++];
    }
  }
  
  while ( lpos <= mid ) tempArray [ pos ++] = array [ lpos ++];
  while ( rpos <= right ) tempArray [ pos ++] = array [ rpos ++];
  
  int iter ;
  /* 将排序后的临时数组复制回原数组 */
  for ( iter =0; iter < pos ; iter ++) {
    array [ iter + left ] = tempArray [ iter ];
  }
  return ;
}