Java插入排序算法

1、排序原理

插入排序是將數(shù)組中的數(shù)據(jù)分為兩個(gè)區(qū)間，已排序區(qū)間和未排序區(qū)間，其中已排序區(qū)間初始只有一個(gè)元素，就是數(shù)組的第一個(gè)元素。插入算法的核心思想是取未排序區(qū)間中的元素，在已排序區(qū)間中找到合適的插入位置將其插入，并保證已排序區(qū)間數(shù)據(jù)一直有序。重復(fù)這個(gè)過程，直到未排序區(qū)間中元素為空，算法結(jié)束。通過一張動(dòng)態(tài)圖，來直觀感受一下，要排序的數(shù)組為：[4，5，6，1，3，2]，正序排序

1.1、排序過程詳解

要排序的數(shù)組為：[4，5，6，1，3，2] ，假設(shè) a為已排序區(qū)間，b為未排序區(qū)間，初始a=[4] ，b=[5 ,6, 1, 3, 2]

第一次遍歷未排序區(qū)間：

未排序區(qū)間中的 5 依次與已排序區(qū)間中的數(shù)據(jù)[4]比較

5和4比較，5大于4，不進(jìn)行數(shù)據(jù)移動(dòng)，結(jié)束此次遍歷。此時(shí)排序區(qū)間 a=[4，5] 未排序區(qū)間b=[ 6, 1, 3, 2]，結(jié)果：[4，5，6，1，3，2]

第二次遍歷未排序區(qū)間：

未排序區(qū)間中的 6 依次與已排序區(qū)間中的數(shù)據(jù)[4,5]比較

6和5比較，6大于5，不進(jìn)行數(shù)據(jù)移動(dòng)，結(jié)束此次遍歷。此時(shí)排序區(qū)間 a=[4，5，6] ，未排序區(qū)間b=[ 1, 3, 2]，結(jié)果：[4，5，6，1，3，2]

第三次遍歷未排序區(qū)間：

未排序區(qū)間中的 1 依次與已排序區(qū)間中的數(shù)據(jù)[4,5,6]比較

1和6比較，1小于6，進(jìn)行數(shù)據(jù)移動(dòng)，結(jié)果：[4，5，1，6，3，2]

1和5比較，1小于5，進(jìn)行數(shù)據(jù)移動(dòng)，結(jié)果：[4，1，5，6，3，2]

1和4比較，1小于4，進(jìn)行數(shù)據(jù)移動(dòng)，結(jié)果：[1，4，5，6，3，2] ，此時(shí)1在已排序區(qū)間中找到合適的插入位置，此時(shí)排序區(qū)間 a=[1，4，5，6] ，未排序區(qū)間b=[3, 2]

第四次遍歷未排序區(qū)間：

未排序區(qū)間中的 3 依次與已排序區(qū)間中的數(shù)據(jù)[1，4，5，6]比較

排序后結(jié)果：[1，3，4，5，6，2]，此時(shí)排序區(qū)間 a=[1，3，4，5，6] ，未排序區(qū)間b=[ 2]

第五次遍歷未排序區(qū)間：

未排序區(qū)間中的 2 依次與已排序區(qū)間中的數(shù)據(jù)[1，3，4，5，6]比較

排序后結(jié)果：[1，2，3，4，5，6]，此時(shí)排序區(qū)間 a=[1，2，3，4，5，6] ，未排序區(qū)間為空b=[ ]，排序結(jié)束

2、代碼實(shí)現(xiàn)

明白了上面的原理，代碼實(shí)現(xiàn)起來就容易多了

/**     * 插入排序     * @param arr     * @return     */    public static int[] insertionSort(int[] arr) {        for (int i = 1; i < arr.length; i++) {            //待排序元素            int value=arr[i];            //已排序元素下標(biāo)            int insertIndex=i-1;            //使用待排序元素依次與已排序區(qū)的元素相比較            while (insertIndex>=0&&value<arr[insertIndex]){                arr[insertIndex+1]=arr[insertIndex];                insertIndex--;            }            //把當(dāng)前未排序數(shù)據(jù)插入到已排序區(qū)間            arr[insertIndex+1]=value;        }        return arr;    }

3、算法分析

3.1、時(shí)間復(fù)雜度

• 最好情況：T(n)=O(n)
• 最壞情況：T(n)=O(n^2)
• 平均情況：T(n)=O(n^2)

3.2、是否穩(wěn)定

在插入排序中，對(duì)于值相同的元素，我們可以選擇將后面出現(xiàn)的元素，插入到前面出現(xiàn)元素的后面，這樣就可以保持原有的前后順序不變，所以插入排序是穩(wěn)定的排序算法。

到此這篇關(guān)于Java排序算法中的插入排序算法實(shí)現(xiàn)的文章就介紹到這了,更多相關(guān)Java插入排序算法內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論