Algorithms 101: Insertion Sort

插入排序 (Insertion Sort)

插入排序是一种简单且高效的排序算法，适用于小规模数据集。其核心思想是在已排序部分中，从右到左找到合适的位置插入新来的元素，使已排序部分依然有序。这个过程重复进行，直到整个数组排序完成。

Insertion Sort is a simple and efficient sorting algorithm, especially for small datasets. The key idea is to insert each new element into its correct position within the already sorted portion by sliding it from right to left until it finds its place. This process is repeated until the entire array is sorted.

1. What is Insertion Sort and How Does It Work?

[English] Insertion sort works by maintaining a sorted portion of the array. Starting with the first element, each subsequent element is compared to the elements in the sorted portion and inserted into its correct position. The process continues until all elements are sorted.

Steps:

1. Start with the first element as the sorted portion.
2. For each new element, compare it with the elements in the sorted portion from right to left.
3. Shift the elements that are larger than the new element to the right.
4. Insert the new element into its correct position.
5. Repeat until the entire array is sorted.

Example:

Initial array: [5, 3, 8, 4, 2]

Step 1: Start with [5] as the sorted portion.

Step 2: Insert 3 into [5] -> [3, 5]

Step 3: Insert 8 into [3, 5] -> [3, 5, 8]

Step 4: Insert 4 into [3, 5, 8] -> [3, 4, 5, 8]

Step 5: Insert 2 into [3, 4, 5, 8] -> [2, 3, 4, 5, 8]

Sorted array: [2, 3, 4, 5, 8]

Behind the Scenes: Each new element is inserted into its correct position within the already sorted portion, ensuring the array remains sorted as elements are added.

[Chinese] 插入排序通过维护数组的已排序部分来工作。从第一个元素开始，每个后续元素与已排序部分的元素进行比较，并插入到正确的位置。这个过程持续进行，直到所有元素都被排序。

步骤:

1. 从第一个元素作为已排序部分开始。
2. 对于每个新元素，从右到左将其与已排序部分的元素进行比较。
3. 将大于新元素的元素右移。
4. 将新元素插入到正确的位置。
5. 重复直到整个数组排序完成。

示例:

初始数组: [5, 3, 8, 4, 2]

步骤 1: 从 [5] 作为已排序部分开始。

步骤 2: 将 3 插入到 [5] -> [3, 5]

步骤 3: 将 8 插入到 [3, 5] -> [3, 5, 8]

步骤 4: 将 4 插入到 [3, 5, 8] -> [3, 4, 5, 8]

步骤 5: 将 2 插入到 [3, 4, 5, 8] -> [2, 3, 4, 5, 8]

排序后的数组: [2, 3, 4, 5, 8]

Behind the Scenes: 每个新元素都插入到已排序部分的正确位置，确保随着元素的添加，数组保持排序。

2. How to Implement Insertion Sort in Python?

[English] Here is the Python code to implement the insertion sort algorithm.

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        # Move elements of arr[0..i-1], that are greater than key,
        # to one position ahead of their current position
        while j >= 0 and key < arr[j]:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key
    return arr

# Example usage
arr = [5, 3, 8, 4, 2]
sorted_arr = insertion_sort(arr)
print("Sorted array:", sorted_arr)

What Happens: The function insertion_sort sorts the input array by iteratively inserting each element into its correct position within the sorted portion.

Behind the Scenes: The algorithm shifts elements that are greater than the current element to the right, making space for the current element to be inserted into its correct position.

[Chinese] 下面是插入排序算法的 Python 实现代码。

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        # 将 arr[0..i-1] 中大于 key 的元素
        # 向前移动一个位置
        while j >= 0 and key < arr[j]:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key
    return arr

# 示例用法
arr = [5, 3, 8, 4, 2]
sorted_arr = insertion_sort(arr)
print("排序后的数组:", sorted_arr)

What Happens: 函数 insertion_sort 通过迭代地将每个元素插入到已排序部分的正确位置来排序输入数组。

Behind the Scenes: 算法将大于当前元素的元素右移，为当前元素插入到正确位置腾出空间。

3. What is the Time Complexity of Insertion Sort?

[English] The time complexity of insertion sort is O(n^2) in the worst and average cases, where n is the number of elements in the array. This is because, in the worst case, each element may need to be compared with every other element. However, in the best case, where the array is already sorted, the time complexity is O(n).

Time Complexity:

• Best Case: O(n) (when the array is already sorted)
• Average Case: O(n^2)
• Worst Case: O(n^2)

Space Complexity:

• Space Complexity: O(1) (in-place sorting, no extra space needed)

[Chinese] 插入排序的时间复杂度在最坏情况和平均情况下都是 O(n^2)，其中 n 是数组中的元素数量。这是因为在最坏的情况下，每个元素可能需要与其他每个元素进行比较。然而，在最好的情况下，如果数组已经排序好，时间复杂度为 O(n)。

时间复杂度:

• 最好情况: O(n)（数组已排序）
• 平均情况: O(n^2)
• 最坏情况: O(n^2)

空间复杂度:

• 空间复杂度: O(1)（原地排序，不需要额外空间）

4. When Should You Use Insertion Sort?

[English] Insertion sort is most effective for small datasets or arrays that are already mostly sorted. Due to its simplicity and ease of implementation, it is often used in educational contexts and in situations where the overhead of more complex sorting algorithms is unnecessary.

Use Cases:

• Small datasets: Efficient for sorting small arrays or lists.
• Nearly sorted arrays: Performs well on arrays that are already mostly sorted.
• Educational purposes: Useful for teaching sorting algorithms due to its straightforward logic.

[Chinese] 插入排序对于小型数据集或已经大部分排序的数组最为有效。由于其简单性和易于实现性，它通常用于教学环境中，以及在复杂排序算法的开销不必要的情况下。

使用场景:

• 小型数据集: 在排序小数组或列表时效率高。
• 近乎排序的数组: 在已经大部分排序的数组上表现良好。
• 教学目的: 由于其简单的逻辑，非常适合作为排序算法的教学工具。

Recommend Resources:

Python: Insertion sorting algorithm by Oggi AI