基本思想 每一趟將一個待排序的記錄,按其關鍵字的大小插入到已經排好序的一組記錄的適當位置上,直到所有待排序記錄全部插入為止。 排序過程 1.初始化無序區、有序區,待排序數組的第一個元素為有序區,剩餘元素為無序區; 2.遍歷無序區,將無序區每一個元素插入到有序區的正確位置上; Java演算法實現 /** ...
基本思想
每一趟將一個待排序的記錄,按其關鍵字的大小插入到已經排好序的一組記錄的適當位置上,直到所有待排序記錄全部插入為止。
排序過程
1.初始化無序區、有序區,待排序數組的第一個元素為有序區,剩餘元素為無序區;
2.遍歷無序區,將無序區每一個元素插入到有序區的正確位置上;
Java演算法實現
/** * 排序介面類 * Created by zhouyh on 2018/5/25. */ public abstract class ISort { public abstract int[] sort(int[] array); } /** * 直接插入排序 * Created by zhouyh on 2018/5/25. */ public class DirectInsertSort extends ISort { @Override public int[] 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[j+1] = array[j]; j--; } array[j+1] = tmp; } } return array; } }View Code
Python代碼實現
def dirInsertSort(reList): length = len(reList) for i in range(1, length): for j in range(i): if reList[i] < reList[j]: reList.insert(j, reList[i]) reList.pop(i+1) break return reList relist = [1, 23, 12, 7, 34, 10, 51] print(dirInsertSort(relist))View Code
性能分析
時間複雜度,在比較的數組有序的情況下,為O(n),即此刻比較次數n-1次,移動次數0;在最壞的情況下,即數組逆序的情況下,為O(n^2),平均時間複雜度為O(n^2)
空間複雜度,直接排序的過程中,僅用到了一個臨時變數,空間複雜端為O(1)
穩定性,直接插入排序為穩定排序,即排序前後的元素位置還是保持和排序前的前後順序一致,例{2①,45,12,2④,3},排序後{2①,2④,3,12,45},其中兩個2的前後順序保持一致。
使用場景
在數組包含的元素數量較小情況下,可以選擇插入排序,元素數量較大的情況下,不適用,因此時移動元素的次數較多;
在數組基本有序的情況下,適合使用插入排序,此時時間複雜度基本上為O(n)