插入排序

引言

插入排序是一种简单的排序算法，它的核心思想是将待排序的元素逐一插入到已排序部分的合适位置。虽然它的时间复杂度较高（最坏情况下是 O(n²)），但在数据量较小或者数据已经部分有序时，插入排序的表现比较优秀，且它是稳定的排序算法。

插入排序的实现原理

插入排序的实现过程可以通过以下步骤描述：

1. 从第二个元素开始：首先，假设第一个元素已经排好序，然后从第二个元素开始，逐个将未排序的元素插入到已排序部分的合适位置。
2. 查找插入位置：对于当前元素，将其与已排序部分的元素逐一比较，找到其应该插入的位置。
3. 元素移位：为了腾出位置，所有比当前元素大的元素都会向后移动一位。
4. 插入当前元素：将当前元素插入到正确的位置。

插入排序的主要操作是将一个元素插入到已经排好序的部分，涉及到元素的比较和移动，因此其时间复杂度最坏情况下为 O(n²)，最优情况下（数据本身已经有序）为 O(n)。

插入排序的代码实现

#include <iostream>
using namespace std;

void insertionSort(int arr[], int n) {
    // 从第二个元素开始，假设第一个元素已经排好序
    for (int i = 1; i < n; i++) {
        int key = arr[i];  // 当前要插入的元素
        int j = i - 1;

        // 找到插入位置，右侧元素向右移动
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }

        // 将当前元素插入到正确的位置
        arr[j + 1] = key;
    }
}

void printArray(int arr[], int n) {
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;
}

int main() {
    int arr[] = {12, 11, 13, 5, 6};
    int n = sizeof(arr) / sizeof(arr[0]);

    cout << "Original array: ";
    printArray(arr, n);

    insertionSort(arr, n);

    cout << "Sorted array: ";
    printArray(arr, n);

    return 0;
}

代码解析

1. insertionSort 函数：
   • 该函数实现了插入排序的主要逻辑。我们从数组的第二个元素开始，依次将每个元素插入到其合适的位置。
   • key 是当前要插入的元素，我们将它与已排序部分的元素逐一比较。
   • j 是已排序部分的最后一个元素索引，while 循环用于找到 key 应该插入的位置。通过比较当前元素和 key 的大小，元素需要向右移动。
   • 最后将 key 插入到合适的位置，即 arr[j + 1] = key。
2. printArray 函数：
   • 用于输出数组的内容，帮助我们观察排序前后的变化。
3. main 函数：
   • 我们定义了一个数组 arr[]，并调用 insertionSort 函数对其进行排序，最后输出排序后的数组。

插入排序的时间复杂度

• 最优情况（已排序）：当数组已经是升序时，插入排序的时间复杂度是 O(n)，因为每个元素都只需要和前一个元素比较一次。
• 最坏情况（逆序）：当数组是降序排列时，插入排序的时间复杂度是 O(n²)，因为每个元素都需要移动到数组的最前面。
• 平均情况：平均情况下，插入排序的时间复杂度也是 O(n²)。

插入排序的空间复杂度

插入排序是原地排序算法，空间复杂度为 O(1)，因为它只需要一个常数的额外空间来存储 key 和 j。

插入排序的优点和缺点

优点：

• 简单、易于实现。
• 对于小规模数据或部分有序的数据，插入排序非常高效。
• 是稳定的排序算法（相等的元素不会改变相对顺序）。

缺点：

• 最坏时间复杂度为 O(n²)，因此对于大规模数据，插入排序效率较低。
• 在数据完全逆序的情况下，效率最差。

总结

插入排序是一种非常直观的排序算法，它通过将未排序的元素插入到已排序部分的合适位置来逐步完成排序。尽管在大多数情况下它的时间复杂度较高，但在数据量较小或部分有序时，它依然表现得非常高效。