色哟哟视频在线观看-色哟哟视频在线-色哟哟欧美15最新在线-色哟哟免费在线观看-国产l精品国产亚洲区在线观看-国产l精品国产亚洲区久久

0
  • 聊天消息
  • 系統(tǒng)消息
  • 評論與回復(fù)
登錄后你可以
  • 下載海量資料
  • 學(xué)習(xí)在線課程
  • 觀看技術(shù)視頻
  • 寫文章/發(fā)帖/加入社區(qū)
會員中心
电子发烧友
开通电子发烧友VIP会员 尊享10大特权
海量资料免费下载
精品直播免费看
优质内容免费畅学
课程9折专享价
創(chuàng)作中心

完善資料讓更多小伙伴認(rèn)識你,還能領(lǐng)取20積分哦,立即完善>

3天內(nèi)不再提示

時間復(fù)雜度為 O(n^2) 的排序算法

京東云 ? 來源:京東保險 王奕 ? 作者:京東保險 王奕 ? 2024-10-19 16:31 ? 次閱讀
加入交流群
微信小助手二維碼

掃碼添加小助手

加入工程師交流群

作者:京東保險 王奕龍

對于小規(guī)模數(shù)據(jù),我們可以選用時間復(fù)雜度為 O(n2) 的排序算法。因為時間復(fù)雜度并不代表實際代碼的執(zhí)行時間,它省去了低階、系數(shù)和常數(shù),僅代表的增長趨勢,所以在小規(guī)模數(shù)據(jù)情況下, O(n2) 的排序算法可能會比 O(nlogn) 的排序算法執(zhí)行效率高。不過隨著數(shù)據(jù)規(guī)模增大, O(nlogn) 的排序算法是不二選擇。本篇我們主要對 O(n2) 的排序算法進(jìn)行介紹,在介紹之前,我們先了解一下算法特性:

算法特性:

穩(wěn)定性:經(jīng)排序后,若等值元素之間的相對位置不變則為穩(wěn)定排序算法,否則為不穩(wěn)定排序算法

原地排序:是否借助額外輔助空間

自適應(yīng)性: 自適應(yīng)性排序受輸入數(shù)據(jù)的影響,即最佳/平均/最差時間復(fù)雜度不等,而非自適應(yīng)排序時間復(fù)雜度恒定

本篇我們將著重介紹插入排序,選擇排序和冒泡排序了解即可。

插入排序

插入排序的工作方式像 整理手中的撲克牌一樣,即不斷地將每一張牌插入到其他已經(jīng)有序的牌中適當(dāng)?shù)奈恢谩?/p>

插入排序的當(dāng)前索引元素左側(cè)的所有元素都是有序的:若當(dāng)前索引為 i,則 [0, i - 1] 區(qū)間內(nèi)的元素始終有序,這種性質(zhì)被稱為 循環(huán)不變式,即在第一次迭代、迭代過程中和迭代結(jié)束時,這種性質(zhì)始終保持不變。

不過,這些有序元素的索引位置暫時不能確定,因為它們可能需要為更小的元素騰出空間而向右移動。插入排序的代碼實現(xiàn)如下:

    private void sort(int[] nums) {
        for (int i = 1; i < nums.length; i++) {
            int base = nums[i];

            int j = i - 1;
            while (j >= 0 && nums[j] > base) {
                nums[j + 1] = nums[j--];
            }
            nums[j + 1] = base;
        }
    }

它的實現(xiàn)邏輯是取未排序區(qū)間中的某個元素為基準(zhǔn)數(shù) base,將 base 與其左側(cè)已排序區(qū)間元素依次比較大小,并"插入"到正確位置。插入排序?qū)?部分有序(數(shù)組中每個元素距離它的最終位置都不遠(yuǎn)或數(shù)組中只有幾個元素的位置不正確等情況)的數(shù)組排序效率很高。事實上,當(dāng)逆序很少或數(shù)據(jù)量不大(n2和nlogn比較接近)時,插入排序可能比其他任何排序算法都要快,這也是一些編程語言的內(nèi)置排序算法在針對小數(shù)據(jù)量數(shù)據(jù)排序時選擇使用插入排序的原因。

