利用c语言详细介绍下插入排序

    插入排序，被称为直接插入排序。它的基本思想是将一个记录插入到已经排好序的有序表中，从而一个新的、记录数增 1 的有序表。

一、图文介绍

    我们还是使用数组【10，5，3，20，1]，排序使用升序的方式，小的元素在前，大的元素在后：

1.1，内循环第一遍

    我们第一遍从第二个元素开始往前比较，如果前面元素大于后面元素，则实现交换。

1.2，内循环第二遍

    我们第二遍从第三个元素开始往前比较。

1.3，内循环第三遍

    我们第三遍从第四个元素开始往前比较。

1.4，内循环第四遍

    我们第四遍从第五个元素开始往前比较，最终结束外循环，完成排序。

二、算法实现

2.1，插入排序

    我们用c语言写一个插入排序算法的函数：

int * insertSort(int *arr,int len)
{int preIdx,cur;for(int i=1;i<len;i++) //从第二个元素开始{preIdx = i - 1;cur = arr[i];while(preIdx>=0&&arr[preIdx]>cur) //往前比较，如果前面数据足够大，则完成交换{arr[preIdx+1] = arr[preIdx];preIdx --;}arr[preIdx+1] = cur; //数据最终落位}return arr;
}

2.2，程序测试

int main() {int a[]={10,5,3,20,1};int *p = insertSort(a,5);printf("the array a after sort is ");for(int i=0;i<5;i++){printf("%d ", *(p++));}}