Java實現直接插入排序算法

• 基本思想

  每次將一個待排序的記錄，按其關鍵字大小插入到前面已經排好序的子序列中的適當位置，直到全部插入完成。

  設數組為a[0...n-1]

  1. 初始時，a[0]自成一個有序區，無序區為a[1...n-1]。令i=1
  2. 將a[i]並入當前有序區a[0...i-1]中形成a[0...i]的有序區間
  3. i++重復第二步直到i==n-1。排序完成

• 算法實現

    public void sort(int[] array) {
        int i, j, k;
    
        for (i = 1; i < array.length; i++) {
    
            for (j = i - 1; j >= 0; j--) { // 找出從0到i-1比i小的數，記錄位置j
                if (array[j] < array[i]) {
                    break;
                }
            }
    
            if (j != i - 1) {
                int tmp = array[i]; // 暫存i的值
    
                for (k = i - 1; k > j; k--) { // 將從j到i-1得數後移
                    array[k + 1] = array[k];
                }
    
                array[k + 1] = tmp; // 將i放到j
            }
        }
    }

這樣的代碼比較長，可以對此進行改寫。將搜索和數據後移合並。

1. 改進

    public void sort(int[] array) {
        for (int i = 1; i < array.length; i++) {
            if (array[i] < array[i - 1]) { // 如果i > i-1的話就不需要移動了
                int tmp = array[i]; // 暫存i的值
                int j;
    
                for (j = i - 1; j >= 0 && array[j] > tmp; j--) { // 從0到i-1，如果0到i-1有大於i的數，全部後移
                    array[j + 1] = array[j];
                }
    
                array[j + 1] = tmp; // 將i的值 插入到當前位置
            }
        }
    }