今天我學(xué)習(xí)的是插入排序，插入排序主要思想是：把要排序的數(shù)字插入到已經(jīng)排好的數(shù)據(jù)中。（我自己理
解的哈）。例如12356是已經(jīng)排好的序，我們將4插入到他們中，時(shí)插入之后也是排好序的。這里顯而易見
是插入到3的后面。變?yōu)?23456.
實(shí)現(xiàn)思路：插入排序就是先是一個(gè)有序的數(shù)據(jù)，然后把要插入的數(shù)據(jù)插到指定的位置，而排序首先給的就
是無序的，我們怎么確定先得到一個(gè)有序的數(shù)據(jù)呢？答案就是：如果只有一個(gè)，當(dāng)然是有序的咯。我們先
拿一個(gè)出來，他是有序的，然后把數(shù)據(jù)一個(gè)一個(gè)插入到其中，那么插入之后是有序的，所以直到最后都是
有序的。。哈哈。結(jié)果就出來了！
當(dāng)然在寫的時(shí)候還是有一個(gè)技巧的，不需要開額外的數(shù)組，下標(biāo)從第二個(gè)元素開始遍歷知道最后一個(gè)，然
后插入到前面已經(jīng)有序的數(shù)據(jù)中。這樣就不會(huì)浪費(fèi)空間了。插入排序用處還是很多的，特別是鏈表中，因
為鏈表是指針存放的，沒有數(shù)組那么好準(zhǔn)確的用下標(biāo)表示，插入是簡單有效的方法。嘻嘻。。廢話少說，
源代碼奉上：
1 #include <stdio.h>
2 #include <stdlib.h>
3
4 //插入排序從下到大，nData為要排序的數(shù)據(jù),nNum為數(shù)據(jù)的個(gè)數(shù),該排序是穩(wěn)定的排序
5 bool InsertionSort(int nData[], int nNum)
6 {
7 for (int i = 1; i < nNum; ++i) //遍歷數(shù)組，進(jìn)行插入排序
8 {
9 int nTemp = nData[i];
10 for (int j = 0; j < i; ++j) //對該數(shù)，尋找他要插入的位置
11 {
12 if (nData[j] > nTemp) //找到位置，然后插入該位置，之后的數(shù)據(jù)后移
13 {
14 for (int k = i; k > j; --k) //數(shù)據(jù)后移
15 {
16 nData[k] = nData[k -1];
17 }
18 nData[j] = nTemp; //將數(shù)據(jù)插入到指定位置
19 break;
20 }
21 }
22 }
23
24 return true;
25 }
26
27 int main()
28 {
29 int nData[10] = {4,10,9,8,7,6,5,4,3,2}; //創(chuàng)建10個(gè)數(shù)據(jù)，測試
30 InsertionSort(nData, 10); //調(diào)用插入排序
31
32 for (int i = 0; i < 10; ++i)
33 {
34 printf("%d ", nData[i]);
35 }
36
37 printf("\n");
38 system("puase");
39 return 0;
40 }