18.4.插入排序

发表于 更新于 分类于 ， 阅读次数： 本文字数： 323 阅读时长 ≈ 1 分钟

\(18.4.\)Insertion Sort

1.The step of Insertion Sort

  The insertion sort follows these general strategies:

  • Starting with an empty output sequence.
  • Add each item from input, inserting into output at right places.

  Also, this method requires a new array, which takes up some memory.As a result, we may try in place sorting by using swapping method.

  Take the below array as example.Suppose we have sorted the first two elements.It's worth noting that we use a \(j\) to track the current spot of the travelling element:

  The \(2\) element will experience the following steps:

  After these steps, the \(2\) element reach its right place, and we get the first third elements sorted:

  Do it recursively, then we can get a sorted array.

2.Step implementation

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public static void sort(Comparable[] a) {
    int n = a.length;
    for (int i = 1; i < n; i ++) {
        //compare with its front element, if it's not in order, swap it
        for(int j = i; j > 0 && less(a[j], a[j - 1]); j --) {
            swap(a, j, j - 1);
        }
    }
}

public static void sort(Comparable[] a, int lo, int hi) {
        for (int i = lo + 1; i < hi; i++) {
            for (int j = i; j > lo && less(a[j], a[j-1]); j--) {
                swap(a, j, j - 1);
            }
        }
    }

3.Some property of Insertion Sort

  Since the principle of insertion sort is to maintain the order of each subsequence, for arrays that are almost sorted, we only need to do few swaps, thus makes sorting fast.

  Suppose that there are \(K\) inversions in the array, the runtime of Insertion Sort is \(\Theta (N+K)\).

  Moreover, we can define an almost sorted array as one in which numbers of inversions \(\leq\;cN\), insertion sort is excellent on these arrays.

  Ususally, for small arrays(with N less than 15), insertion sort is fast.

4.Sorting Summary