插入排序和希尔排序，C语言实现
插入排序的思想：只有一个元素的数组一定是有序的，我们可以把第二个元素放在正确的位置，使这两个元素组成的数组保持有序。接着可以把第三个元素放在正确的位置，使这三个元素组成的数组仍然保持有序。数组的插入操作的时间复杂度为O(N)，需要执行n - 1次，所以插入排序的时间复杂度是O(N2)。插入排序是简单排序中最快的一种，特别是当整个数组是有序的时候，插入排序的时间复杂度是O(N)。当数据规模比较小 (n < 100) 时，插入排序比其它任何一种比较排序算法都要快，所以插入排序经常用于高级排序的优化。
插入排序的代码： #include <stdio.h> #include <stdlib.h>
int arr[] = {4, 1, 5, 7, 3, 2, 9, 8, 6, 0, 5, 4, 3, 6, 7, 8}; int size = 0;
void insertSort() { //第0个数是有序的，所以从第1个数开始排序 for(int i = 1; i < size; i++) { int temp = arr[i]; //记录第i个数据 int j = i - 1; //从i - 1个数据开始往前查找
//j的下标不能 < 0，且arr[j] > temp。
//从小到大排序
while(j >= 0 && arr[j] > temp)
{
arr[j + 1] = arr[j]; //用前一个数字覆盖后一个数字
j--;
}
arr[j + 1] = temp; //在正确的位置插入数据
}
}
int main() { size = sizeof(arr) / sizeof(int); insertSort(); //排序 return 0; }
