插入排序法 (Insert Sort) 是將陣列中的元素，逐一與已排序好的資料作比較，再將該陣列元素插入適當的位置，
演算程序
插入法分析
- 最壞及平均情況需比較 (n-1)+(n-2)+(n-3)+...+3+2+1=n(n-1)/2 次；時間復雜度為 O(n^2)，最好情況時間復雜度為 O(n)，
- 插入排序是穩定排序法，
- 只需一個額外的空間，所以空間復雜度為最佳，
- 此排序法適用于大部分資料已經過排序或已排序資料庫新增資料后進行排序的情況，
- 插入排序法會造成資料的大量搬移，所以建議在鏈表上使用，
example1
/** * 插入排序法 * */ public class InsertSort { public static void main(String[] args) { int data[] = new int[] {6, 4, 9, 8, 3}; System.out.print("原始資料："); showData(data); insert(data); System.out.print("排序后的資料："); showData(data); } private static void insert(int data[]) { int i, j, tmp; for (i = 1; i < data.length; i++) { tmp = data[i]; j = i; while (--j >= 0 && tmp < data[j]) { data[j+1] = data[j]; data[j] = tmp; } showData(data); } } private static void showData(int data[]) { for (int i = 0; i < data.length; i++) { System.out.printf("[%d]", data[i]); } System.out.printf("%n"); } }
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/62076.html
標籤：其他
上一篇：資料結構-選擇排序法