快捷導航

Java插入排序算法實現(xiàn)方法例子

更新時間：2024年10月08日 10:37:35 作者：小川_wenxun

所謂排序,是將一組數(shù)據(jù)按照特定順序重新排列的過程,穩(wěn)定排序算法中相同鍵值的元素排序后保持原有順序,直接插入排序和希爾排序是插入排序的兩種形式,這篇文章主要介紹了Java插入排序算法實現(xiàn)的相關(guān)資料,需要的朋友可以參考下

排序的概念

排序：所謂的排序，就是使一串記錄，按照某個或某些關(guān)鍵字的大小，遞增或遞減的排列起來的操作。

穩(wěn)定性：假定在待排序的記錄序列中，存在多個具有相同的關(guān)鍵字的記錄，若經(jīng)過排序，這些記錄的相對次序保持不變，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，則稱這種排序算法是穩(wěn) 定的；否則稱為不穩(wěn)定的。

常見的排序算法有下面四種：

插入排序：直接插入排序，希爾排序
選擇排序：選擇排序，堆排序
交換排序：冒泡排序，快速排序
歸并排序：歸并排序

這里主要介紹Java如何實現(xiàn)插入排序中的直接排序和希爾排序。

插入排序

基本思想：把待排序的記錄按照其關(guān)鍵碼值的大小逐個插入到一個已經(jīng)拍好的有序序列中，直到所有的記錄插入完為止，得到一個新的有序序列。生活中的例子，就像我們在完撲克牌的時候機型排序一樣。

直接插入排序

思路：

直接插入排序的過程就像是有一組無序數(shù)據(jù)，用第二個元素先和第一個元素比較，如果第一個元素比第二個元素大，那么二者就交換位置，否則繼續(xù)往后推，隨著往后推，每一次前一個元素都要不斷和之前排序過的元素進行比較。

Sort類

public class Sort {
    /**
     * 時間復雜度：O(N^2)
     * 空間復雜度：O(1)
     * 穩(wěn)定性：穩(wěn)定的排序
     * @param array
     */
    //直接插入排序
    public static void insertSort(int[] arr){
        for (int i = 1; i < arr.length; i++) {
            int tmp = arr[i];
            int j = i-1;
            for (; j >= 0; j--) {
                if(arr[j] > tmp){
                    arr[j+1] = arr[j];
                }else{
                    arr[j+1] = tmp;
                    break;
                }
            }
            //確保j位置的數(shù)，也就是前一個數(shù)能換位成功
            arr[j+1] = tmp;
        }
    }
}

Test類測試類

public class Test {
    public static void main(String[] args) {
        int[] arr = {12,6,59,45,73,26,2};
        System.out.println("排序前：" + Arrays.toString(arr));
        Sort.insertSort(arr);
        System.out.println("排序前：" + Arrays.toString(arr));
    }
}

輸出結(jié)果為：

關(guān)于i=1，且i < arr.length思路，因為數(shù)組是從0開始的，所以arr[6]的位置剛好是最后一位。

通過上面的動圖我們不難發(fā)現(xiàn)，如果數(shù)組一開始越有序，直接插入排序的效率越高，這也為下面的哈希排序提供了思路。

穩(wěn)定性

直接插入排序是穩(wěn)定的，由上面圖片能看到它是具有穩(wěn)定性的，但如果是代碼部分的 arr[j] > tmp 改為：arr[j] >= tmp，以上面的2a和2b為例，它們的順序就會發(fā)生變化。那么這還能說直接插入排序是穩(wěn)定的嗎？

當然能，因為本身是一個穩(wěn)定的排序，那么可以實現(xiàn)為不穩(wěn)定的。

但是，如果一個排序本身是不穩(wěn)定的，那就不能實現(xiàn)穩(wěn)定的排序。

哈希排序

哈希排序可以看作是直接插入排序的優(yōu)化，先通過 gap來不斷簡化其中的有序性，然后再用直接插入排序，越有序，直接插入排序的時間復雜度越小，速度越快。

通過間隔分為不同的組，組內(nèi)進行排序，然后再縮短gap來進行再次排序。

代碼為

public static void shellInsert(int[] array){
    int gap = array.length;
    while(gap > 1){
        gap /= 2;
        shell(array, gap);
    }
}

private static void shell(int[] array, int gap) {
    for (int i = gap; i < array.length; i++) {
        int tmp = array[i];
        int j = i-gap;
        for (; j >= 0; j-= gap) {
            if(array[j] > tmp){
                array[j+gap] = array[j];
            }else{
                array[j+gap] = tmp;
                break;
            }
        }
        array[j+gap] = tmp;
    }
}

到這里，插入排序中的直接插入排序和希爾排序就結(jié)束了，接下來我會繼續(xù)給出剩下排序的思路和代碼。