一、介绍
直接插入排序是最简单的一种排序，最坏情况下时间复杂度为O(n2)，最好情况下时间复杂度为O(n)，平均为O(n2).
二、算法思想
当要对序列中一个元素（设元素下标为j）进行排序时，遍历这个元素前面的所有元素，找到该元素的目的位置，即如果要求序列从小到大排序的话，则遍历在该元素前面的所有元素，找出第一个大于该元素的元素，设为array[k]，则对区间[k,j)中的元素依次向后移动一个位置，将array[j] 放入array[k]中。
三、算法实现（C++）
#include "stdafx.h"
#include <iostream>
#include <vector>
using namespace std;
void InsertSort(vector<int>& vec)
{
int i, j;
//从第一个元素开始插入
for (i = 0; i < vec.size(); i++)
{
//遍历[0,i)区间内所以元素，寻找vec[i]应该存放的位置
for (j = 0; j < i; j++)
{
if (vec[i] < vec[j])
break;
}
if (j < i)
{
//在区间[0,i)中找到vec[i]应该存放的位置为j
//将区间[j,i)之间的元素依次后移一个位置，空出j位置给vec[i]
int tmp = vec[i];
for (int k = i - 1; k >= j; k--)
{
vec[k + 1] = vec[k];
}
vec[j] = tmp;
}
}
}
int _tmain(int argc, _TCHAR* argv[])
{
vector<int> vec;
vec.push_back(9);
vec.push_back(1);
vec.push_back(2);
vec.push_back(5);
vec.push_back(7);
vec.push_back(4);
vec.push_back(7);
vec.push_back(6);
vec.push_back(3);
vec.push_back(5);
InsertSort(vec);
for (size_t i = 0; i < vec.size(); i++)
{
cout << vec[i] << " ";
}
cout << endl;
system("pause");
return 0;
}
运行结果为：
转载请注明原文地址: https://ju.6miu.com/read-33923.html
