Java數據結構與算法——插入排序

騫諱護發(fā)布于2019-08-15 15:19 / 1981人閱讀

摘要：當序列本身有序時，插入排序的時間復雜度為。因為此時的分區(qū)內數據往往是近似有序的，所以使用快排并不一定優(yōu)于插入排序。

聲明：碼字不易，轉載請注明出處，歡迎文章下方討論交流。

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

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

java數據結構與算法——快速排序
java數據結構與算法——桶排序

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

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

插入排序是在待排序數組里插入數據。一般我們認為插入排序就是往一個已經排好序的數列中插入一個元素，使得插入這個數以后，數組仍然有序。

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

首先需要明確待排序的數組由兩部分組成，一部分是已經排好序的部分，另一部分是待排序的部分。

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

一直重復步驟2，直到待排元素已經沒有元素可進行插入時，停止操作，當前數列為已排好序的數列。

2、插入排序java代碼實現

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

public class InsertSort {
    private int[] array;
    public InsertSort(int[] array){
        this.array = array;
    }
    
    public void insertSort(){
        if(array==null){
            throw new RuntimeException("沒有待排數組");
        }
        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(){  //用于打印排完序后的數組
        for(int i=0;i
測試程序
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、插入排序的特點及性能
插入排序和玩撲克牌摸牌后在手中排序一樣的原理，比較容易理解。插入排序在序列近似有序時，效率比較高，因為此時減少了比較和移動的次數。
從原理和代碼來看，插入排序的時間復雜度尾O(n^2)，外層循環(huán)執(zhí)行n次，內層在最壞的情況下也執(zhí)行n次，并且除了比較操作還有移動操作。最好的情況是序列近似有序，這時內層循環(huán)只需比較及移動較少個元素即可完成。當序列本身有序時，插入排序的時間復雜度為O(n)。因此，在數列越有序，效率越高。
空間復雜度為O(1)，是常量級的。因為只用了一個變量暫存每次未排好序的首個元素。
插入排序是穩(wěn)定的排序算法，因為是在相對排好序的基礎上進行比較和移動，所以可以保持相對順序不變，所以是穩(wěn)定的排序算法。
4、插入排序的適用場景
插入排序的特點是在近似有序的情況下效率比較高。但因為其時間復雜度為O(n^2)，所以通常并不多帶帶適用。在所有的排序算法中，我們優(yōu)先使用快速排序?？焖倥判蛟诜謪^(qū)規(guī)模達到一定的值時（比如10左右），我們改用插入排序算法排該分區(qū)。因為此時的分區(qū)內數據往往是近似有序的，所以使用快排并不一定優(yōu)于插入排序。在很多高級語言在內部對快速排序的實現中，也是在分區(qū)達到一定規(guī)模改用插入排序來排該分區(qū)。
其他排序算法索引(待更)
java數據結構與算法——快速排序
java數據結構與算法——桶排序
碼字不易，如對您有幫助，歡迎點贊收藏打賞^_^

云服務器 GPU云服務器 java插入排序算法插入排序算法 java插入排序優(yōu)化插入排序java

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

轉載請注明本文地址：http://systransis.cn/yun/68993.html

數據結構與算法——常用排序算法及其Java實現

摘要：數據結構與算法常用數據結構及其實現經過前面文章的鋪墊，我們鞏固了基礎數據結構的知識，接下來就可以進入算法的鞏固階段了。首先我們來看常見的排序算法。同樣的小規(guī)模數據轉換為插入排序會有效果提升。它只能對整數進行排序。數據結構與算法——常用數據結構及其Java實現經過前面文章的鋪墊，我們鞏固了基礎數據結構的知識，接下來就可以進入算法的鞏固階段了。首先我們來看常見的排序算法。冒泡排序原理...

eternalshallow 2019-08-15 13:48 評論0 收藏0
JavaScript算法 ,Python算法,Go算法,java算法,C#算法系列之插入排序

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

GeekQiaQia 2019-08-21 11:41 評論0 收藏0
JavaScript算法 ,Python算法,Go算法,java算法,C#算法系列之插入排序

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

cgspine 2019-08-16 10:33 評論0 收藏0
JavaScript算法 ,Python算法,Go算法,java算法,C#算法系列之插入排序

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

lufficc 2019-07-31 10:56 評論0 收藏0
八大排序算法Java實現

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

Coly 2019-08-15 11:57 評論0 收藏0