C++排序算法之插入排序

插入排序是一种简单且直观的排序算法，在实现上也比较容易。它的基本思路是把一个待排序的序列分成两个部分：已排序部分和未排序部分，然后从未排序部分取出一个元素插入到已排序部分的合适位置，作为新的已排序部分。

算法过程

插入排序的过程可以用以下步骤概括：

1. 将序列的第一个元素看成已排序部分，其他元素看成未排序部分
2. 从未排序部分选择一个元素，插入到已排序部分的合适位置
3. 重复步骤2，直到未排序部分为空

具体来说，每次取出未排序部分的第一个元素，循环与已排序部分的元素比较，并插入到合适位置。比较的方式可以选择从前往后比较，也可以从后往前比较，这里选择从前往后比较。

因为需要插入的元素必须始终与已排序部分进行比较，插入排序的时间复杂度取决于序列的初始状态。如果序列已经接近有序，插入排序的速度很快；如果序列完全无序，插入排序的速度则很慢，需要比较$n(n-1)/2$次。

代码示例

以下是使用C++实现插入排序的代码：

void insertionSort(int arr[], int n) 
{ 
    int i, key, j; 
    for (i = 1; i < n; i++) { 
        key = arr[i]; 
        j = i - 1; 

        /* 移动已排序部分的元素，为key腾出插入位置 */
        while (j >= 0 && arr[j] > key) { 
            arr[j + 1] = arr[j]; 
            j = j - 1; 
        } 
        arr[j + 1] = key; 
    } 
} 

这段代码使用了一个for循环，每次将未排序部分的第一个元素插入到已排序部分的正确位置。在插入过程中，需要不断地比较已排序部分的元素和未排序部分的元素，直至找到合适的位置。在比较过程中，为了腾出插入位置，需要不断地将已排序部分的元素向右移动。

以下代码是使用插入排序实现对整型数组排序的示例：

#include <iostream>
using namespace std;

void insertionSort(int arr[], int size) {
    for (int i = 1; i < size; 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;
    }
}

int main() {
    int arr[] = { 5, 2, 4, 6, 1, 3 };
    int size = sizeof(arr) / sizeof(arr[0]);

    insertionSort(arr, size);

    for (int i = 0; i < size; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;

    return 0;
}

在这个示例中，我们首先定义了一个包含六个元素的整型数组。然后调用insertionSort函数对这个数组进行排序，最后输出排好序的结果。

另一个示例

以下是另外一个示例，使用插入排序对字符串数组进行排序：

#include <iostream>
#include <cstring>
using namespace std;

void insertionSort(string arr[], int size) {
    for (int i = 1; i < size; i++) {
        string key = arr[i];
        int j = i - 1;
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}

int main() {
    string arr[] = { "b", "a", "d", "c", "f", "e" };
    int size = sizeof(arr) / sizeof(arr[0]);

    insertionSort(arr, size);

    for (int i = 0; i < size; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;

    return 0;
}

这个示例与上一个示例类似，只不过将整型数组改成了字符串数组。insertionSort函数的实现与之前相同，我们只需要将string类型的变量换成整型变量即可。