C++ 实现插入排序 - 摩柯技术社区

一、插入排序基础概念

插入排序（Insertion Sort）是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

想象一下我们在玩扑克牌，每次从桌上拿起一张牌，然后将它插入到手中已有的牌中合适的位置，以保持手中牌的有序。插入排序就类似于这个过程。在插入排序中，数组被分为已排序和未排序两部分。开始时，已排序部分只有一个元素，即数组的第一个元素。然后，从第二个元素开始，依次将未排序部分的元素插入到已排序部分的合适位置。

1.1 插入排序的基本步骤

初始化：将数组的第一个元素视为已排序部分，其余元素为未排序部分。
遍历未排序部分：从第二个元素开始，依次选取未排序部分的元素。
插入操作：对于选取的元素，在已排序部分从后向前比较。如果已排序部分的元素大于选取的元素，则将该元素后移一位。直到找到一个小于或等于选取元素的位置，然后将选取元素插入到该位置。
重复：重复步骤2和3，直到未排序部分的所有元素都插入到已排序部分。

例如，对于数组[5, 3, 4, 6, 2]，插入排序的过程如下：

初始状态：已排序部分[5]，未排序部分[3, 4, 6, 2]。
第一轮：选取未排序部分的第一个元素3，与已排序部分[5]比较，3 < 5，将5后移一位，3插入到5原来的位置，此时已排序部分变为[3, 5]，未排序部分变为[4, 6, 2]。
第二轮：选取未排序部分的第一个元素4，与已排序部分[3, 5]比较，4 > 3且4 < 5，将5后移一位，4插入到5原来的位置，此时已排序部分变为[3, 4, 5]，未排序部分变为[6, 2]。
第三轮：选取未排序部分的第一个元素6，与已排序部分[3, 4, 5]比较，6 > 5，直接将6放在5后面，此时已排序部分变为[3, 4, 5, 6]，未排序部分变为[2]。
第四轮：选取未排序部分的第一个元素2，与已排序部分[3, 4, 5, 6]比较，2 < 3，依次将3、4、5、6后移一位，2插入到最前面，最终数组变为[2, 3, 4, 5, 6]，排序完成。

二、C++ 实现插入排序

2.1 简单实现代码

下面是用 C++ 实现插入排序的基本代码：

#include <iostream>
#include <vector>

// 插入排序函数
void insertionSort(std::vector<int>& arr) {
    int n = arr.size();
    for (int i = 1; i < n; ++i) {
        int key = arr[i];
        int j = i - 1;

        // 将大于 key 的元素向后移动
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            --j;
        }
        arr[j + 1] = key;
    }
}

// 打印数组函数
void printArray(const std::vector<int>& arr) {
    for (int num : arr) {
        std::cout << num << " ";
    }
    std::cout << std::endl;
}

int main() {
    std::vector<int> arr = {12, 11, 13, 5, 6};

    std::cout << "原始数组: ";
    printArray(arr);

    insertionSort(arr);

    std::cout << "排序后的数组: ";
    printArray(arr);

    return 0;
}

2.2 代码解析

函数定义：insertionSort函数接受一个std::vector<int>类型的引用作为参数，即要排序的数组。printArray函数用于打印数组元素，方便我们查看排序前后的数组状态。
主函数main：在main函数中，我们定义了一个整数数组arr，并调用printArray函数打印原始数组。然后调用insertionSort函数对数组进行排序，最后再次调用printArray函数打印排序后的数组。
插入排序核心逻辑：
- 在insertionSort函数中，我们首先获取数组的大小n。然后从第二个元素（索引为1）开始遍历未排序部分。
- 对于每个未排序的元素arr[i]，我们将其存储在key中。接着，我们使用一个while循环，在已排序部分（从索引i - 1开始向前）中找到合适的插入位置。如果已排序部分的元素arr[j]大于key，则将arr[j]后移一位（arr[j + 1] = arr[j]），并将j减1。
- 当找到一个小于或等于key的元素或者j小于0时，while循环结束。此时，j + 1就是key应该插入的位置，我们将key插入到该位置（arr[j + 1] = key）。

三、插入排序的性能分析

3.1 时间复杂度

插入排序的时间复杂度取决于输入数据的初始状态。

最好情况：当数组已经是有序的，每次选取的未排序元素只需要与已排序部分的最后一个元素比较一次，就可以确定其位置，不需要移动元素。这种情况下，插入排序的时间复杂度为$O(n)$，其中n是数组的大小。因为只需要遍历一次数组，每次比较操作的时间复杂度为常数时间$O(1)$，总的时间复杂度就是$n \times O(1) = O(n)$。
最坏情况：当数组是逆序的，每次选取的未排序元素都需要与已排序部分的所有元素进行比较，并将已排序部分的所有元素向后移动一位。对于第i个元素，需要进行i次比较和i次移动操作。总的比较次数为$1 + 2 + \cdots + (n - 1) = \frac{n(n - 1)}{2}$，总的移动次数也为$\frac{n(n - 1)}{2}$。因此，最坏情况下的时间复杂度为$O(n^2)$。
平均情况：平均情况下，插入排序的时间复杂度也是$O(n^2)$。可以通过概率论的方法来推导，假设数组元素的初始排列是随机的，对于每个未排序元素，平均需要比较和移动的次数大约是已排序部分元素数量的一半。总的比较和移动次数的数量级与最坏情况相同，所以平均时间复杂度为$O(n^2)$。

