大话数据结构之：直接插入排序

直接插入排序

直接插入排序（straight insertion sort）的基本操作是将一个记录插入到已经排好序的有序表中，从而得到一个新的、记录数增1 的有序表。

从名称上就知道它是一种插入排序的方法。它的前提是，已存在的数据表中的数据是有序的。

代码

具体代码如下：

//直接插入排序 升序 void straight_insertion_sort(int *array, int n) { int i, j; for(i = 1; i < n; i++){//循环从第二个元素开始 if(array[i] < array[i - 1]){ int temp = array[i]; //设置哨兵 for(j = i - 1; j >= 0 && array[j] > temp; j--){ array[j + 1] = array[j]; //记录后移 } array[j + 1] = temp; //插入到正确的位置 } } } //直接插入排序 降序 void straight_insertion_sort(int *array, int n) { int i, j; for(i = 1; i < n; i++){//循环从第二个元素开始 if(array[i] > array[i - 1]){ int temp = array[i]; //设置哨兵 for(j = i - 1; j >= 0 && array[j] < temp; j--){ array[j + 1] = array[j]; //记录后移 } array[j + 1] = temp; //插入到正确的位置 } } }

此算法需要两层循环：

外层控制需要比较的关键字，从第二个关键字开始进行比较；内层确定关键字的位置；