排序算法之 —> 插入排序

插入排序.cpp

//-----------------------------------------------------------------------------
// 作    者：adoredee
// 创建时间：2019.04.23
// 描    述：插入排序
//-----------------------------------------------------------------------------
/*
    数组前面是排序好的，乱序的数依次向有序的数比较

*/
#include <iostream>
#include <vector>

using namespace std;

void InsertSort(vector<int>& arr)
{
	// 默认第一个元素是有序的
	for (int i = 1; i < arr.size(); i++)
	{
		int key = arr[i];
		int j = i - 1;
		// 从小到大排序
		/*
		    从后向前逐个比较已经排序过数组，如果比它小，则把后者用前者代替，
			从而找到合适的位置插入key值
		*/
		while (j >= 0 && key < arr[j])
		{
			arr[j + 1] = arr[j];   // 把前一位的值赋值给后一位
			j--;  // 向前移动
		}
		arr[j + 1] = key;   // 找到合适的位置了，把key值放到j索引的后面
	}
}

int main()
{
	vector<int> arr = { 5, 3, 7, 6, 6, 8, 10, 1 };
	InsertSort(arr);

	// for (int i = 0; i < arr.size(); i++)
	//     cout << arr[i] << " ";
	for(auto i : arr)    // i为容器里的元素，不为索引
		cout << i << " ";

	return 0;
}