直接插入排序算法思想及示例（C语言实现）

本文主要是介绍直接插入排序算法思想及示例（C语言实现），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

一、算法思想

直接插入排序的主要思想是：

把数列分成两部分，前面部分为有序区，后面部分为无序区，初始时有序区只有第一个元素，一个数字组成的数列当然是有序的
遍历无序区，把其中每个数不断地插入有序区，形成一个更大的有序区，遍历完成时整个数列也就有序了

算法步骤：

假设数组N是待排序的数组，初始时认为N[0]是有序的，那么遍历N[1]到N[n-1]
遍历到N[i]的时候,前面的数列已经是有序的了，那么把N[i]与N[i-1]…一直往前比较,用j来记录与其比较的元素下标，每次比较j自减，循环结束的时候可能出现两种情况：①N[i-1]到N[0]中存在一个N[j]<=N[i]②不存在符合①中的N[j],那么结束循环时j = -1
无论出现2.中的哪种情况，N[i]最终都是插入到N[j+1]的位置，所以使用临时变量记录N[i]的值，然后从N[j+1]到N[i-1]的所有元素后移一位，N[i]插入到N[j+1]的位置

二、示例代码

#include <stdio.h>
void sort(int* N,int n){int i,j,k,temp;for(i = 1; i < n; i++){for(j = i - 1; j >= 0; j--){//往前找一个小于等于N[i]的数if(N[i] >= N[j]) break;}//执行到此，如果N[j]存在那么i的位置在它后面//用一个临时变量来记录N[i]的值temp = N[i];//从N[j+1]开始到N[i-1]的元素向后移动一位for(k = i; k > j + 1; k--){N[k] = N[k -  1];}N[j + 1] = temp;}
}
int main(int argc, char **argv)
{int N[10] = {10,9,8,7,6,5,4,3,2,1};sort(N,10);for(int i = 0; i < 10; i++){printf("%d",N[i]);if(i < 9) printf(",");}return 0;
}