使用范圍：小規(guī)模數(shù)據(jù)的排序的方案，而且是一種穩(wěn)定的排序。
算法復(fù)雜度：O（n2）
思想：
首先我們來想一個(gè)問題，我們是否能找到一種方法，使一個(gè)數(shù)插入到一個(gè)有序的數(shù)組當(dāng)中，并保證它依然有序呢？
那么，我們又如何將一組無序的數(shù)插入到一個(gè)有序的數(shù)組之中，并且保證它依然有序呢？
至此，聰明的讀者就會(huì)發(fā)現(xiàn)，解決了這兩個(gè)問題，我們就知道如何排序了。
下面我們來詳細(xì)的講解一下查入排序的思想：
首先我們將一組無序的數(shù)分為兩組，一組有序的，記作A，一組無序的，記作B。開始的時(shí)候A中只有一個(gè)元素，顯然只有一個(gè)元素的數(shù)組是有序的，我們開始將B中的元素逐個(gè)插入到A中，并且每一次插入都保證A是有序的，一直將B中的元素全部插入到A中，那么我們就將這個(gè)數(shù)組排好序了。
下面我們來看一下如何將一個(gè)數(shù)插入到一個(gè)有序數(shù)組中，有一個(gè)數(shù)組{3，5，7，9，12}和一個(gè)數(shù)6，我們可以從數(shù)組的前面開始查找直到找到一個(gè)不小于6的數(shù)，然后把6放在他前面。我們也可以從數(shù)組的后面開始查找直到找到一個(gè)不大于6的數(shù)，然后把6放到他的后面?；蛘呶覀兛梢杂枚植檎业?應(yīng)該在數(shù)組中的位置然后把6放在那。在這個(gè)查找位置的過程中，基于比較的復(fù)雜度依次是O（n）、O（n）、O（log2n）。
那么，將一個(gè)數(shù)組排序的過程，就是將有序數(shù)組不斷增大的過程，從開始只有一個(gè)元素，到后來整個(gè)數(shù)組都是有序的，那么，每插入一次的時(shí)間復(fù)雜度與有序數(shù)組的大小有關(guān)，假設(shè)目前的有序數(shù)組大小為i，此次插入的最壞比較次數(shù)為i，那么，最壞情況下，也就是數(shù)組倒序時(shí)，總體的比較次數(shù)為1+2+3+…+(n-1)=n(n-1)/2
情況下，也就是數(shù)組有序時(shí)，這時(shí)的比較次數(shù)為n-1次。
平均情況下，一次插入的比較次數(shù)為i/2，總體的比較次數(shù)為1/2+2/2+3/2+…+(n-1)/2=n(n-1)/4
所以，平均情況下比較復(fù)雜度為O(n2),如果我們考慮每次插入，在查找位置時(shí)使用二分查找，平均情況下比較復(fù)雜度為O（nlog2n）。
細(xì)心的讀者會(huì)發(fā)現(xiàn)，插入排序的時(shí)間復(fù)雜度不是O（n2）嗎？怎么變成O（nlog2n）了？其實(shí)，在排序的過程中，除了比較的花銷之外，還有元素移動(dòng)的花銷。
如果用數(shù)組來實(shí)現(xiàn)，每次移動(dòng)的花銷是O（n）,總體的花銷是O(n2)。
如果用鏈表來實(shí)現(xiàn)，每次移動(dòng)的花銷是O（1），但查找時(shí)就不能用二分法，所以總體的花銷還是O(n2)。
下面給出一個(gè)用數(shù)組為數(shù)據(jù)結(jié)構(gòu)的插入排序的C＋＋代碼：
/**
* 插入排序方法
* @param array 數(shù)組名
* @param left 排序的起始位置
* @param length 數(shù)組要排序的長度
* @author oracleot & Iceer
*/
void insertSort(int * array, int left, int length) {
//對(duì)一開始的數(shù)組，可分為［left,left+1）有序數(shù)組，考試,大提示只有一個(gè)數(shù)
//［left+1,left+length)無序數(shù)組。
for( int i = left + 1; i < left + length ; ++ i ) {
//現(xiàn)在的任務(wù)是把a(bǔ)rray[i]插入到array[left,i)中。
int current = array[i] ;
int j ;
//如果current不小于array[j]則把current查入到j(luò)＋1位置。（）
for( j = i-1; (j >= left) && (current < array[j]); -- j ) {
array[j+1] = array[j] ;
}
array[j+1] = current ;
}
}
算法復(fù)雜度：O（n2）
思想：
首先我們來想一個(gè)問題，我們是否能找到一種方法，使一個(gè)數(shù)插入到一個(gè)有序的數(shù)組當(dāng)中，并保證它依然有序呢？
那么，我們又如何將一組無序的數(shù)插入到一個(gè)有序的數(shù)組之中，并且保證它依然有序呢？
至此，聰明的讀者就會(huì)發(fā)現(xiàn)，解決了這兩個(gè)問題，我們就知道如何排序了。
下面我們來詳細(xì)的講解一下查入排序的思想：
首先我們將一組無序的數(shù)分為兩組，一組有序的，記作A，一組無序的，記作B。開始的時(shí)候A中只有一個(gè)元素，顯然只有一個(gè)元素的數(shù)組是有序的，我們開始將B中的元素逐個(gè)插入到A中，并且每一次插入都保證A是有序的，一直將B中的元素全部插入到A中，那么我們就將這個(gè)數(shù)組排好序了。
下面我們來看一下如何將一個(gè)數(shù)插入到一個(gè)有序數(shù)組中，有一個(gè)數(shù)組{3，5，7，9，12}和一個(gè)數(shù)6，我們可以從數(shù)組的前面開始查找直到找到一個(gè)不小于6的數(shù)，然后把6放在他前面。我們也可以從數(shù)組的后面開始查找直到找到一個(gè)不大于6的數(shù)，然后把6放到他的后面?；蛘呶覀兛梢杂枚植檎业?應(yīng)該在數(shù)組中的位置然后把6放在那。在這個(gè)查找位置的過程中，基于比較的復(fù)雜度依次是O（n）、O（n）、O（log2n）。
那么，將一個(gè)數(shù)組排序的過程，就是將有序數(shù)組不斷增大的過程，從開始只有一個(gè)元素，到后來整個(gè)數(shù)組都是有序的，那么，每插入一次的時(shí)間復(fù)雜度與有序數(shù)組的大小有關(guān)，假設(shè)目前的有序數(shù)組大小為i，此次插入的最壞比較次數(shù)為i，那么，最壞情況下，也就是數(shù)組倒序時(shí)，總體的比較次數(shù)為1+2+3+…+(n-1)=n(n-1)/2
情況下，也就是數(shù)組有序時(shí)，這時(shí)的比較次數(shù)為n-1次。
平均情況下，一次插入的比較次數(shù)為i/2，總體的比較次數(shù)為1/2+2/2+3/2+…+(n-1)/2=n(n-1)/4
所以，平均情況下比較復(fù)雜度為O(n2),如果我們考慮每次插入，在查找位置時(shí)使用二分查找，平均情況下比較復(fù)雜度為O（nlog2n）。
細(xì)心的讀者會(huì)發(fā)現(xiàn)，插入排序的時(shí)間復(fù)雜度不是O（n2）嗎？怎么變成O（nlog2n）了？其實(shí)，在排序的過程中，除了比較的花銷之外，還有元素移動(dòng)的花銷。
如果用數(shù)組來實(shí)現(xiàn)，每次移動(dòng)的花銷是O（n）,總體的花銷是O(n2)。
如果用鏈表來實(shí)現(xiàn)，每次移動(dòng)的花銷是O（1），但查找時(shí)就不能用二分法，所以總體的花銷還是O(n2)。
下面給出一個(gè)用數(shù)組為數(shù)據(jù)結(jié)構(gòu)的插入排序的C＋＋代碼：
/**
* 插入排序方法
* @param array 數(shù)組名
* @param left 排序的起始位置
* @param length 數(shù)組要排序的長度
* @author oracleot & Iceer
*/
void insertSort(int * array, int left, int length) {
//對(duì)一開始的數(shù)組，可分為［left,left+1）有序數(shù)組，考試,大提示只有一個(gè)數(shù)
//［left+1,left+length)無序數(shù)組。
for( int i = left + 1; i < left + length ; ++ i ) {
//現(xiàn)在的任務(wù)是把a(bǔ)rray[i]插入到array[left,i)中。
int current = array[i] ;
int j ;
//如果current不小于array[j]則把current查入到j(luò)＋1位置。（）
for( j = i-1; (j >= left) && (current < array[j]); -- j ) {
array[j+1] = array[j] ;
}
array[j+1] = current ;
}
}