算法特性:

空間復(fù)雜度:O(1)

原地排序

穩(wěn)定排序

自適應(yīng)排序:當(dāng)數(shù)組為升序時,時間復(fù)雜度為 O(n);當(dāng)數(shù)組為降序時,時間復(fù)雜度為 O(n2)

希爾排序

插入排序?qū)τ诖笠?guī)模亂序數(shù)組排序很慢,因為它只會交換相鄰的元素,所以元素只能一步步地從一端移動到另一端,如果最小的元素恰好在數(shù)組的最右端,要將它移動到正確的位置需要移動 N - 1 次。

希爾排序是基于插入排序改進(jìn)的排序算法,它可以交換不相鄰的元素以對數(shù)組的局部進(jìn)行排序,并最終用插入排序?qū)⒕植坑行虻臄?shù)組排序。它的思想是使數(shù)組中間隔為 h 的元素有序(h 有序數(shù)組),如下圖為間隔為 4 的有序數(shù)組:

wKgaomcQeFWAejYVAAF0WDlfIVY746.jpg

排序之初 h 較大,這樣我們能將較小的元素盡可能移動到靠近左端的位置,為實現(xiàn)更小的 h 有序創(chuàng)造便利,最后一次循環(huán)時 h 為 1,便是我們熟悉的插入排序。這就是希爾排序的過程,代碼實現(xiàn)如下:

    private void sort(int[] nums) {
        int N = nums.length;
        int h = 1;
        while (h < N / 3) {
            h = 3 * h + 1;
        }

        while (h >= 1) {
            for (int i = h; i < N; i++) {
                int base = nums[i];

                int j = i - h;
                while (j >= 0 && nums[j] > base) {
                    nums[j + h] = nums[j];
                    j -= h;
                }
                nums[j + h] = base;
            }

            h /= 3;
        }
    }

希爾排序更高效的原因是它權(quán)衡了子數(shù)組的規(guī)模和有序性,它也可以用于大型數(shù)組。排序之初,各個子數(shù)組都很短,排序之后子數(shù)組都是部分有序的,這兩種情況都很適合插入排序。

選擇排序

選擇排序的實現(xiàn)非常簡單:每次選擇未排序數(shù)組中的最小值,將其放到已排序區(qū)間的末尾,代碼實現(xiàn)如下:

    private void sort(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            int min = i;
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[j] < nums[min]) {
                    min = j;
                }
            }
            swap(nums, i, min);
        }
    }

    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

算法特性:

空間復(fù)雜度:O(1)

原地排序

非穩(wěn)定排序:會改變等值元素之間的相對位置

非自適應(yīng)排序:最好/平均/最壞時間復(fù)雜度均為 O(n2)

冒泡排序

冒泡排序通過 連續(xù)地比較與交換相鄰元素實現(xiàn)排序,每輪循環(huán)會將未被排序區(qū)間內(nèi)的最大值移動到數(shù)組的最右端,這個過程就像是氣泡從底部升到頂部一樣,代碼實現(xiàn)如下:

    public void sort(int[] nums) {
        for (int i = nums.length - 1; i > 0; i--) {
            // 沒有發(fā)生元素交換的標(biāo)志位
            boolean flag = true;
            for (int j = 0; j < i; j++) {
                if (nums[j] > nums[j + 1]) {
                    swap(nums, j, j + 1);
                    flag = false;
                }
            }

            if (flag) {
                break;
            }
        }
    }

    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

算法特性:

空間復(fù)雜度:O(1)

原地排序

穩(wěn)定排序

自適應(yīng)排序:經(jīng)過優(yōu)化后最佳時間復(fù)雜度為 O(n)

巨人的肩膀

《算法導(dǎo)論 第三版》第 2.1 章

《算法 第四版》第 2.1 章

《Hello 算法》第 11 章

排序算法-希爾排序

審核編輯 黃宇

