顾乔芝士网

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

以下是插入排序的算法步骤：

1. 从第一个元素开始，该元素可以认为已经被排序。

2. 取出下一个元素，在已经排序的元素序列中从后向前扫描。

3. 如果该元素（已排序）大于新元素，将该元素移到下一位置。

4. 重复步骤 3，直到找到已排序的元素小于或者等于新元素的位置。

5. 将新元素插入到该位置后。

6. 重复步骤 2~5。

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

#include

#include

using namespace std;

// 插入排序函数

vector insertionSort(vector 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 = j - 1;

}

arr[j + 1] = key;

}

return arr;

}

int main() {

vector numbers = { 5, 2, 4, 6, 1, 3 };

vector sorted = insertionSort(numbers);

for (int num : sorted) {

cout << num << " ";

}

cout << endl;

return 0;

}

在上述代码中，insertionSort 函数实现了插入排序的逻辑。main 函数中定义了一个待排序的数组，调用 insertionSort 函数对其进行排序，并输出排序后的结果。