X5-1、java數(shù)據(jù)結(jié)構(gòu)---插入排序算法【2020-12-8】

總目錄：地址如下看總綱

http://m.itdecent.cn/p/929ca9e209e8

一、簡單插入排序

1、插入排序概要

插入式排序?qū)儆趦?nèi)部排序法，是對于欲排序的元素以插入的方式找尋該元素的適當(dāng)位置，以達到排序的目的。

2、基本思想

把n個待排序的元素看成為一個有序表和一個無序表，開始時有序表中只包含一個元素，無序表中包含有n-1個元素，排序過程中每次從無序表中取出第一個元素，把它的排序碼依次與有序表元素的排序碼進行比較，將它插入到有序表中的適當(dāng)位置，使之成為新的有序表。


image.png

3、代碼

/**
 * title: 簡單插入排序
 * @author 阿K
 * 2020年12月8日 下午10:38:05 
 */
public class InsertSort {

    public static void main(String[] args) {
//      int[] arr = {101, 34, 119, 1, -1, 89}; 
//      insertSort(arr);
//      System.out.println(Arrays.toString(arr));

        // 創(chuàng)建要給80000個的隨機的數(shù)組
        int[] arr = new int[80000];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = (int) (Math.random() * 8000000);
        }
        new InsertSort(arr);
    }

    //
    public InsertSort(int[] arr) {
        long time = new Date().getTime();
        insertSort(arr);
        long time2 = new Date().getTime();
        System.out.println("使用了：" + (time2 - time) + "毫秒");
    }

    // 直接插入排序 Api
    public static void insertSort(int[] arr) {
        int insertVal = 0;
        int insertIndex = 0;
        for (int i = 1; i < arr.length; i++) {
            // 定義待插入的數(shù)
            insertVal = arr[i];
            // 即arr[1]的前面這個數(shù)的下標(biāo)
            insertIndex = i - 1;

            // 給insertVal 尋找到插入的位置
            // 說明
            // 1. insertIndex >= 0 保證在給insertVal 找插入位置，不越界
            // 2. insertVal < arr[insertIndex] 待插入的數(shù)，還沒有找到插入位置
            // 3. 就需要將 arr[insertIndex] 后移
            while (insertIndex >= 0 && insertVal < arr[insertIndex]) {
                arr[insertIndex + 1] = arr[insertIndex];
                insertIndex--;
            }

            // 當(dāng)退出while循環(huán)時，說明插入的位置找到, insertIndex + 1
            // 判斷是否需要賦值
            if (insertIndex + 1 != i) {
                arr[insertIndex + 1] = insertVal;
            }
        }
    }
}

4、八萬數(shù)據(jù)測試

image.png

二、希爾排序（簡單插入的增強）

1、基本介紹

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

2、思想

image.png

image.png

1、希爾排序時， 對有序序列在插入時采用交換法
2、希爾排序時， 對有序序列在插入時采用移動法(交換法的增強)

3、逐輪分析代碼

/**
 * title: 希爾排序
 * @author 阿K
 * 2020年12月10日 下午11:01:23 
 */
public class ShellSort {

    public static void main(String[] args) {
        int[] arr = { 8, 9, 1, 7, 2, 3, 5, 4, 6, 0 };
        shellSort(arr);
        System.out.println(Arrays.toString(arr));
    }

