首页 > 代码库 > 插入排序详解

插入排序详解

说一说插入排序

插入排序的基本操作就是将一个数据插入到已经排序好序的数据中,从而得到一个新的,个数加一的有序数据,算法适用与少量的数据的排序。时间复杂度O(n^2),是稳定的排序算法。

基本思想:每步将一个待排序的记录,按其关键码值的大小插入前面已经排序的文件的适当位置上去,直到全部插入完为止。

原理示意图:

技术分享

 

 函数段的c++代码实现:

技术分享

全部代码如下:

 1 #include <iostream>
 2 using namespace std;
 3 void insert_sort(int* a,int b)//实现插入排序,引入两个参数,a为数组首地址,b为数组元素个数 
 4 {
 5     for(int i=1;i<b;i++)
 6     {
 7         int j=i;
 8         int t=*(a+j);//标记待排序的元素 
 9         //将大于待排序元素的数整体后移,然后将t插入小于它的数的后面 
10         while(t<*(a+j-1)&&j!=0)
11         {
12             *(a+j)=*(a+j-1);
13             j--;    
14         }
15         *(a+j)=t;
16     }
17 }
18 int main()
19 {
20     int a[5];
21     for(int i=0;i<5;i++)
22     {
23         cin>>a[i];
24     }
25     insert_sort(a,5);
26     for(int i=0;i<5;i++)
27     {
28         cout<<a[i]<<" ";
29      } 
30 }

 

插入排序详解