Insertion Sort

Idea

Insertion Sort inserts each element into the already-sorted prefix, repeating until all elements are ordered.

插入排序演示

524613

下一步

Algorithm

1. From the 2nd element onward, compare backward with the sorted part and insert at the right spot.
2. Repeat until all elements are placed.

Pseudo-code:

for i = 1 to n-1:
    key = A[i]
    j = i-1
    while j >= 0 and A[j] > key:
        A[j+1] = A[j]
        j--
    A[j+1] = key

Complexity

• Best: $O(n)$ (already sorted)
• Worst/avg: $O(n^2)$
• Space: $O(1)$
• Stability: stable

Exercises

Exercise 1

Insert-sort $A = [5, 2, 4, 6, 1, 3]$ and show each pass.

参考答案

思路：每次把一个元素插到前面有序段。

步骤：

1. 初始：[5, 2, 4, 6, 1, 3]
2. 第 1 趟：[2, 5, 4, 6, 1, 3]
3. 第 2 趟：[2, 4, 5, 6, 1, 3]
4. 第 3 趟：[2, 4, 5, 6, 1, 3]
5. 第 4 趟：[1, 2, 4, 5, 6, 3]
6. 第 5 趟：[1, 2, 3, 4, 5, 6]

答案：如上，逐步有序。

Exercise 2

What are the time and space complexities of insertion sort?

参考答案

思路：复杂度与空间。

步骤：

1. 时间复杂度 $O(n^2)$
2. 空间复杂度 $O(1)$

答案：时间 $O(n^2)$，空间 $O(1)$。

PreviousOrigins and Practical Significance of SortingThe history, real-world applications, and motivations behind sorting. NextBubble SortBubble sort basics, algorithm flow, complexity, and practice.