快捷導(dǎo)航

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

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

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

排序的概念

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

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

常見(jiàn)的排序算法有下面四種：

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

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

插入排序

基本思想：把待排序的記錄按照其關(guān)鍵碼值的大小逐個(gè)插入到一個(gè)已經(jīng)拍好的有序序列中，直到所有的記錄插入完為止，得到一個(gè)新的有序序列。生活中的例子，就像我們?cè)谕険淇伺频臅r(shí)候機(jī)型排序一樣。

直接插入排序

思路：

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

Sort類(lèi)

public class Sort {
    /**
     * 時(shí)間復(fù)雜度：O(N^2)
     * 空間復(fù)雜度：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ù)，也就是前一個(gè)數(shù)能換位成功
            arr[j+1] = tmp;
        }
    }
}

Test類(lèi) 測(cè)試類(lèi)

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思路，因?yàn)閿?shù)組是從0開(kāi)始的，所以arr[6]的位置剛好是最后一位。

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

穩(wěn)定性

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

當(dāng)然能，因?yàn)?本身是一個(gè)穩(wěn)定的排序，那么可以實(shí)現(xiàn)為不穩(wěn)定的。

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

哈希排序

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

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

代碼為

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é)束了，接下來(lái)我會(huì)繼續(xù)給出剩下排序的思路和代碼。