

插入排序

Insertion sort divides the sequence into two parts, "sorted" and "unsorted". Each time, it selects one from the "unsorted" elements to insert into the correct position of the "sorted" part.

The worst case time complexity and average case time complexity of insertion sort are both $O(n^2)$ , but their efficiency is very high when the sequence is almost ordered.

Insertion sort is a stable sort.

Pseudocode:

$$\begin{array}{ll} 1 & \textbf{Input. } \text{An array } A \text{ consisting of }n\text{ elements.} \\ 2 & \textbf{Output. } A\text{ will be sorted in nondecreasing order stably.} \\ 3 & \textbf{Method. } \\ 4 & \textbf{for } i\gets 2\textbf{ to }n\\ 5 & \qquad key\gets A[i]\\ 6 & \qquad j\gets i-1\\ 7 & \qquad\textbf{while }j>0\textbf{ and }A[j]>key\\ 8 & \qquad\qquad A[j + 1]\gets A[j]\\ 9 & \qquad\qquad j\gets j - 1\\ 10 & \qquad A[j + 1]\gets key \end{array}$$

C++ code

void insertion_sort(int* a, int n) {
  // perform insertion sort on a[1],a[2],...,a[n]
  for (int i = 2; i <= n; ++i) {
    int key = a[i];
    int j = i - 1;
    while (j > 0 && a[j] > key) {
      a[j + 1] = a[j];
      --j;
    }
    a[j + 1] = key;
  }
}

---

build本页面最近更新：，更新历史
edit发现错误？想一起完善？ 在 GitHub 上编辑此页！
people本页面贡献者：OI-wiki
copyright本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用

评论