插入排序算法是所有排序方法中最简单的一种算法,其主要的实现思想是将数据按照一定的顺序一个一个的插入到有序的表中,最终得到的序列就是已经排序好的数据。
直接插入排序是插入排序算法中的一种,采用的方法是:在添加新的记录时,使用顺序查找的方式找到其要插入的位置,然后将新记录插入。
很多初学者所说的插入排序,实际上指的就是直接插入排序算法,插入排序算法还包括折半插入排序、2-路插入排序,表插入排序和希尔排序等,后序文章都会一一讲到。
例如采用直接插入排序算法将无序表{3,1,7,5,2,4,9,6}进行升序排序的过程为:
直接插入排序的具体代码实现为:
#include <stdio.h>
//自定义的输出函数
void print(int a[], int n ,int i){
printf("%d:",i);
for(int j=0; j<8; j++){
printf("%d",a[j]);
}
printf("\n");
}
//直接插入排序函数
void InsertSort(int a[], int n)
{
for(int i= 1; i<n; i++){
if(a[i] < a[i-1]){//若第 i 个元素大于 i-1 元素则直接插入;反之,需要找到适当的插入位置后在插入。
int j= i-1;
int x = a[i];
while(j>-1 && x < a[j]){ //采用顺序查找方式找到插入的位置,在查找的同时,将数组中的元素进行后移操作,给插入元素腾出空间
a[j+1] = a[j];
j--;
}
a[j+1] = x; //插入到正确位置
}
print(a,n,i);//打印每次排序后的结果
}
}
int main(){
int a[8] = {3,1,7,5,2,4,9,6};
InsertSort(a,8);
return 0;
}
运行结果为:
直接插入排序算法本身比较简洁,容易实现,该算法的时间复杂度为O(n2)。
插入排序的其它 4 种排序方法,在后序章节中有详细介绍。