聲明:本文內(nèi)容及配圖由入駐作者撰寫或者入駐合作網(wǎng)站授權(quán)轉(zhuǎn)載。文章觀點僅代表作者本人,不代表電子發(fā)燒友網(wǎng)立場。文章及其配圖僅供工程師學(xué)習(xí)之用,如有內(nèi)容侵權(quán)或者其他違規(guī)問題,請聯(lián)系本站處理。 舉報投訴
  • 算法
    +關(guān)注

    關(guān)注

    23

    文章

    4707

    瀏覽量

    95197
  • 排序算法
    +關(guān)注

    關(guān)注

    0

    文章

    53

    瀏覽量

    10237
收藏 0人收藏
加入交流群
微信小助手二維碼

掃碼添加小助手

加入工程師交流群

    評論

    相關(guān)推薦
    熱點推薦

    時間復(fù)雜度是指什么

    原理->微機(jī)原理->軟件工程,編譯原理,數(shù)據(jù)庫數(shù)據(jù)結(jié)構(gòu)1.時間復(fù)雜度時間復(fù)雜度是指執(zhí)行算法所需要的計算工作量,因為整個
    發(fā)表于 07-22 10:01

    各種排序算法時間空間復(fù)雜度、穩(wěn)定性

    各種排序算法時間空間復(fù)雜度、穩(wěn)定性一、排序算法分類:二、
    發(fā)表于 12-21 07:48

    常用的非比較排序算法:計數(shù)排序,基數(shù)排序,桶排序的詳細(xì)資料概述

    這篇文章中我們來探討一下常用的非比較排序算法:計數(shù)排序,基數(shù)排序,桶排序。在一定條件下,它們的時間
    的頭像 發(fā)表于 06-18 15:11 ?7442次閱讀
    常用的非比較<b class='flag-5'>排序</b><b class='flag-5'>算法</b>:計數(shù)<b class='flag-5'>排序</b>,基數(shù)<b class='flag-5'>排序</b>,桶<b class='flag-5'>排序</b>的詳細(xì)資料概述

    常用排序算法分析

    一種是比較排序時間復(fù)雜度O(nlogn) ~ O(n^2
    的頭像 發(fā)表于 07-13 16:13 ?2371次閱讀

    深度剖析時間復(fù)雜度

    相信每一位錄友都接觸過時間復(fù)雜度,但又對時間復(fù)雜度的認(rèn)識處于一種朦朧的狀態(tài),所以是時候?qū)?b class='flag-5'>時間復(fù)雜度
    的頭像 發(fā)表于 03-18 10:18 ?2143次閱讀

    如何求遞歸算法時間復(fù)雜度

    那么我通過一道簡單的面試題,模擬面試的場景,來帶大家逐步分析遞歸算法時間復(fù)雜度,最后找出最優(yōu)解,來看看同樣是遞歸,怎么就寫成了O(n)的代
    的頭像 發(fā)表于 07-13 11:30 ?2506次閱讀

    如何求遞歸算法時間復(fù)雜度

    相信很多同學(xué)對遞歸算法時間復(fù)雜度都很模糊,那么這篇Carl來給大家通透的講一講。
    的頭像 發(fā)表于 07-13 11:33 ?1836次閱讀

    算法之空間復(fù)雜度

    算法之空間復(fù)雜度:衡量一個算法運行需要開辟的額外空間
    的頭像 發(fā)表于 08-31 10:29 ?1864次閱讀

    常見機(jī)器學(xué)習(xí)算法的計算復(fù)雜度

    時間復(fù)雜度不是測量一個算法或一段代碼在某個機(jī)器或者條件下運行所花費的時間時間復(fù)雜度一般指
    發(fā)表于 10-02 12:45 ?944次閱讀

    算法時空復(fù)雜度分析實用指南2

    類似的,想想之前說的數(shù)據(jù)結(jié)構(gòu)擴(kuò)容的場景,也許`N`次操作中的某一次操作恰好觸發(fā)了擴(kuò)容,導(dǎo)致時間復(fù)雜度提高,但總的時間復(fù)雜度依然保持在`
    的頭像 發(fā)表于 04-12 14:38 ?699次閱讀
    <b class='flag-5'>算法</b>時空<b class='flag-5'>復(fù)雜度</b>分析實用指南<b class='flag-5'>2</b>

    算法時空復(fù)雜度分析實用指南(上)

    本文會篇幅較長,會涵蓋如下幾點: 1、Big O 表示法的幾個基本特點。 2、非遞歸算法中的時間復(fù)雜度分析。 3、數(shù)據(jù)結(jié)構(gòu)
    的頭像 發(fā)表于 04-19 10:34 ?1078次閱讀
    <b class='flag-5'>算法</b>時空<b class='flag-5'>復(fù)雜度</b>分析實用指南(上)

    算法時空復(fù)雜度分析實用指南(下)

    Big O 表示法的幾個基本特點。 2、非遞歸算法中的時間復(fù)雜度分析。 3、數(shù)據(jù)結(jié)構(gòu) API 的效率衡量方法(攤還分析)。
    的頭像 發(fā)表于 04-19 10:35 ?934次閱讀
    <b class='flag-5'>算法</b>時空<b class='flag-5'>復(fù)雜度</b>分析實用指南(下)

    常見排序算法分類

    本文將通過動態(tài)演示+代碼的形式系統(tǒng)地總結(jié)十大經(jīng)典排序算法排序算法 算法分類 —— 十種常見排序
    的頭像 發(fā)表于 06-22 14:49 ?1357次閱讀
    常見<b class='flag-5'>排序</b><b class='flag-5'>算法</b>分類

    如何計算時間復(fù)雜度

    來完成,那么該算法的用處就不會太大。同樣如果該算法需要若干個GB的內(nèi)存,那么在大部分機(jī)器上都無法使用。 一個算法的評價主要從時間復(fù)雜度和空間
    的頭像 發(fā)表于 10-13 11:19 ?3804次閱讀
    如何計算<b class='flag-5'>時間</b><b class='flag-5'>復(fù)雜度</b>

    時間復(fù)雜度O (nlogn)的排序算法簡述

    歸并排序遵循分治的思想:將原問題分解幾個規(guī)模較小但類似于原問題的子問題,遞歸地求解這些子問題,然后合并這些子問題的解來建立原問題的解。
    的頭像 發(fā)表于 12-05 09:57 ?884次閱讀
    <b class='flag-5'>時間</b><b class='flag-5'>復(fù)雜度</b><b class='flag-5'>為</b><b class='flag-5'>O</b> (nlogn)的<b class='flag-5'>排序</b><b class='flag-5'>算法</b>簡述
    主站蜘蛛池模板: 国产白丝精品爽爽久久久久久蜜臀 | 日韩精品卡1卡2三卡四卡乱码 | 男人扒开添女人下部口述 | 最新老头恋老OLDMAN | 免费韩国伦理2017最新 | 美女张开大腿 | 丰满的寡妇hd高清在线观看 | 免费果冻传媒在线完整观看 | 伦理片天堂eeuss影院 | 国产欧美另类久久久精品免费 | 69夫妇交友群 | 达达兔欧美午夜国产亚洲 | 国产精一品亚洲二区在线播放 | 在线观看亚洲专区5555 | 看了n遍舍不得删的黄文 | 国产黄a三级三级三级 | 色综合久久网女同蕾丝边 | 8050午夜二级一片 | 男人天堂2018亚洲男人天堂 | 国产在线一区二区AV视频 | 国产在线观看网址你懂得 | 中国xxx视频| 含羞草完整视频在线播放免费 | 这里只有精品在线视频 | 2023国产精品一卡2卡三卡4卡 | 一本色道久久88综合日韩精品 | 麻豆免费高清完整版 | G国产精品无马 | 午夜福利体验试看120秒 | 一本道中文无码亚洲 | 亚洲综合香蕉在线视频 | 9久久免费国产精品特黄 | 色综合久久88色综合天天提莫 | 亚洲成人在线免费观看 | 日本 稀土矿 | 夜色福利院在线观看免费 | 亚洲国产货青视觉盛宴 | 在线观看亚洲免费人成网址 | 精品亚洲一区二区在线播放 | 手机在线国产视频 | 99热久这里都是精品小草 |

    電子發(fā)燒友

    中國電子工程師最喜歡的網(wǎng)站

    • 2931785位工程師會員交流學(xué)習(xí)
    • 獲取您個性化的科技前沿技術(shù)信息
    • 參加活動獲取豐厚的禮品