插入排序（Insertion Sort）

插入序算法是一种稳定的排序算法，其算法的时间复杂度为 O(n2)，其算法基本思想如下：

每次将一个待排序的记录，按其关键字大小插入到前面已经排好序的子序列中的适当位置，直到全部记录插入完成为止。

#include <iostream>
using namespace std;


// 升序
void insertion_sort(int arr[], int len)
{

	for (int i = 1; i < len; ++i)
	{
		if (arr[i] < arr[i - 1])
		{	
			int temp = arr[i];
			int j = i - 1;
			for (; j >= 0 && arr[j] > temp; --j)
			{
				arr[j + 1] = arr[j];
			}

			// 将 temp 插入到 j + 1 位置
			arr[j + 1] = temp;
		}
	}
}

int main()
{
	int arr[] = { 6, 8, 5, 7, 4 };
	insertion_sort(arr, sizeof(arr) / sizeof(int));

	for (auto v : arr) cout << v << " ";
	cout << endl;

	return 0;
}

程序执行结果：

4 5 6 7 8