成人无码视频,亚洲精品久久久久av无码,午夜精品久久久久久毛片,亚洲 中文字幕 日韩 无码

資訊專(zhuān)欄INFORMATION COLUMN

Java數(shù)據(jù)結(jié)構(gòu)與算法——插入排序

騫諱護(hù) / 2037人閱讀

摘要：當(dāng)序列本身有序時(shí)，插入排序的時(shí)間復(fù)雜度為。因?yàn)榇藭r(shí)的分區(qū)內(nèi)數(shù)據(jù)往往是近似有序的，所以使用快排并不一定優(yōu)于插入排序。

聲明：碼字不易，轉(zhuǎn)載請(qǐng)注明出處，歡迎文章下方討論交流。

前言：Java數(shù)據(jù)結(jié)構(gòu)與算法專(zhuān)題會(huì)不定時(shí)更新，歡迎各位讀者監(jiān)督。本篇文章介紹排序算法中插入排序算法，包括插入排序的思路，適用場(chǎng)景，性能分析，java代碼等

0、其他排序算法索引(待更)

java數(shù)據(jù)結(jié)構(gòu)與算法——快速排序
java數(shù)據(jù)結(jié)構(gòu)與算法——桶排序

1、插入排序的思想及原理

插入排序一般分為直接插入排序和二分插入排序，本文只介紹直接插入排序，兩者的區(qū)別僅在于插入的方式不一樣。

插入排序是在待排序數(shù)組里插入數(shù)據(jù)。一般我們認(rèn)為插入排序就是往一個(gè)已經(jīng)排好序的數(shù)列中插入一個(gè)元素，使得插入這個(gè)數(shù)以后，數(shù)組仍然有序。

下面具體介紹下插入排序的思路：

首先需要明確待排序的數(shù)組由兩部分組成，一部分是已經(jīng)排好序的部分，另一部分是待排序的部分。

接著我們每次選取待排序部分的第一個(gè)元素，分別與前面排好序的元素進(jìn)行比較。當(dāng)大于前面元素時(shí)，可以將該元素直接進(jìn)入已排好序的部分； 當(dāng)小于前面元素時(shí)，需要把這個(gè)元素拿出來(lái)暫存，將前面的元素后移，繼續(xù)與前面的元素相比，直到比較到數(shù)組第一個(gè)元素或者出現(xiàn)第一個(gè)小于拿出的這個(gè)元素，這時(shí)停止比較、移動(dòng)，直接把這個(gè)元素放到當(dāng)前空位上。

一直重復(fù)步驟2，直到待排元素已經(jīng)沒(méi)有元素可進(jìn)行插入時(shí)，停止操作，當(dāng)前數(shù)列為已排好序的數(shù)列。

2、插入排序java代碼實(shí)現(xiàn)

首先最外層必定有個(gè)大循環(huán)，用于待排序部分的數(shù)列。還需要一個(gè)內(nèi)層循環(huán)，分別與前面排好序的部分進(jìn)行比較和移動(dòng)，直到找到位置可以進(jìn)行插入。參照撲克牌摸牌后排序

public class InsertSort {
    private int[] array;
    public InsertSort(int[] array){
        this.array = array;
    }
    
    public void insertSort(){
        if(array==null){
            throw new RuntimeException("沒(méi)有待排數(shù)組");
        }
        int length = array.length;
        if(length>0){
            for(int i=1;i0&&array[j-1]>temp;j--){  //原理中的步驟2
                    array[j] = array[j-1];   //移位
                }
                array[j] = temp;   //插入
            }
        }
    }
    
    public void print(){  //用于打印排完序后的數(shù)組
        for(int i=0;i

測(cè)試程序


public class SortTest {
    public static void main(String[] args) {
        insertSortTest();
    }

    private static void insertSortTest(){
        int[] array = {3,5,0,7,1,4,6};
        InsertSort is = new InsertSort(array);
        is.insertSort();
        is.print();
    }
}

3、插入排序的特點(diǎn)及性能

插入排序和玩撲克牌摸牌后在手中排序一樣的原理，比較容易理解。插入排序在序列近似有序時(shí)，效率比較高，因?yàn)榇藭r(shí)減少了比較和移動(dòng)的次數(shù)。


從原理和代碼來(lái)看，插入排序的時(shí)間復(fù)雜度尾O(n^2)，外層循環(huán)執(zhí)行n次，內(nèi)層在最壞的情況下也執(zhí)行n次，并且除了比較操作還有移動(dòng)操作。最好的情況是序列近似有序，這時(shí)內(nèi)層循環(huán)只需比較及移動(dòng)較少個(gè)元素即可完成。當(dāng)序列本身有序時(shí)，插入排序的時(shí)間復(fù)雜度為O(n)。因此，在數(shù)列越有序，效率越高。


空間復(fù)雜度為O(1)，是常量級(jí)的。因?yàn)橹挥昧艘粋€(gè)變量暫存每次未排好序的首個(gè)元素。


插入排序是穩(wěn)定的排序算法，因?yàn)槭窃谙鄬?duì)排好序的基礎(chǔ)上進(jìn)行比較和移動(dòng)，所以可以保持相對(duì)順序不變，所以是穩(wěn)定的排序算法。

4、插入排序的適用場(chǎng)景

