本文共 822 字,大约阅读时间需要 2 分钟。
InsertSort 插入排序算法:
平均比较和移动次数为(n^2)/4,时间复杂度也为O(n^2)
直接插入排序比冒泡和简单选择排序的性能要好一些。
思路:
从第二个数开始遍历到最后一个数,如果当前的数小于前一个数,用tmp保存当前数,比较前面的数与tmp的大小,
如果比tmp大则将前面的数往后移动一位,最终将tmp存放在没有再比tmp数大的那个数的位置。
代码:
//插入排序(排序后为从小到大)#include程序输出:#include using namespace std;void InsertSort(int (&a)[7]){//数组作为引用形参传入,使用在此修改对原数组也有效 int aSize = sizeof(a) / sizeof(a[0]);//取数组的大小 int tmp;//设置一个空变量,来保存当a[i] tmp&&j >= 0; --j){//如果前面的数都小于当前数 a[j + 1] = a[j];//将前面的这些数位置后移一位 } a[j + 1] = tmp;//将这个a[i]放到没有比它大的数之前 } }}int main(){ int a[] = {12, 42, 6, 17, 32, 4, 19 }; cout << "Before Sorted:" << endl; for (size_t i = 0; i < 7; ++i){//输出 cout << a[i] << " "; } cout << endl; InsertSort(a); cout << "After Sorted:" << endl; for (size_t i = 0; i < 7; ++i){//输出 cout << a[i] << " "; } cout << endl; return 0;}