直接插入排序

来源:https://www.cnblogs.com/yhzhou/archive/2018/05/25/9091036.html
-Advertisement-
Play Games

基本思想 每一趟將一個待排序的記錄,按其關鍵字的大小插入到已經排好序的一組記錄的適當位置上,直到所有待排序記錄全部插入為止。 排序過程 1.初始化無序區、有序區,待排序數組的第一個元素為有序區,剩餘元素為無序區; 2.遍歷無序區,將無序區每一個元素插入到有序區的正確位置上; Java演算法實現 /** ...


基本思想

每一趟將一個待排序的記錄,按其關鍵字的大小插入到已經排好序的一組記錄的適當位置上,直到所有待排序記錄全部插入為止。

排序過程

1.初始化無序區、有序區,待排序數組的第一個元素為有序區,剩餘元素為無序區;

2.遍歷無序區,將無序區每一個元素插入到有序區的正確位置上;

Java演算法實現

/**
 * 排序介面類
 * Created by zhouyh on 2018/5/25.
 */
public abstract class ISort {
    public abstract int[] sort(int[] array);
}

/**
 * 直接插入排序
 * Created by zhouyh on 2018/5/25.
 */
public class DirectInsertSort extends ISort {
    @Override
    public int[] sort(int[] array) {
        int tmp;
        for (int i=1; i<array.length; i++){
            tmp = array[i]; //array[i]的拷貝
            //如果右側無序區第一個元素array[i] < array[i-1]小於左側有序區最後一個元素
            //需要將左側有序區比array[i]大的元素後移
            if (array[i] < array[i-1]){
                int j = i-1;
                while (j>=0 && tmp<array[j]){
                    array[j+1] = array[j];
                    j--;
                }
                array[j+1] = tmp;
            }
        }
        return array;
    }
}
View Code

Python代碼實現

def dirInsertSort(reList):
    length = len(reList)
    for i in range(1, length):
        for j in range(i):
            if reList[i] < reList[j]:
                reList.insert(j, reList[i])
                reList.pop(i+1)
                break
    return reList

relist = [1, 23, 12, 7, 34, 10, 51]

print(dirInsertSort(relist))
View Code

性能分析

時間複雜度,在比較的數組有序的情況下,為O(n),即此刻比較次數n-1次,移動次數0;在最壞的情況下,即數組逆序的情況下,為O(n^2),平均時間複雜度為O(n^2)

空間複雜度,直接排序的過程中,僅用到了一個臨時變數,空間複雜端為O(1)

穩定性,直接插入排序為穩定排序,即排序前後的元素位置還是保持和排序前的前後順序一致,例{2①,45,12,2④,3},排序後{2①,2④,3,12,45},其中兩個2的前後順序保持一致。

使用場景

在數組包含的元素數量較小情況下,可以選擇插入排序,元素數量較大的情況下,不適用,因此時移動元素的次數較多;

在數組基本有序的情況下,適合使用插入排序,此時時間複雜度基本上為O(n)


您的分享是我們最大的動力!

-Advertisement-
Play Games
更多相關文章
  • 上一篇文章聊了聊基於PAX的混合存儲結構的RCFile,其實這裡筆者還瞭解一些八卦,RCfile的主力團隊都是來自中科院的童鞋在Facebook完成的,算是一個由華人主導的編碼項目。但是RCfile仍然存在一些缺陷,後續被 HortonWorks 盯上之後上馬了 ORCFile 格式,而老對頭 Cl ...
  • 這段時間談戀愛了,也就沒更新隨筆。後天就軟考了,不過我已經抱著失敗是成功他媽的準備了。做軟體不能急,要穩著性子做幾年再說,剛畢業的應屆生啥都想學,老想一口吃個胖子,沒有5年以上的工作經驗,就是再NB也不行,搞技術的要有工匠精神,而工匠精神必須沉浸下去搞很多年技術。沒有耐心研究技術,貪多求快,這樣不適 ...
  • 本書是Eric Evans對他自己寫的《領域驅動設計-軟體核心複雜性應對之道》的一本字典式的參考書,可用於快速查找《領域驅動設計》中的諸多概念及其簡明解釋。 其它本系列其它文章地址: [譯文]Domain Driven Design Reference(一)—— 前言 [譯文]Domain Driv ...
  • 分散式架構的演進過程 一.分散式架構的發展歷史 1946年,世界上第一臺電子電腦在美國的賓夕法尼亞大學誕生,它的名字是:ENICAC ,這台電腦的體重比較大,計算速度也不快,但是而代表了電腦時代的到來,再以後的互聯網的發展中也有基礎性的意義。 電腦的組成是有五部分完成的,分別是:輸入設備,輸 ...
  • 面向對象之 結構體和類的區別 1.結構體是一種值類型,而類是引用類型。值類型用於存儲數據的值,引用類型用於存儲對實際數據的引用。 那麼結構體就是當成值來使用的,類則通過引用來對實際數據操作。 2.結構使用棧存儲(Stack Allocation),而類使用堆存儲(Heap Allocation) 棧 ...
  • Java開源生鮮電商平臺-優惠券設計與架構(源碼可下載) 說明:現在電商白熱化的程度,無論是生鮮電商還是其他的電商等等,都會有促銷的這個體系,目的就是增加訂單量與知名度等等 那麼對於Java開源生鮮電商平臺而言,我們採用優惠券的這種方式進行促銷。(補貼價格戰對燒錢而言非常的恐怖的,太燒錢了) 1. ...
  • 索引: 開源Spring解決方案--lm.solution 參看代碼 GitHub: solution/pom.xml pojo/pom.xml mapper/pom.xml common/pom.xml service/pom.xml console/pom.xml web/pom.xml web ...
  • 簡單創建json格式文件 核心就兩點: addProperty 添加屬性(也就是加鍵值對) add是添加 另外的object對象 然後直接toString()輸出 核心代碼如下; ...