插入排序的特點(diǎn)是在近似有序的情況下效率比較高。但因?yàn)槠鋾r(shí)間復(fù)雜度為O(n^2)，所以通常并不多帶帶適用。在所有的排序算法中，我們優(yōu)先使用快速排序?？焖倥判蛟诜謪^(qū)規(guī)模達(dá)到一定的值時(shí)（比如10左右），我們改用插入排序算法排該分區(qū)。因?yàn)榇藭r(shí)的分區(qū)內(nèi)數(shù)據(jù)往往是近似有序的，所以使用快排并不一定優(yōu)于插入排序。在很多高級(jí)語(yǔ)言在內(nèi)部對(duì)快速排序的實(shí)現(xiàn)中，也是在分區(qū)達(dá)到一定規(guī)模改用插入排序來(lái)排該分區(qū)。


其他排序算法索引(待更)
java數(shù)據(jù)結(jié)構(gòu)與算法——快速排序
java數(shù)據(jù)結(jié)構(gòu)與算法——桶排序


碼字不易，如對(duì)您有幫助，歡迎點(diǎn)贊收藏打賞^_^

文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址：http://m.hztianpu.com/yun/68993.html

相關(guān)文章

  • 數(shù)據(jù)結(jié)構(gòu)與算法——常用排序算法及其Java實(shí)現(xiàn)

    摘要：數(shù)據(jù)結(jié)構(gòu)與算法常用數(shù)據(jù)結(jié)構(gòu)及其實(shí)現(xiàn)經(jīng)過(guò)前面文章的鋪墊，我們鞏固了基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)的知識(shí)，接下來(lái)就可以進(jìn)入算法的鞏固階段了。首先我們來(lái)看常見(jiàn)的排序算法。同樣的小規(guī)模數(shù)據(jù)轉(zhuǎn)換為插入排序會(huì)有效果提升。它只能對(duì)整數(shù)進(jìn)行排序。 數(shù)據(jù)結(jié)構(gòu)與算法——常用數(shù)據(jù)結(jié)構(gòu)及其Java實(shí)現(xiàn)經(jīng)過(guò)前面文章的鋪墊，我們鞏固了基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)的知識(shí)，接下來(lái)就可以進(jìn)入算法的鞏固階段了。首先我們來(lái)看常見(jiàn)的排序算法。 冒泡排序 原理...

    eternalshallow 評(píng)論0 收藏0

  • JavaScript算法 ,Python算法,Go算法,java算法,C#算法系列之插入排序

    摘要：常見(jiàn)的內(nèi)部排序算法有插入排序希爾排序選擇排序冒泡排序歸并排序快速排序堆排序基數(shù)排序等。插入排序在實(shí)現(xiàn)上，通常采用排序即只需用到的額外空間的排序，因而在從后向前掃描過(guò)程中，需要反復(fù)把已排序元素逐步向后挪位，為最新元素提供插入空間。 常見(jiàn)的內(nèi)部排序算法有：插入排序、希爾排序、選擇排序、冒泡排序、歸并排序、快速排序、堆排序、基數(shù)排序等。用一張圖概括： showImg(https://segm...

    GeekQiaQia 評(píng)論0 收藏0

  • JavaScript算法 ,Python算法,Go算法,java算法,C#算法系列之插入排序

    摘要：常見(jiàn)的內(nèi)部排序算法有插入排序希爾排序選擇排序冒泡排序歸并排序快速排序堆排序基數(shù)排序等。插入排序在實(shí)現(xiàn)上，通常采用排序即只需用到的額外空間的排序，因而在從后向前掃描過(guò)程中，需要反復(fù)把已排序元素逐步向后挪位，為最新元素提供插入空間。 常見(jiàn)的內(nèi)部排序算法有：插入排序、希爾排序、選擇排序、冒泡排序、歸并排序、快速排序、堆排序、基數(shù)排序等。用一張圖概括： showImg(https://segm...

    cgspine 評(píng)論0 收藏0

  • JavaScript算法 ,Python算法,Go算法,java算法,C#算法系列之插入排序

    摘要：常見(jiàn)的內(nèi)部排序算法有插入排序希爾排序選擇排序冒泡排序歸并排序快速排序堆排序基數(shù)排序等。插入排序在實(shí)現(xiàn)上，通常采用排序即只需用到的額外空間的排序，因而在從后向前掃描過(guò)程中，需要反復(fù)把已排序元素逐步向后挪位，為最新元素提供插入空間。 常見(jiàn)的內(nèi)部排序算法有：插入排序、希爾排序、選擇排序、冒泡排序、歸并排序、快速排序、堆排序、基數(shù)排序等。用一張圖概括： showImg(https://segm...

    lufficc 評(píng)論0 收藏0

  • 八大排序算法Java實(shí)現(xiàn)

    摘要：向后移動(dòng)位簡(jiǎn)單選擇排序基本思想常用于取序列中最大最小的幾個(gè)數(shù)時(shí)。代碼實(shí)現(xiàn)循環(huán)次數(shù)選出最小的值和位置交換位置堆排序基本思想對(duì)簡(jiǎn)單選擇排序的優(yōu)化。 概述 常見(jiàn)的八大排序算法，它們之間的關(guān)系如下： showImg(https://segmentfault.com/img/remote/1460000011395738?w=880&h=671); 直接插入排序 希爾排序 簡(jiǎn)單選擇排序 堆排序...

    Coly 評(píng)論0 收藏0

發(fā)表評(píng)論

0條評(píng)論

閱讀需要支付1元查看
<