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