資料結構與算法學習筆記——插入排序、希爾排序

插入排序

插入式排序屬于内部排序法，是對于欲排序的元素以插入的方式找尋該元素的适當位置，以達到排序的目的。

實作思路

插入排序(Insertion Sorting）的基本思想是:把n個待排序的元素看成為一個有序表和一個無序表，開始時有序表中隻包含一個元素，無序表中包含有n-1個元素，排序過程中每次從無序表中取出第一個元素，把它的排序碼依次與有序表元素的排序碼進行比較，将它插入到有序表中的适當位置，使之成為新的有序表。

代碼實作

import java.util.Arrays;

public class InsertSort {

    public static void main(String[] args) {
        int[] arr = {101, 34, 119, 1, -1, 89};

        System.out.println("插入排序前");
        System.out.println(Arrays.toString(arr));
        insertSort(arr); //調用插入排序算法
        System.out.println("插入排序前後");
        System.out.println(Arrays.toString(arr));

    }

    //插入排序
    public static void insertSort(int[] arr) {
        int insertVal = 0;
        int insertIndex = 0;
        //使用for循環來把代碼簡化
        for(int i = 1; i < arr.length; i++) {
            //定義待插入的數
            insertVal = arr[i];
            insertIndex = i - 1; // 即arr[1]的前面這個數的下标

            // 給insertVal 找到插入的位置
            // 說明
            // 1. insertIndex >= 0 保證在給insertVal 找插入位置，不越界
            // 2. insertVal < arr[insertIndex] 待插入的數，還沒有找到插入位置
            // 3. 就需要将 arr[insertIndex] 後移
            while (insertIndex >= 0 && insertVal < arr[insertIndex]) {
                arr[insertIndex + 1] = arr[insertIndex];// arr[insertIndex]
                insertIndex--;
            }
            // 當退出while循環時，說明插入的位置找到, insertIndex + 1
            // 舉例：了解不了，我們一會 debug
            //這裡我們判斷是否需要指派
            if(insertIndex + 1 != i) {
                arr[insertIndex + 1] = insertVal;
            }

        }

        
    }

}

           

希爾排序

希爾排序是希爾(Donald Shell）于1959年提出的一種排序算法。希爾排序也是一種插入排序，它是簡單插入排序經過改進之後的一個更高效的版本，也稱為縮小增量排序。

實作思路

希爾排序是把記錄按下标的一定增量分組，對每組使用直接插入排序算法排序;随着增量逐漸減少，每組包含的關鍵詞越來越多，當增量減至1時，整個檔案恰被分成一組，算法便終止

代碼實作

import java.util.Arrays;

public class ShellSort {

    public static void main(String[] args) {
        int[] arr = { 8, 9, 1, 7, 2, 3, 5, 4, 6, 0 };

        System.out.println("排序前");
        System.out.println(Arrays.toString(arr));
        shellSort(arr); //交換式
        System.out.println("排序後");
        System.out.println(Arrays.toString(arr));
    }

    // 使用逐漸推導的方式來編寫希爾排序
    // 希爾排序時， 對有序序列在插入時采用交換法,
    // 思路(算法) ===> 代碼
    public static void shellSort(int[] arr) {

        int temp = 0;
        // 根據前面的逐漸分析，使用循環處理
        for (int gap = arr.length / 2; gap > 0; gap /= 2) {
            for (int i = gap; i < arr.length; i++) {
                // 周遊各組中所有的元素(共gap組，每組有個元素), 步長gap
                for (int j = i - gap; j >= 0; j -= gap) {
                    // 如果目前元素大于加上步長後的那個元素，說明交換
                    if (arr[j] > arr[j + gap]) {
                        temp = arr[j];
                        arr[j] = arr[j + gap];
                        arr[j + gap] = temp;
                    }
                }
            }
        }


    }


}