一周排行
    -Advertisement-
    Play Games
  • 移動開發(一):使用.NET MAUI開發第一個安卓APP 對於工作多年的C#程式員來說,近來想嘗試開發一款安卓APP,考慮了很久最終選擇使用.NET MAUI這個微軟官方的框架來嘗試體驗開發安卓APP,畢竟是使用Visual Studio開發工具,使用起來也比較的順手,結合微軟官方的教程進行了安卓 ...
  • 前言 QuestPDF 是一個開源 .NET 庫,用於生成 PDF 文檔。使用了C# Fluent API方式可簡化開發、減少錯誤並提高工作效率。利用它可以輕鬆生成 PDF 報告、發票、導出文件等。 項目介紹 QuestPDF 是一個革命性的開源 .NET 庫,它徹底改變了我們生成 PDF 文檔的方 ...
  • 項目地址 項目後端地址: https://github.com/ZyPLJ/ZYTteeHole 項目前端頁面地址: ZyPLJ/TreeHoleVue (github.com) https://github.com/ZyPLJ/TreeHoleVue 目前項目測試訪問地址: http://tree ...
  • 話不多說,直接開乾 一.下載 1.官方鏈接下載: https://www.microsoft.com/zh-cn/sql-server/sql-server-downloads 2.在下載目錄中找到下麵這個小的安裝包 SQL2022-SSEI-Dev.exe,運行開始下載SQL server; 二. ...
  • 前言 隨著物聯網(IoT)技術的迅猛發展,MQTT(消息隊列遙測傳輸)協議憑藉其輕量級和高效性,已成為眾多物聯網應用的首選通信標準。 MQTTnet 作為一個高性能的 .NET 開源庫,為 .NET 平臺上的 MQTT 客戶端與伺服器開發提供了強大的支持。 本文將全面介紹 MQTTnet 的核心功能 ...
  • Serilog支持多種接收器用於日誌存儲,增強器用於添加屬性,LogContext管理動態屬性,支持多種輸出格式包括純文本、JSON及ExpressionTemplate。還提供了自定義格式化選項,適用於不同需求。 ...
  • 目錄簡介獲取 HTML 文檔解析 HTML 文檔測試參考文章 簡介 動態內容網站使用 JavaScript 腳本動態檢索和渲染數據,爬取信息時需要模擬瀏覽器行為,否則獲取到的源碼基本是空的。 本文使用的爬取步驟如下: 使用 Selenium 獲取渲染後的 HTML 文檔 使用 HtmlAgility ...
  • 1.前言 什麼是熱更新 游戲或者軟體更新時,無需重新下載客戶端進行安裝,而是在應用程式啟動的情況下,在內部進行資源或者代碼更新 Unity目前常用熱更新解決方案 HybridCLR,Xlua,ILRuntime等 Unity目前常用資源管理解決方案 AssetBundles,Addressable, ...
  • 本文章主要是在C# ASP.NET Core Web API框架實現向手機發送驗證碼簡訊功能。這裡我選擇是一個互億無線簡訊驗證碼平臺,其實像阿裡雲,騰訊雲上面也可以。 首先我們先去 互億無線 https://www.ihuyi.com/api/sms.html 去註冊一個賬號 註冊完成賬號後,它會送 ...
  • 通過以下方式可以高效,並保證數據同步的可靠性 1.API設計 使用RESTful設計,確保API端點明確,並使用適當的HTTP方法(如POST用於創建,PUT用於更新)。 設計清晰的請求和響應模型,以確保客戶端能夠理解預期格式。 2.數據驗證 在伺服器端進行嚴格的數據驗證,確保接收到的數據符合預期格 ...