直接插入排序(InsertSort)
每次插入一个新的待排序数到已排序序列中，注意此时从后往前比较，更节省时间。
举例
原始序列： 49, 38, 65, 13, 27
- 一开始只看49,则单个数字肯定是有序的
{49} / 38, 65, 13, 27
- 此时插入38， 由于38<45， 故45向后移动， 38插入到49原来的位置
{38, 49} / 65, 13, 27
- 此时插入65, 从后向前进行比较，49<65， 故65直接插入到49之后
{38, 49, 65} / 13, 27
- 此时插入13，从后向前进行比较，一直到38>13，这趟排序后的结果为：
{13, 38, 49, 65} / 27
- 此时插入27，从后向前进行比较，发现该插入到13之后，38之前
{13, 27, 38, 49, 65}
代码：
#include <iostream>
using namespace std;
void InsertSort(int array[], int n) {
int i, j, temp;
for (i = 1; i < n; ++i) {
temp = array[i];
j = i - 1;
while (j >= 0 && temp < array[j]) {
array[j+1] = array[j];
--j;
}
array[j+1] = temp;
}
}
void print_array(int array[], int n) {
for (int i = 0; i < n; ++i)
cout<<array[i]<<" ";
cout<<endl;
}
int main() {
int array[] = {49, 38, 65, 13, 27};
print_array(array, 5);
InsertSort(array, 5);
print_array(array, 5);
return 0;
}
复杂度分析
1. 时间复杂度：
最坏情况，整个原始序列是逆序的，则内层循环temp<array[i]每次都成立，则时间复杂度为O(n^2).
最好情况，整个原始序列原本就是按序排列的，则内存循环条件不满足，时间复杂度为O(n).
综合来看，时间复杂度为O(N^2).
2. 空间复杂度：
只需要一个temp，并不随着待排序列的规模而变化，因此空间复杂度为O(1).
