经典的排序算法——插入排序（排序算法十大经典方法）

插入排序（Insertion Sort）是一种简单直观的排序算法，它的工作原理是将一个记录插入到已经排序好的有序序列中，从而得到一个新的、个数增1的有序序列。插入排序就像我们日常生活中整理一副扑克牌的过程：每次从剩余未排序的部分取出一张牌，然后将其插入到已排序的手牌中的正确位置。

以下是插入排序的基本步骤：

1. 将数组分为两个部分，初始时左侧视为有序序列（只有一个元素或者为空），右侧视为无序序列。
2. 从无序序列的第一个元素开始，与有序序列的所有元素进行比较。
3. 如果当前元素比有序序列中的某个元素小，则将该元素及之后的所有元素向后移动一位，腾出空间来插入当前元素。
4. 将当前元素插入到腾出的位置上，保证了插入后的序列依然有序。
5. 重复以上过程，直到所有元素都被依次插入到有序序列中。

C++实现插入排序的示例代码如下：

#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; // 从当前元素前一位开始比较
		// 将大于key的元素向后移动，并找到key应该插入的位置
		while (j >= 0 && arr[j] > key) {
			arr[j + 1] = arr[j];
			j--;
		}
		// 插入key到正确的位置
		arr[j + 1] = key;
	}
}
// 测试函数
void printArray(int arr[], int size) {
	for (int i = 0; i < size; i++)
		cout << arr[i] << " ";
	cout << endl;
}
int main() {
	int arr[] = { 64, 25, 12, 22, 11 };
	int n = sizeof(arr) / sizeof(arr[0]);
	insertionSort(arr, n);
	cout << "Sorted array: \n";
	printArray(arr, n);
	return 0;
}

插入排序的时间复杂度在最好情况下（即输入数组已经是有序的）为O(n)，最坏和平均情况下为O(n2)。尽管对于大规模数据集效率不高，但对于小规模数据或部分有序的数据，插入排序表现得相对较好。此外，由于其稳定性和原地排序的特点，在实际应用中有一定的适用场景。