    // 希爾排序 api
    public static void shellSort(int[] arr) {

        int temp = 0;// 輔助變量
        int count = 0;

        // 希爾排序的第1輪排序
        // 因為第1輪排序，是將10個數(shù)據(jù)分成了 5組
        // [3, 5, 1, 6, 0, 8, 9, 4, 7, 2]
        for (int i = 5; i < arr.length; i++) {
            // 遍歷各組中所有的元素(共5組，每組有2個元素), 步長5
            for (int j = i - 5; j >= 0; j -= 5) {
                // 如果當(dāng)前元素大于加上步長后的那個元素，說明交換
                if (arr[j] > arr[j + 5]) {
                    temp = arr[j];
                    arr[j] = arr[j + 5];
                    arr[j + 5] = temp;
                }
            }
        }

        // 希爾排序的第2輪排序
        // 因為第2輪排序，是將10個數(shù)據(jù)分成了 2組
        // [0, 2, 1, 4, 3, 5, 7, 6, 9, 8]
        for (int i = 2; i < arr.length; i++) {
            // 遍歷各組中所有的元素(共5組，每組有2個元素), 步長5
            for (int j = i - 2; j >= 0; j -= 2) {
                // 如果當(dāng)前元素大于加上步長后的那個元素，說明交換
                if (arr[j] > arr[j + 2]) {
                    temp = arr[j];
                    arr[j] = arr[j + 2];
                    arr[j + 2] = temp;
                }
            }
        }

        // 希爾排序的第3輪排序
        // 因為第3輪排序，是將10個數(shù)據(jù)分成了 2/2= 1 組
        // [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
        for (int i = 1; i < arr.length; i++) {
            // 遍歷各組中所有的元素(共5組，每組有2個元素), 步長5
            for (int j = i - 1; j >= 0; j -= 1) {
                // 如果當(dāng)前元素大于加上步長后的那個元素，說明交換
                if (arr[j] > arr[j + 1]) {
                    temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
    }
}

4、代碼（交換法）

// 希爾排序 api
    public static void shellSort2(int[] arr) {
        int temp = 0;// 輔助變量
        int count = 0;
        
        // 根據(jù)前面的逐步分析，使用循環(huán)處理
        // gap 控制組數(shù)
        for(int gap = arr.length/2;gap>0;gap/=2) {
            for(int i=gap;i<arr.length;i++) {
                // 遍歷各組中所有的元素(共gap組，每組有 (arr.length/gap) 個元素), 步長gap
                for(int j=i-gap;j>=0;j-=gap) {
                    // 如果當(dāng)前元素大于加上步長后的那個元素，說明交換
                    if(arr[j]>arr[j+gap]) {
                        temp = arr[j];
                        arr[j] = arr[j+gap];
                        arr[j+gap] = temp;
                    }
                }
            }
        }
    }

5、代碼（移位法）

    // 希爾排序 api 移位法
    public static void shellSort3(int[] arr) {

        // 增量gap, 并逐步的縮小增量
        for (int gap = arr.length / 2; gap > 0; gap /= 2) {
            // 從第gap個元素，逐個對其所在的組進行直接插入排序
            for (int i = gap; i < arr.length; i++) {
                int j = i;// 保存待插入的索引
                int temp = arr[j];// 記錄待插入的值
                if (arr[j] < arr[j - gap]) {// 記住 gap是步長值
                    while (j - gap >= 0 && temp < arr[j - gap]) {
                        // 找到了適當(dāng)位置，插入（移動）
                        arr[j] = arr[j - gap];
                        j -= gap;
                    }
                    // 當(dāng)退出while后，就給temp找到插入的位置
                    arr[j] = temp;
                }
            }
        }
    }

6、八萬數(shù)據(jù)效率

image.png

7、最終完整代碼

package com.kk.datastructure.sort;

import java.util.Arrays;
import java.util.Date;


/**
 * title: 希爾排序
 * @author 阿K
 * 2020年12月10日 下午11:25:31 
 */
public class ShellSort {

    public static void main(String[] args) {
//      int[] arr = { 8, 9, 1, 7, 2, 3, 5, 4, 6, 0 };
//      shellSort3(arr);
//      System.out.println(Arrays.toString(arr));

        // 創(chuàng)建80000個的隨機的數(shù)組
        int[] arr = new int[80000];
        for (int i = 0; i < 80000; i++) {
            arr[i] = (int) (Math.random() * 8000000); // 生成一個[0, 8000000) 數(shù)
        }
        new ShellSort(arr, "2");
        new ShellSort(arr, "3");
    }

    public ShellSort(int[] arr, String zhiling) {
        long time = new Date().getTime();
        if ("2".equals(zhiling)) {
            shellSort2(arr);
            long time2 = new Date().getTime();
            System.out.println("希爾排序（交換法運行）：" + (time2 - time) + "毫秒");
        } else {
            shellSort3(arr);
            long time2 = new Date().getTime();
            System.out.println("希爾排序（移位法運行）：" + (time2 - time) + "毫秒");
        }

    }

    // 希爾排序 api
    public static void shellSort(int[] arr) {

        int temp = 0;// 輔助變量

        // 希爾排序的第1輪排序
        // 因為第1輪排序，是將10個數(shù)據(jù)分成了 5組
        // [3, 5, 1, 6, 0, 8, 9, 4, 7, 2]
        for (int i = 5; i < arr.length; i++) {
            // 遍歷各組中所有的元素(共5組，每組有2個元素), 步長5
            for (int j = i - 5; j >= 0; j -= 5) {
                // 如果當(dāng)前元素大于加上步長后的那個元素，說明交換
                if (arr[j] > arr[j + 5]) {
                    temp = arr[j];
                    arr[j] = arr[j + 5];
                    arr[j + 5] = temp;
                }
            }
        }

        // 希爾排序的第2輪排序
        // 因為第2輪排序，是將10個數(shù)據(jù)分成了 2組
        // [0, 2, 1, 4, 3, 5, 7, 6, 9, 8]
        for (int i = 2; i < arr.length; i++) {
            // 遍歷各組中所有的元素(共5組，每組有2個元素), 步長5
            for (int j = i - 2; j >= 0; j -= 2) {
                // 如果當(dāng)前元素大于加上步長后的那個元素，說明交換
                if (arr[j] > arr[j + 2]) {
                    temp = arr[j];
                    arr[j] = arr[j + 2];
                    arr[j + 2] = temp;
                }
            }
        }

        // 希爾排序的第3輪排序
        // 因為第3輪排序，是將10個數(shù)據(jù)分成了 2/2= 1 組
        // [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
        for (int i = 1; i < arr.length; i++) {
            // 遍歷各組中所有的元素(共5組，每組有2個元素), 步長5
            for (int j = i - 1; j >= 0; j -= 1) {
                // 如果當(dāng)前元素大于加上步長后的那個元素，說明交換
                if (arr[j] > arr[j + 1]) {
                    temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
    }

    // 希爾排序 api 交換法
    public static void shellSort2(int[] arr) {
        int temp = 0;// 輔助變量

        // 根據(jù)前面的逐步分析，使用循環(huán)處理
        // gap 控制組數(shù)
        for (int gap = arr.length / 2; gap > 0; gap /= 2) {
            for (int i = gap; i < arr.length; i++) {
                // 遍歷各組中所有的元素(共gap組，每組有 (arr.length/gap) 個元素), 步長gap
                for (int j = i - gap; j >= 0; j -= gap) {
                    // 如果當(dāng)前元素大于加上步長后的那個元素，說明交換
                    if (arr[j] > arr[j + gap]) {
                        temp = arr[j];
                        arr[j] = arr[j + gap];
                        arr[j + gap] = temp;
                    }
                }
            }
        }
    }

    // 希爾排序 api 移位法
    public static void shellSort3(int[] arr) {

        // 增量gap, 并逐步的縮小增量
        for (int gap = arr.length / 2; gap > 0; gap /= 2) {
            // 從第gap個元素，逐個對其所在的組進行直接插入排序
            for (int i = gap; i < arr.length; i++) {
                int j = i;// 保存待插入的索引
                int temp = arr[j];// 記錄待插入的值
                if (arr[j] < arr[j - gap]) {// 記住 gap是步長值
                    while (j - gap >= 0 && temp < arr[j - gap]) {
                        // 找到了適當(dāng)位置，插入（移動）
                        arr[j] = arr[j - gap];
                        j -= gap;
                    }
                    // 當(dāng)退出while后，就給temp找到插入的位置
                    arr[j] = temp;
                }
            }
        }
    }
}
最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時請結(jié)合常識與多方信息審慎甄別。
平臺聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點，簡書系信息發(fā)布平臺，僅提供信息存儲服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容