基本思想
假設待排序的記錄存放在數組R[0..n-1]中。初始時，R[0]自成1個有序區，無序區為R[1..n-1]。 從i=1起直至i=n-1為止，依次將R[i]插入當前的有序區R[0..i-1]中，生成含n個記錄的有序區。
算法實現
直接插入排序算法，java實現，代碼如下所示：
public abstract class Sorter { public abstract void sort(int[] array);}public class StraightInsertionSorter extends Sorter { @Override public void sort(int[] array) { int tmp; for (int i = 1; i < array.length; i++) { tmp = array[i]; // array[i]的拷貝 // 如果右側無序區第一個元素array[i] < 左側有序區最大的array[i-1]， // 需要將有序區比array[i]大的元素向后移動。 if (array[i] < array[i - 1]) { int j = i - 1; // 從右到左掃描有序區 while (j >= 0 && tmp < array[j]) { // 將左側有序區中元素比array[i]大的array[j+1]后移 array[j + 1] = array[j]; j--; } // 如果array[i]>=左側有序區最大的array[i-1]，或者經過掃描移動后，找到一個比array[i]小的元素 // 將右側無序區第一個元素tmp = array[i]放到正確的位置上 array[j + 1] = tmp; } } }}排序過程
直接插入排序的執行過程，如下所示：
初始化無序區和有序區：數組第一個元素為有序區，其余的元素作為無序區。遍歷無序區，將無序區的每一個元素插入到有序區正確的位置上。具體執行過程為：每次取出無序區的第一個元素，如果該元素tmp大于有序區最后一個元素，不做任何操作；如果tmp小于有序區最后一個元素，說明需要插入到有序區最后一個元素前面的某個位置，從后往前掃描有序區，如果有序區元素大于tmp，將有序區元素后移（第一次后移：tmp小于有序區最大的元素，有序區最大的元素后移覆蓋無序區第一個元素，而無序區第一個元素的已經拷貝到tmp中；第二次后移：tmp小于有序區從后向前第二個的元素，有序區從后向前第二個元素后移覆蓋有序區最大元素的位置，而有序區最后一個元素已經拷貝到無序區第一個元素的位置上；以此類推），直到找到一個元素比tmp小的元素（如果沒有找到，就插入到有序區首位置），有序區后移操作停止。接著，將tmp插入到：從有序區由前至后找到的第一個比tmp小的元素的后面即可。此時，有序區增加一個元素，無序區減少一個元素，直到無序區元素個數為0，排序結束。下面，通過實例來演示執行直接插入排序的過程，假設待排序數組為array = {94,12,34,76,26,9,0,37,55,76,37,5,68,83,90,37,12,65,76,49}，數組大小為20，則執行排序過程如下所示：
初始有序區為{94}，無序區為{12,34,76,26,9,0,37,55,76,37,5,68,83,90,37,12,65,76,49}。對于array[1] = 12（無序區第一個元素）：臨時拷貝tmp = array[1] = 12，tmp = 12小于有序區{94}最后一個元素(94)，因為有序區只有一個元素，所以將tmp插入到有序區首位置，此時，有序區為{12,94}，無序區為{34,76,26,9,0,37,55,76,37,5,68,83,90,37,12,65,76,49}。對于array[2] = 34（無序區第一個元素）：臨時拷貝tmp = array[2] = 34，tmp = 34小于有序區{12,94}最后一個元素(94)，將94后移覆蓋array[2]，亦即：array[2] = 94；繼續將tmp = 34與有序區{12,94}從后向前第二個元素比較，tmp = 34 > 12，則直接將tmp = 34插入到12后面的位置。此時，有序區為{12,34,94}，無序區為{76,26,9,0,37,55,76,37,5,68,83,90,37,12,65,76,49}。對于array[3] = 76（無序區第一個元素）：臨時拷貝tmp = array[3] = 76，tmp = 76小于有序區{12,34,94}最后一個元素(94)，將94后移覆蓋array[3]，亦即：array[3] = 94；繼續將tmp = 76與有序區{12,34,94}從后向前第二個元素比較，tmp = 76 > 34，則直接將tmp = 76插入到34后面的位置。此時，有序區為{12,34,76,94}，無序區為{26,9,0,37,55,76,37,5,68,83,90,37,12,65,76,49}。……依此類推執行，直到無序區沒有元素為止，則有序區即為排序后的數組。
算法分析
時間復雜度最好情況：有序通過直接插入排序的執行過程可以看到，如果待排序數組恰好為有序，則每次從大小為n-1的無序區數組取出一個元素，和有序區最后一個元素比較，一定是比最后一個元素大，需要插入到有序區最后一個元素的后面，也就是原地插入。可見，比較次數為n-1次，數組元素移動次數為0次。
最壞情況：逆序每次從無序區取出第一個元素，首先需要與有序區最后一個元素比較一次，然后繼續從有序區的最后一個元素比較，直到比較到有序區第一個元素，然后插入到有序區首位置。每次從無序區取出第一個元素，移動放到拷貝tmp中，然后再將tmp與有序區元素比較，這個比較過程一共移動的次數為：有序區數組大小，最后還要將拷貝tmp移動插入到有序區的位置上。在這個過程中：有序區數組大小為1時，比較2次，移動3次；有序區數組大小為2時，比較3次，移動4次；……有序區數組大小為n-1時，比較n次，移動n+1次。可見：比較的次數為：2+3+……+n = (n+2)(n-1)/2移動的此時為：3+4+……+n+1 = (n+4)(n-1)/2
通過上面兩種情況的分析，直接插入排序的時間復雜度為O(n2)。
空間復雜度在直接插入排序的過程中，只用到一個tmp臨時存放待插入元素，因此空間復雜度為O(1)。
排序穩定性通過上面的例子來看：當有序區為{0,9,12,26,34,37,55,76,94}，無序區為{76,37,5,68,83,90,37,12,65,76,49}的時候，執行下一趟直接插入排序：對于array[9] = 76（無序區第一個元素）：臨時拷貝tmp = array[9] = 76，tmp = 76小于有序區{0,9,12,26,34,37,55,76,94}最后一個元素(94)，將94后移覆蓋array[9]，亦即：array[9] = 94；繼續將tmp = 76與有序區{0,9,12,26,34,37,55,76,94}從后向前第二個元素(76)比較，tmp = 76 = 76，則直接將tmp = 76插入到有序區數組元素76后面的位置。此時，有序區為{0,9,12,26,34,37,55,76,76,94}，無序區為{37,5,68,83,90,37,12,65,76,49}。繼續執行直至完成的過程中，對于兩個相等的數組元素，原始為排序數組中索引位置的大小關系并沒有發生改變，也就是說，對于值相等的元素e，存在ei1，ei2，……eik，其中i1，i2……ik是數組元素e在為排序數組中的索引位置，排序前有i1<i2<……<ik，排序后仍然有j1<j2<……<jk，其中j1<j2<……<jk為排序后值相等的元素e的索引。
可見，直接插入排序是穩定的。
新聞熱點
疑難解答
