这篇文章写自英文，阅读原文章.
由于本文暂未被翻译成中文，请使用下面工具选项进行翻译

Insertion Sort

Insertion Sort

Pseudocode

Algorithm 6: Insertion Sort

Analysis

• Best case: list is already sorted, number of comparisons is $(n − 1)$
• Worst case: reversed list; each iteration shifts the element all the way down
• First iteration: 1 comparison, 2nd: at most 2, etc., last iteration: at most $(n − 1)$
comparisons $$\sum_{i=1}^{n-1}i=\frac{n(n-1)}{2} $$
• Worst case: $O(n^2)$
• A more complex analysis for the average case, but still $O(n^2)$
• Practical consideration: insertion sort is inherently adaptive; good performance in
practice
• Very efficient on small lists, especially if there is already some structure (partially
ordered) to them

Code Samples

Code Sample 13: Java Insertion Sort for integers
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 ;
  }
}
Code Sample 14: C Insertion Sort for integers
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 ;
  }
}
The function mergeSort would be called as follows:
1
2
3
int * a = (int *) malloc ( sizeof (int) * n ) ;
...
mergeSort (a , 0 , n -1) ;
Code Sample 21: C Merge Sort for integers
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
void merge (int * array , int left , int mid , int right )
{
  /* temporary array to store the new sorted part */
  int tempArray [ right - left +1];
  int pos =, lpos = left , rpos = mid + 1; // not strict ANSI C
  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 ;
  /* copy back the sorted array to the original array */
  for ( iter =0; iter < pos ; iter ++) {
    array [ iter + left ] = tempArray [ iter ];
  }
  return ;
}