插入排序算法基本思想

将待排元素逐一插到有序序列中，保持序列有序，从而使有序序列的长度不断增加。过程类似于，我们打扑克时，排牌的过程。

算法动画演示

插入排序

算法举例

待排序列：

数值：6，5，3，1，8，7，2，4

下标：0 1 2 3 4 5 6 7

0--0 有序：6 5 3 1 8 7 2 4

0--1 有序：5 6 3 1 8 7 2 4

0--2 有序：3 5 6 1 8 7 2 4

0--3 有序：1 3 5 6 8 7 2 4

0--4 有序：1 3 5 6 8 7 2 4

0--5 有序：1 3 5 6 7 8 2 4

0--6 有序：1 2 3 5 6 7 8 4

0--7 有序：1 2 3 4 5 6 7 8

算法代码

#include
#include
using namespace std;

//升序
void insertSort(vector& arr)
{
	//数组元素个数
	int len = arr.size();
	//元素个数小于2，直接return
	if (len < 2) return;
	//0--0有序,不需要任何操作
	//0--1有序....
	for (int i = 1; i < len; i++)
	{
		for (int j = i - 1; j >= 0 && arr[j] > arr[j + 1]; j--)
		{
			swap(arr[j], arr[j + 1]);
		}
	}
}

//降序
void insertSortDown(vector& arr)
{
	//数组元素个数
	int len = arr.size();
	//元素个数小于2，直接return
	if (len < 2) return;
	//0--0有序,不需要任何操作
	//0--1有序....
	for (int i = 1; i < len; i++)
	{
		for (int j = i - 1; j >= 0 && arr[j] < arr[j + 1]; j--)
		{
			swap(arr[j], arr[j + 1]);
		}
	}

}

int main()
{
	vector arr = { 6,5,3,1,8,7,2,4 };
	//升序
	insertSort(arr);
	for (int i = 0; i < arr.size(); i++)
	{
		cout << arr[i] << " ";
	}
	cout << endl;
	//降序
	insertSortDown(arr);
	for (int i = 0; i < arr.size(); i++)
	{
		cout << arr[i] << " ";
	}
	cout << endl;
	return 0;
}

运行结果：

算法特性

时间复杂度：O(N*N)

空间复杂度：O(1)

稳定性：稳定