插入排序（Insertion_sort）

本文主要是介绍插入排序（Insertion_sort），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

最简单的一种排序

基本思想就是从第一个元素开始，每次排列一个元素，一直排列到结尾

例如：

3  1  4  5  7  2  6

第一个元素不用排序，从第二个开始

因为3  >  1所以直接将3覆盖到1上

3  3  4  5  7  2  6

而1用一个变量先存储着

就这样一直覆盖，直到找到比1小或者到最开头为止

然后结束循环的位置就是这个元素的位置

结束循环位置是0在，则赋值为

1  3  4  5  7  2  6

然后改排序4了

因为3小于4所以直接结束循环，将4的位置还是赋值给4

1  3  4  5  7  2  6

然后排序5和7也是一样

接着排序2，这里直接写出排序2的步骤，自行理解

1  3  4  5  7  7  6

1  3  4  5  5  7  6

1  3  4  4  5  7  6

1  3  3  4  5  7  6

然后结束循环

赋值：

1  2  3  4  5  7  6

6不在演示

c++代码如下：

#include <bits/stdc++.h>using namespace std;void Insertion_sort(int *arr,int size)
{int i,j;for(i = 1;i < size;++i)//第一个元素不用排序{int t = arr[i];for(j = i-1;j >= 0 && arr[j] > t;--j){arr[j+1] = arr[j];//直接覆盖，速度更快（将前一个覆盖到后面）}arr[j+1] = t;//因为是覆盖，所以要最后赋值}
}void print_arr(int *arr,int size)
{for(int i = 0;i < size;++i){cout << arr[i];if(i != size-1){cout << " ";}}
}int main()
{int n;cin >> n;int arr[n];for(int i = 0;i < n;++i){cin >> arr[i];}Insert_sort(arr,n);print_arr(arr,n);cout << endl;
}

这篇关于插入排序（Insertion_sort）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---