直接插入排序

mgckid 發布于2019-08-14 15:11 / 978人閱讀

摘要：插入排序在實現上，通常采用排序即只需用到的額外空間，因而在從后向前掃描過程中，需要反復把已排序元素逐步向后挪位，為最新元素提供插入空間。兩個相同的保持他們原來的前后順序，所以直接插入排序是穩定的。

概述

插入排序是一種簡單直觀的排序算法。它的工作原理是通過構建有序序列，對于未排序數據，在已排序序列中從后向前掃描，找到相應位置并插入。插入排序在實現上，通常采用 in-place 排序（即只需用到O(1)的額外空間），因而在從后向前掃描過程中，需要反復把已排序元素逐步向后挪位，為最新元素提供插入空間。

換句話說，就是：

假設在序號 i 之前的元素即 [0... i-1] 都已經排好序，本趟需要找到 i 對應的元素 x 的正確位置 k ，在尋找這個位置 k 的過程中逐個將比較過的元素往后移一位，為元素 x “騰位置”，最后將 k 位置對應的元素值賦為 x ，插入排序的時間復雜度和空間復雜度分別為 O(n²) 和 O(1)。

步驟

從第一個元素開始，該元素可以認為已經被排序

取出下一個元素，在已經排序的元素序列中從后向前掃描

如果該元素（已排序）大于新元素，將該元素移到下一位置

重復步驟3，直到找到已排序的元素小于或者等于新元素的位置

將新元素插入到該位置中

重復步驟2，直到排好序為止

實例

舉個簡單的例子，幫助理解。

原始數據：

3 5 2 6 2

第一輪，把 3 作為已經排好序的，取出 5 與 3 進行比較，5 大于 3 位置保持不變，新的有序組為 [3 5]

3 5 2 6 2

第二輪，取出第一個 2 ，從已排序的 [3 5] 數組從后往前比較，與 5 比較，小于 5，將 5 向后移動一個位置，再與 3 比較，小于 3，將 3 向后移動一個位置，前面沒有了，將 2 放置在原來 3 的位置，新的有序組為 [2 3 5]

2 3 5 6 2

第三輪，取出 6 ，與 5 比較，5 保持不動，新的有序組 [2 3 5 6]

2 3 5 6 2

第四輪，取出 2 ，與 6 比較，6 向后移動一位，與 5 比較，5 向后移動一位，與 3 比較，3 向后移動一位，與 2 比較，不需移動，將取出的 2 放到原來 3 的位置即可，至此完成排序。

2 2 3 5 6

兩個相同的 2 保持他們原來的前后順序，所以直接插入排序是穩定的。

代碼實現(Java)

package com.coder4j.main.arithmetic.sorting;
    
public class StraightInsertion {

    /**
     * 直接插入排序
     * 
     * @param array
     * @return
     */
    public static int[] sort(int[] array) {
        // 將第一個i=0作為已排序組
        for (int i = 1; i < array.length; i++) {
            System.out.println("第" + i + "輪比較結果：");
            
            // 取出i索引待排序元素
            int temp = array[i];
            int j;
            // 從已排序數組后面往前逐個比較，確定i元素的位置，并將相應的元素后移一位
            for (j = i - 1; j >= 0 && temp < array[j]; j--) {
                array[j + 1] = array[j];
            }
            // 找到了位置
            array[j + 1] = temp;
            // 輸出此輪排序結果
            for (int k : array) {
                System.out.print(k + " ");
            }
            System.out.println();
        }
        return array;
    }

    public static void main(String[] args) {
        int[] array = { 3, 5, 2, 6, 2 };
        int[] sorted = sort(array);
        System.out.println("最終結果");
        for (int i : sorted) {
            System.out.print(i + " ");
        }
    }

}

測試輸出結果：

第1輪比較結果：
3 5 2 6 2 
第2輪比較結果：
2 3 5 6 2 
第3輪比較結果：
2 3 5 6 2 
第4輪比較結果：
2 2 3 5 6 
最終結果
2 2 3 5 6

經測試，與實例中結果一致。

GPU云服務器云服務器直接插入排序 php 實現直接插入直接選擇排序插入排序

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

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/65417.html

【算法】插入排序——希爾排序+直接插入排序

希爾排序在介紹希爾排序之前，先了解一下直接插入排序文章目錄希爾排序一、直接插入排序1. 單趟排序2. 直接插入排序二、希爾排序三、測試希爾排序和直接插入排序性能一、直接插入排序 1. 單趟排序 x插入一個有序區間這里end是指向數組最后一個元素 2. 直接插入排序根據上面的單趟排序啟發 end是數組的最后一個元素，end之后的元素都是待排序一個關鍵的判斷點，end和...

GitChat 2021-11-17 09:33 評論0 收藏0
JS中可能用得到的全部的排序算法

本篇有7k+字, 系統梳理了js中常見的12種排序算法。除了基本排序算法，文章還包含了希爾排序、堆排序、桶排序等較為復雜的排序實現，如果喜歡請點贊支持~謝謝. 原文: http://louiszhai.github.io/20... 導讀排序算法可以稱得上是我的盲點, 曾幾何時當我知道Chrome的Array.prototype.sort使用了快速排序時, 我的內心是奔潰的(啥是快排, 我只知道...

verano 2019-08-20 15:08 評論0 收藏0
排序（2）：直接插入排序

摘要：一前言直接插入排序序是一種最簡單的插入排序。所以，數據越接近正序，直接插入排序的算法性能越好。算法穩定性直接插入排序的過程中，不需要改變相等數值元素的位置，所以它是穩定的算法。一、前言直接插入排序（Insertion Sort）序是一種最簡單的插入排序。為簡化問題，我們下面只討論升序排序。二、算法思想插入排序：每一趟將一個待排序的記錄，按照其關鍵字的大小插入到有序隊列的合適位置里，...

付倫 2019-07-31 10:08 評論0 收藏0
【數據結構初階】第九篇——八大經典排序算法總結（圖解+動圖演示+代碼實現+八大排序比較）

摘要：本篇博客我要來和大家一起聊一聊數據結構初階中的最后一篇博客八大經典排序算法的總結，其中會介紹他們的原來，還有復雜度的分析以及各種優化。快速排序遞歸版本快速排序是于年提出的一種二叉樹結構的交換排序方法。 ...

xiaowugui666 2021-11-25 09:43 評論0 收藏0
Java數據結構與算法——插入排序

摘要：當序列本身有序時，插入排序的時間復雜度為。因為此時的分區內數據往往是近似有序的，所以使用快排并不一定優于插入排序。聲明：碼字不易，轉載請注明出處，歡迎文章下方討論交流。前言：Java數據結構與算法專題會不定時更新，歡迎各位讀者監督。本篇文章介紹排序算法中插入排序算法，包括插入排序的思路，適用場景，性能分析，java代碼等 0、其他排序算法索引(待更) java數據結構與算法——快速...

騫諱護 2019-08-15 15:19 評論0 收藏0