插入排序,将被排序序列分为两个序列,一个是已经排序好的有序序列
, 一个是未经排序的无序序列
, 在排序的过程中,每次取一个无序序列元素到插入到有序序列中适当位置,直到所有无序序列元素插入到有序序列中去。
#include <iostream>
#include <stdio.h>
#include <cstdio>
#include <vector>
#include <algorithm>
#include "dbg.h"
using namespace std;
void insertSort(int R[], int len)
{
int temp;
// 初始将index = 0的值默认为有序序列
for (int i = 1; i < len; i++)
{
temp = R[i];
int j = i - 1; // 有序序列最后一个元素
while (j >= 0 && temp < R[j])
{
R[j + 1] = R[j]; // 后移
j--;
}
R[j + 1] = temp;
}
}
int main(int argc, char *argv[])
{
int R[] = {1, 3, 2, 18, 3, 28, 23, 38, 7, 8};
cout << "Before sorting = " << endl;
dbg(R);
int len = sizeof(R) / sizeof(R[0]);
cout << "After sorting = " << endl;
insertSort(R, len);
dbg(R);
return 0;
}
运行结果 =
最坏情况:整个序列为逆序
- 内层循环
temp < R[j]
始终成立 - 时间复杂度 = O(n2)
最好情况:整个序列为有序
- 内层循环
temp < R[j]
始终不成立,退化为单层循环 - 时间复杂度 = O(n)