3.2 空间复杂度

插入排序是一种原地排序算法，它只需要一个额外的空间来存储key（即O(1)的额外空间），因此空间复杂度为$O(1)$。这意味着插入排序在排序过程中不需要额外的大量内存空间，只在原数组上进行操作。

四、插入排序的稳定性

4.1 稳定性定义

排序算法的稳定性是指如果在待排序的数组中存在两个相等的元素A和B，且A在B之前，那么在排序后的数组中，A仍然在B之前。

4.2 插入排序的稳定性分析

插入排序是稳定的排序算法。在插入排序的过程中，当我们将一个元素插入到已排序部分时，我们是从后向前比较。如果遇到相等的元素，我们会将当前元素插入到相等元素的后面，而不会改变相等元素之间的相对顺序。例如，对于数组[3, 2, 2']（这里2'表示另一个值为2的元素），在排序过程中，2会先被插入到3前面，然后2'也会被插入到3前面，但2'会在2后面，从而保持了相等元素的相对顺序。

五、插入排序的应用场景

5.1 小规模数据排序

由于插入排序在小规模数据上表现良好，当数据量较小时，其简单的实现和较低的常数因子使得它比一些复杂的排序算法（如快速排序、归并排序）更高效。例如，在一些嵌入式系统或者对内存和性能要求较高的小型应用中，如果需要对少量数据进行排序，插入排序是一个不错的选择。

5.2 部分有序数据排序

当数据已经部分有序时，插入排序的时间复杂度可以接近最好情况$O(n)$。例如，在一些实时数据处理场景中，新的数据不断到来，但这些数据本身就有一定的顺序性，使用插入排序可以高效地将新数据插入到已有的有序序列中，保持整体数据的有序性。

5.3 作为其他排序算法的子过程

插入排序可以作为一些更复杂排序算法的子过程。例如，在希尔排序中，希尔排序会先对数组进行分组，然后对每个分组使用插入排序。这样结合使用可以利用插入排序在小规模数据和部分有序数据上的优势，提高整体排序效率。

六、优化插入排序

6.1 二分插入排序

普通插入排序在寻找插入位置时，是通过线性比较的方式从后向前遍历已排序部分。二分插入排序则利用二分查找的思想来优化这一过程，从而减少比较次数。二分查找的时间复杂度为$O(\log n)$，相比于普通插入排序的$O(n)$比较次数，在大规模数据时可以显著提高效率。

以下是二分插入排序的代码实现：

#include <iostream>
#include <vector>

// 二分查找函数，返回插入位置
int binarySearch(const std::vector<int>& arr, int left, int right, int key) {
    while (left <= right) {
        int mid = left + (right - left) / 2;

        if (arr[mid] < key) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    return left;
}

// 二分插入排序函数
void binaryInsertionSort(std::vector<int>& arr) {
    int n = arr.size();
    for (int i = 1; i < n; ++i) {
        int key = arr[i];
        int j = i - 1;

        int insertIndex = binarySearch(arr, 0, j, key);

        // 将元素向后移动
        while (j >= insertIndex) {
            arr[j + 1] = arr[j];
            --j;
        }
        arr[insertIndex] = key;
    }
}

// 打印数组函数
void printArray(const std::vector<int>& arr) {
    for (int num : arr) {
        std::cout << num << " ";
    }
    std::cout << std::endl;
}

int main() {
    std::vector<int> arr = {12, 11, 13, 5, 6};

    std::cout << "原始数组: ";
    printArray(arr);

    binaryInsertionSort(arr);

    std::cout << "排序后的数组: ";
    printArray(arr);

    return 0;
}

在上述代码中，binarySearch函数使用二分查找找到key在已排序部分的插入位置。binaryInsertionSort函数与普通插入排序类似，只是在寻找插入位置时调用binarySearch函数。虽然二分插入排序减少了比较次数，但移动元素的次数仍然与普通插入排序相同，所以在最坏和平均情况下，时间复杂度仍然是$O(n^2)$，但在大规模数据时，由于比较次数的减少，性能会有所提升。

6.2 链表插入排序

如果数据存储在链表中，普通的插入排序实现需要对链表进行特殊处理。链表插入排序利用链表的特性，通过调整节点指针来实现元素的插入。相比于数组插入排序，链表插入排序在移动元素时不需要进行大量的数据复制，因为只需要调整指针。

以下是链表插入排序的代码实现（假设链表节点定义如下）：

#include <iostream>

// 链表节点定义
struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(NULL) {}
};

// 链表插入排序函数
ListNode* insertionSortList(ListNode* head) {
    if (head == NULL || head->next == NULL) {
        return head;
    }

    ListNode dummy(0);
    dummy.next = head;

    ListNode* prev = head;
    ListNode* curr = head->next;

    while (curr != NULL) {
        if (curr->val >= prev->val) {
            prev = curr;
            curr = curr->next;
        } else {
            ListNode* temp = &dummy;
            while (temp->next->val < curr->val) {
                temp = temp->next;
            }
            prev->next = curr->next;
            curr->next = temp->next;
            temp->next = curr;
            curr = prev->next;
        }
    }
    return dummy.next;
}

// 打印链表函数
void printList(ListNode* head) {
    while (head != NULL) {
        std::cout << head->val << " ";
        head = head->next;
    }
    std::cout << std::endl;
}

int main() {
    ListNode* head = new ListNode(4);
    head->next = new ListNode(2);
    head->next->next = new ListNode(1);
    head->next->next->next = new ListNode(3);

    std::cout << "原始链表: ";
    printList(head);

    head = insertionSortList(head);

    std::cout << "排序后的链表: ";
    printList(head);

    return 0;
}

在链表插入排序中，我们首先创建一个哑节点dummy，用于简化边界处理。然后从链表的第二个节点开始遍历，对于每个节点，如果它的值大于等于前一个节点的值，则继续向后遍历；否则，我们在已排序的链表部分找到合适的插入位置，通过调整指针将当前节点插入到该位置。链表插入排序的时间复杂度与数组插入排序相同，在最坏和平均情况下为$O(n^2)$，但在某些场景下，由于链表的特性，其空间复杂度可能更优，并且在移动元素时效率更高。

七、与其他排序算法的比较

7.1 与冒泡排序比较

相似性：冒泡排序和插入排序都是简单的比较排序算法，并且都是稳定的排序算法。它们的时间复杂度在最坏和平均情况下都是$O(n^2)$，空间复杂度都是$O(1)$。
不同点：冒泡排序是通过多次比较相邻元素并交换位置，将最大（或最小）的元素逐步“冒泡”到数组末尾。而插入排序是通过将未排序元素插入到已排序部分的合适位置来实现排序。在实际应用中，插入排序通常比冒泡排序更高效，因为插入排序在部分有序的情况下性能更好，而冒泡排序无论数据初始状态如何，都需要进行大量的比较和交换操作。

7.2 与选择排序比较

相似性：选择排序和插入排序都是简单排序算法，空间复杂度都为$O(1)$。
不同点：选择排序每次从未排序部分选择最小（或最大）的元素，与未排序部分的第一个元素交换位置。插入排序则是将未排序元素逐步插入到已排序部分。选择排序是不稳定的，而插入排序是稳定的。在时间复杂度方面，虽然两者最坏和平均情况都是$O(n^2)$，但插入排序在部分有序数据上表现更好，而选择排序在任何情况下都需要进行$n(n - 1)/2$次比较。

7.3 与快速排序比较

性能差异：快速排序是一种高效的排序算法，平均时间复杂度为$O(n \log n)$，在大多数情况下比插入排序快得多。插入排序在小规模数据或部分有序数据上有优势，而快速排序适用于大规模数据的排序。快速排序的最坏时间复杂度为$O(n^2)$，例如当每次选择的基准元素都是数组中的最大或最小元素时，但通过随机化选择基准元素等方法可以有效避免这种情况。
稳定性：快速排序通常是不稳定的，而插入排序是稳定的。在一些对稳定性有要求的场景中，插入排序可能更合适。

7.4 与归并排序比较

性能差异：归并排序也是一种高效的排序算法，时间复杂度始终为$O(n \log n)$，空间复杂度为$O(n)$。归并排序采用分治思想，将数组不断分成两半，分别排序后再合并。插入排序在小规模数据和部分有序数据上表现较好，而归并排序更适合大规模数据，并且在处理大规模数据时性能更稳定。
稳定性：归并排序是稳定的排序算法，与插入排序一样。但由于归并排序需要额外的空间来进行合并操作，在空间有限的情况下，插入排序可能更有优势。

通过对插入排序与其他常见排序算法的比较，我们可以根据具体的应用场景和数据特点，选择最合适的排序算法来提高程序的效率和性能。在实际编程中，了解各种排序算法的特性和适用场景是非常重要的。无论是简单的插入排序，还是复杂的快速排序和归并排序，都在不同的情况下发挥着各自的作用。同时，对插入排序进行优化，如二分插入排序和链表插入排序，可以进一步拓展其应用范围，使其在更多场景下能够高效地完成排序任务。