快捷導(dǎo)航

圖解Java經(jīng)典算法插入排序的原理與實現(xiàn)

更新時間：2022年09月10日 09:45:23 作者：Binaire-沐辰

插入排序的算法描述是一種簡單直觀的排序算法。其原理是通過構(gòu)建有序序列，對于未排序數(shù)據(jù)，在已排序序列中從后向前掃描，找到相應(yīng)位置并插入。本文將用Java語言實現(xiàn)插入排序算法并進行可視化，感興趣的可以了解一下

一、算法介紹

插入排序，也稱為直接插入排序。插入排序是簡單排序中效率最好的一種，它也是學習其他高級排序的基礎(chǔ)，比如希爾排序/快速排序，所以非常重要，而它相對于選擇排序的優(yōu)點就在于比較次數(shù)幾乎是少了一半。

二、算法思想

每次將待排序的元素插入到已排序的序列中，直至全部插入完成。

三、算法原理

把所有元素分為兩個序列，將第一待排序序列第一個元素看做一個有序序列，把第二個元素到最后一個元素當成是未排序序列。
從未排序序列中的第一個元素開始，向已排序的序列中插入
倒序遍歷已排序序列，依次和待插入的元素比較，找到一個小于或等于待插入的元素，插入到該元素后面，其余元素向后移動一位

四、動圖演示

五、代碼實現(xiàn)

核心代碼

public class InsertionSort {
    //  插入排序
    public static void sort(Comparable[] a){
       for (int i = 1;i < a.length;i++){
           for (int j = i;j > 0;j--){
               //比較索引j處的值與索引j-1處的值,如果j-1索引處的值大，則交換數(shù)據(jù)，反之，則找到了合適的位置，退出循環(huán)
               if (greater(a[j - 1],a[j])){
                   swap(a,j - 1,j);
               }else{
                   break;
               }
           }
       }
    }
    //比較 v 是否大于 w
    public static boolean greater(Comparable v,Comparable w){
        return v.compareTo(w) > 0;
    }
    //數(shù)組元素交換位置
    private static void swap(Comparable[] a,int i,int j){
        Comparable temp;
        temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
}

方法調(diào)用

public class InsertionSortTest {
    public static void main(String[] args) {
        Integer[] arr = {3,44,38,5,47,15,36,26,27};
        InsertionSort.sort(arr);
        System.out.println(Arrays.toString(arr));
    }
}
//排序前：{3,44,38,5,47,15,36,26,27}
//排序后：{3,5,15,26,27,36,38,44,47}