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