導語
接上一篇文章(冒泡排序也要寫得優(yōu)雅出眾) http://www.reibang.com/p/8abad5e9432b 直接插入排序的思想是：將數(shù)組的無序區(qū)元素一個個插入到前面的有序區(qū)的合適位置，使有序區(qū)仍然有序蚁孔，開始時有序區(qū)只有第一個元素a[0]。
直接插入排序算法步驟：
1.假設待排序數(shù)組為a[0...n]，a[0]自成一個有序區(qū)烛愧，無序區(qū)為a[1...n];
2.遍歷a[1..n]，在有序區(qū)里找到a[i]的合適位置
3.在有序區(qū)內(nèi)掂碱，大于a[i]的元素后移怜姿，將a[i]插入使得有序區(qū)仍然有序。
下面給出嚴格按照定義書寫的代碼：
void insertSort(int a[], int length) {
//a[0]為有序區(qū)疼燥，從第二個元素a[1]開始遍歷
for (int i = 1; i < length; i++) {
//為a[i]在前面的有序區(qū)里找到適合的位置
int j;
for (j = i - 1; j >= 0; j--) {
if (a[j] < a[i]) {
break;
}
}
if(j != i-1){//如果找到位置
int temp = a[i];
//將大于a[i]的數(shù)往后移一位
for (int k = i-1; k > j; k--) {
a[k+1] = a[k];
}
a[j+1] = temp;//將a[i]放到合適位置
}
}
}
下面給出一種改進方法沧卢，可以將找位置和移位合并起來，每次a[i]先和a[i-1]進行比較醉者，如果a[i]>a[i-1]說明已經(jīng)有序不需要找但狭，反之披诗，將大于a[i]的元素一邊進行后移，一邊查找插入位置立磁，代碼如下：
void insertSort2(int a[], int length) {
for (int i = 1; i < length; i++) {
int temp = a[i];
//將找位置與數(shù)據(jù)后移合并
if (a[i] < a[i - 1]) {
int j;
for (j = i-1; j >= 0 && a[j] > temp; j--) {
a[j+1] = a[j];
}
a[j+1] = temp;
}
}
}
我在網(wǎng)上也看到過另一種改進方法呈队，將數(shù)據(jù)后移用交換函數(shù)替代，這樣寫代碼十分簡潔：
void insertSort3(int a[], int length) {
for (int i = 1; i < length; i++) {
for (int j = i-1; j >= 0 && a[j] > a[j+1]; j--) {
//用交換代替數(shù)據(jù)后移
swap(a[j], a[j+1]);
}
}
}
