插入排序
直接插入排序是一種簡單的插入排序法谦炬，其基本思想是：把待排序的紀錄按其關(guān)鍵碼值的大小逐個插入到一個已經(jīng)排好序的有序序列中悦屏，直到所有的紀錄插入完為止节沦，得到一個新的有序序列键思。[1]
例如,已知待排序的一組紀錄是：
60,71,49,11,24,3,66
假設(shè)在排序過程中，前3個紀錄已按關(guān)鍵碼值遞增的次序重新排列甫贯，構(gòu)成一個有序序列：
49,60,71
將待排序紀錄中的第4個紀錄（即11）插入上述有序序列吼鳞，以得到一個新的含4個紀錄的有序序列。首先叫搁，應(yīng)找到11的
插入位置赔桌，再進行插入供炎。可以講11放入數(shù)組的第一個單元r[0]中疾党，這個單元稱為監(jiān)視哨音诫，然后從71起從右到左查找，11小于71雪位，將71右移一個位
置竭钝，11小于60，又將60右移一個位置雹洗，11小于49香罐，又再將49右移一個位置，這時再將11與r[0]的值比較时肿，11≥r[0]庇茫，它的插入位置就是
r[1]。假設(shè)11大于第一個值r[1]螃成。它的插入位置應(yīng)該在r[1]和r[2]之間旦签，由于60已經(jīng)右移了，留出來的位置正好留給11.后面的紀錄依照同
樣的方法逐個插入到該有序序列中寸宏。若紀錄數(shù)n,續(xù)進行n-1趟排序顷霹，才能完成。
直接插入排序的算法思路：
（1） 設(shè)置監(jiān)視哨r[0]击吱，將待插入紀錄的值賦值給r[0]淋淀；
（2） 設(shè)置開始查找的位置j；
（3） 在數(shù)組中進行搜索覆醇，搜索中將第j個紀錄后移朵纷，直至r[0].key≥r[j].key為止；
（4） 將r[0]插入r[j+1]的位置上永脓。
int array[] = {3,7,5,2,9,4,1,8,6};
int count = sizeof(array) / sizeof(array[0]);
int j;
for ( int i = 1; i < count; i ++) {
j = i;
int tem = array[j];
while ( j > 0 && array[j - 1 ] > tem) {
array[j] = array[j -1];
j --;
}array[j] = tem;
}for (int i = 0; i < count;? i ++) {
printf("%d",array[i]);
}
