-
當前位置:首頁 > 創(chuàng)意學院 > 技術(shù) > 專題列表 > 正文
1、排序算法概述
nlogn的排序(nlogn的排序口訣)
大家好!今天讓創(chuàng)意嶺的小編來大家介紹下關(guān)于nlogn的排序的問題,以下是小編對此問題的歸納整理,讓我們一起來看看吧。
開始之前先推薦一個非常厲害的Ai人工智能工具,一鍵生成原創(chuàng)文章、方案、文案、工作計劃、工作報告、論文、代碼、作文、做題和對話答疑等等
只需要輸入關(guān)鍵詞,就能返回你想要的內(nèi)容,越精準,寫出的就越詳細,有微信小程序端、在線網(wǎng)頁版、PC客戶端
官網(wǎng):https://ai.de1919.com。
創(chuàng)意嶺作為行業(yè)內(nèi)優(yōu)秀的企業(yè),服務客戶遍布全球各地,如需了解SEO相關(guān)業(yè)務請撥打電話175-8598-2043,或添加微信:1454722008
本文目錄:
一、排序算法概述
十大排序算法:冒泡排序,選擇排序,插入排序,歸并排序,堆排序,快速排序、希爾排序、計數(shù)排序,基數(shù)排序,桶排序
穩(wěn)定 :如果a原本在b前面,而a=b,排序之后a仍然在b的前面;
不穩(wěn)定 :如果a原本在b的前面,而a=b,排序之后a可能會出現(xiàn)在b的后面;
排序算法如果是穩(wěn)定的,那么從一個鍵上排序,然后再從另一個鍵上排序,前一個鍵排序的結(jié)果可以為后一個鍵排序所用。
算法的復雜度往往取決于數(shù)據(jù)的規(guī)模大小和數(shù)據(jù)本身分布性質(zhì)。
時間復雜度 : 一個算法執(zhí)行所耗費的時間。
空間復雜度 :對一個算法在運行過程中臨時占用存儲空間大小的量度。
常見復雜度由小到大 :O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n)
在各種不同算法中,若算法中語句執(zhí)行次數(shù)(占用空間)為一個常數(shù),則復雜度為O(1);
當一個算法的復雜度與以2為底的n的對數(shù)成正比時,可表示為O(log n);
當一個算法的復雜度與n成線性比例關(guān)系時,可表示為O (n),依次類推。
冒泡、選擇、插入排序需要兩個for循環(huán),每次只關(guān)注一個元素,平均時間復雜度為
(一遍找元素O(n),一遍找位置O(n))
快速、歸并、堆基于分治思想,log以2為底,平均時間復雜度往往和O(nlogn)(一遍找元素O(n),一遍找位置O(logn))相關(guān)
而希爾排序依賴于所取增量序列的性質(zhì),但是到目前為止還沒有一個最好的增量序列 。例如希爾增量序列時間復雜度為O(n²),而Hibbard增量序列的希爾排序的時間復雜度為 , 有人在大量的實驗后得出結(jié)論;當n在某個特定的范圍后希爾排序的最小時間復雜度大約為n^1.3。
從平均時間來看,快速排序是效率最高的:
快速排序中平均時間復雜度O(nlog n),這個公式中隱含的常數(shù)因子很小,比歸并排序的O(nlog n)中的要小很多,所以大多數(shù)情況下,快速排序總是優(yōu)于合并排序的。
而堆排序的平均時間復雜度也是O(nlog n),但是堆排序存在著重建堆的過程,它把根節(jié)點移除后,把最后的葉子結(jié)點拿上來后需要重建堆,但是,拿上的值是要比它的兩個葉子結(jié)點要差很多的,一般要比較很多次,才能回到合適的位置。堆排序就會有很多的時間耗在堆調(diào)整上。
雖然快速排序的最壞情況為排序規(guī)模(n)的平方關(guān)系,但是這種最壞情況取決于每次選擇的基準, 對于這種情況,已經(jīng)提出了很多優(yōu)化的方法,比如三取樣劃分和Dual-Pivot快排。
同時,當排序規(guī)模較小時,劃分的平衡性容易被打破,而且頻繁的方法調(diào)用超過了O(nlog n)為
省出的時間,所以一般排序規(guī)模較小時,會改用插入排序或者其他排序算法。
一種簡單的排序算法。它反復地走訪過要排序的數(shù)列,一次比較兩個元素,如果它們的順序錯誤就把它們交換過來。這個工作重復地進行直到?jīng)]有元素再需要交換,也就是說該數(shù)列已經(jīng)排序完成。這個算法的名字由來是因為元素會經(jīng)由交換慢慢“浮”到數(shù)列的頂端。
1.從數(shù)組頭開始,比較相鄰的元素。如果第一個比第二個大(小),就交換它們兩個;
2.對每一對相鄰元素作同樣的工作,從開始第一對到尾部的最后一對,這樣在最后的元素應該會是最大(小)的數(shù);
3.重復步驟1~2,重復次數(shù)等于數(shù)組的長度,直到排序完成。
首先,找到數(shù)組中最大(?。┑哪莻€元素;
其次,將它和數(shù)組的第一個元素交換位置(如果第一個元素就是最大(小)元素那么它就和自己交換);
再次,在剩下的元素中找到最大(小)的元素,將它與數(shù)組的第二個元素交換位置。如此往復,直到將整個數(shù)組排序。
這種方法叫做選擇排序,因為它在不斷地選擇剩余元素之中的最大(?。┱?。
對于未排序數(shù)據(jù),在已排序序列中從后向前掃描,找到相應位置并插入。
為了給要插入的元素騰出空間,我們需要將插入位置之后的已排序元素在都向后移動一位。
插入排序所需的時間取決于輸入中元素的初始順序。例如,對一個很大且其中的元素已經(jīng)有序(或接近有序)的數(shù)組進行排序?qū)葘﹄S機順序的數(shù)組或是逆序數(shù)組進行排序要快得多。
總的來說,插入排序?qū)τ诓糠钟行虻臄?shù)組十分高效,也很適合小規(guī)模數(shù)組。
一種基于插入排序的快速的排序算法。簡單插入排序?qū)τ诖笠?guī)模亂序數(shù)組很慢,因為元素只能一點一點地從數(shù)組的一端移動到另一端。例如,如果主鍵最小的元素正好在數(shù)組的盡頭,要將它挪到正確的位置就需要N-1 次移動。
希爾排序為了加快速度簡單地改進了插入排序,也稱為縮小增量排序,同時該算法是突破O(n^2)的第一批算法之一。
希爾排序是把待排序數(shù)組按一定數(shù)量的分組,對每組使用直接插入排序算法排序;然后縮小數(shù)量繼續(xù)分組排序,隨著數(shù)量逐漸減少,每組包含的元素越來越多,當數(shù)量減至 1 時,整個數(shù)組恰被分成一組,排序便完成了。這個不斷縮小的數(shù)量,就構(gòu)成了一個增量序列。
在先前較大的增量下每個子序列的規(guī)模都不大,用直接插入排序效率都較高,盡管在隨后的增量遞減分組中子序列越來越大,由于整個序列的有序性也越來越明顯,則排序效率依然較高。
從理論上說,只要一個數(shù)組是遞減的,并且最后一個值是1,都可以作為增量序列使用。有沒有一個步長序列,使得排序過程中所需的比較和移動次數(shù)相對較少,并且無論待排序列記錄數(shù)有多少,算法的時間復雜度都能漸近最佳呢?但是目前從數(shù)學上來說,無法證明某個序列是“最好的”。
常用的增量序列
希爾增量序列 :{N/2, (N / 2)/2, ..., 1},其中N為原始數(shù)組的長度,這是最常用的序列,但卻不是最好的
Hibbard序列:{2^k-1, ..., 3,1}
Sedgewick序列:{... , 109 , 41 , 19 , 5,1} 表達式為
歸并排序是建立在歸并操作上的一種有效的排序算法。該算法是采用分治法的一個非常典型的應用。
對于給定的一組數(shù)據(jù),利用遞歸與分治技術(shù)將數(shù)據(jù)序列劃分成為越來越小的半子表,在對半子表排序后,再用遞歸方法將排好序的半子表合并成為越來越大的有序序列。
為了提升性能,有時我們在半子表的個數(shù)小于某個數(shù)(比如15)的情況下,對半子表的排序采用其他排序算法,比如插入排序。
若將兩個有序表合并成一個有序表,稱為2-路歸并,與之對應的還有多路歸并。
快速排序(Quicksort)是對冒泡排序的一種改進,也是采用分治法的一個典型的應用。
首先任意選取一個數(shù)據(jù)(比如數(shù)組的第一個數(shù))作為關(guān)鍵數(shù)據(jù),我們稱為基準數(shù)(Pivot),然后將所有比它小的數(shù)都放到它前面,所有比它大的數(shù)都放到它后面,這個過程稱為一趟快速排序,也稱為分區(qū)(partition)操作。
通過一趟快速排序?qū)⒁判虻臄?shù)據(jù)分割成獨立的兩部分,其中一部分的所有數(shù)據(jù)都比另外一部分的所有數(shù)據(jù)都要小,然后再按此方法對這兩部分數(shù)據(jù)分別進行快速排序,整個排序過程可以遞歸進行,以此達到整個數(shù)組變成有序序列。
為了提升性能,有時我們在分割后獨立的兩部分的個數(shù)小于某個數(shù)(比如15)的情況下,會采用其他排序算法,比如插入排序。
基準的選?。鹤顑?yōu)的情況是基準值剛好取在無序區(qū)數(shù)值的中位數(shù),這樣能夠最大效率地讓兩邊排序,同時最大地減少遞歸劃分的次數(shù),但是一般很難做到最優(yōu)?;鶞实倪x取一般有三種方式,選取數(shù)組的第一個元素,選取數(shù)組的最后一個元素,以及選取第一個、最后一個以及中間的元素的中位數(shù)(如4 5 6 7, 第一個4, 最后一個7, 中間的為5, 這三個數(shù)的中位數(shù)為5, 所以選擇5作為基準)。
Dual-Pivot快排:雙基準快速排序算法,其實就是用兩個基準數(shù), 把整個數(shù)組分成三份來進行快速排序,在這種新的算法下面,比經(jīng)典快排從實驗來看節(jié)省了10%的時間。
許多應用程序都需要處理有序的元素,但不一定要求他們?nèi)坑行颍蛘卟灰欢ㄒ淮尉蛯⑺麄兣判?,很多時候,我們每次只需要操作數(shù)據(jù)中的最大元素(最小元素),那么有一種基于二叉堆的數(shù)據(jù)結(jié)構(gòu)可以提供支持。
所謂二叉堆,是一個完全二叉樹的結(jié)構(gòu),同時滿足堆的性質(zhì):即子結(jié)點的鍵值或索引總是小于(或者大于)它的父節(jié)點。在一個二叉堆中,根節(jié)點總是最大(或者最?。┕?jié)點。
堆排序算法就是抓住了這一特點,每次都取堆頂?shù)脑兀缓髮⑹S嗟脑刂匦抡{(diào)整為最大(最?。┒?,依次類推,最終得到排序的序列。
推論1:對于位置為K的結(jié)點 左子結(jié)點=2 k+1 右子結(jié)點=2 (k+1)
驗證:C:2 2 2+1=5 2 (2+1)=6
推論2:最后一個非葉節(jié)點的位置為 (N/2)-1,N為數(shù)組長度。
驗證:數(shù)組長度為6,(6/2)-1=2
計數(shù)排序?qū)σ欢ǚ秶鷥?nèi)的整數(shù)排序時候的速度非???,一般快于其他排序算法。但計數(shù)排序局限性比較大,只限于對整數(shù)進行排序,而且待排序元素值分布較連續(xù)、跨度小的情況。
計數(shù)排序是一個排序時不比較元素大小的排序算法。
如果一個數(shù)組里所有元素都是整數(shù),而且都在0-K以內(nèi)。對于數(shù)組里每個元素來說,如果能知道數(shù)組里有多少項小于或等于該元素,就能準確地給出該元素在排序后的數(shù)組的位置。
桶排序 (Bucket sort)的工作的原理:假設輸入數(shù)據(jù)服從均勻分布,利用某種函數(shù)的映射關(guān)系將數(shù)據(jù)分到有限數(shù)量的桶里,每個桶再分別排序(有可能再使用別的排序算法或是以遞歸方式繼續(xù)使用桶排序)。
桶排序利用函數(shù)的映射關(guān)系,減少了幾乎所有的比較工作。實際上,桶排序的f(k)值的計算,其作用就相當于快排中劃分,已經(jīng)把大量數(shù)據(jù)分割成了基本有序的數(shù)據(jù)塊(桶)。然后只需要對桶中的少量數(shù)據(jù)做排序即可。
常見的數(shù)據(jù)元素一般是由若干位組成的,比如字符串由若干字符組成,整數(shù)由若干位0~9數(shù)字組成?;鶖?shù)排序按照從右往左的順序,依次將每一位都當做一次關(guān)鍵字,然后按照該關(guān)鍵字對數(shù)組排序,同時每一輪排序都基于上輪排序后的結(jié)果;當我們將所有的位排序后,整個數(shù)組就達到有序狀態(tài)?;鶖?shù)排序不是基于比較的算法。
基數(shù)是什么意思?對于十進制整數(shù),每一位都只可能是0~9中的某一個,總共10種可能。那10就是它的基,同理二進制數(shù)字的基為2;對于字符串,如果它使用的是8位的擴展ASCII字符集,那么它的基就是256。
基數(shù)排序 vs 計數(shù)排序 vs 桶排序
基數(shù)排序有兩種方法:
MSD 從高位開始進行排序
LSD 從低位開始進行排序
這三種排序算法都利用了桶的概念,但對桶的使用方法上有明顯差異:
基數(shù)排序:根據(jù)鍵值的每位數(shù)字來分配桶
計數(shù)排序:每個桶只存儲單一鍵值
桶排序:每個桶存儲一定范圍的數(shù)值
有時,待排序的文件很大,計算機內(nèi)存不能容納整個文件,這時候?qū)ξ募筒荒苁褂脙?nèi)部排序了(我們一般的排序都是在內(nèi)存中做的,所以稱之為內(nèi)部排序,而外部排序是指待排序的內(nèi)容不能在內(nèi)存中一下子完成,它需要做內(nèi)外存的內(nèi)容交換),外部排序常采用的排序方法也是歸并排序,這種歸并方法由兩個不同的階段組成:
采用適當?shù)膬?nèi)部排序方法對輸入文件的每個片段進行排序,將排好序的片段(成為歸并段)寫到外部存儲器中(通常由一個可用的磁盤作為臨時緩沖區(qū)),這樣臨時緩沖區(qū)中的每個歸并段的內(nèi)容是有序的。
利用歸并算法,歸并第一階段生成的歸并段,直到只剩下一個歸并段為止。
例如要對外存中4500個記錄進行歸并,而內(nèi)存大小只能容納750個記錄,在第一階段,我們可以每次讀取750個記錄進行排序,這樣可以分六次讀取,進行排序,可以得到六個有序的歸并段
每個歸并段的大小是750個記錄,并將這些歸并段全部寫到臨時緩沖區(qū)(由一個可用的磁盤充當)內(nèi)了,這是第一步的排序結(jié)果。
完成第二步該怎么做呢?這時候歸并算法就有用處了。
二、快速排序算法在平均情況下的時間復雜度為 求詳解
時間復雜度為O(nlogn) n為元素個數(shù)
1. 快速排序的三個步驟:
1.1. 找到序列中用于劃分序列的元素
1.2. 用元素劃分序列
1.3. 對劃分后的兩個序列重復1,2兩個步驟指導序列無法再劃分
所以對于n個元素其排序時間為
T(n) = 2*T(n/2) + n (表示將長度為n的序列劃分為兩個子序列,每個子序列需要T(n/2)
的時間,而劃分序列需要n的時間)
而 T(1) = 1 (表示長度為1的序列無法劃分子序列,只需要1的時間即可)
T(n) = 2^logn + logn * n (n被不斷二分最終只能二分logn次(最優(yōu)的情況,每次選取
的元素都均分序列))
= n + nlogn
因此T(n) = O(nlogn)
以上是最優(yōu)情況的推導,因此快速排序在最優(yōu)情況下其排序時間為O(nlogn),通常平均情況
我們也認為是此值。
在最壞情況下其會退化為冒泡排序,T(n) = T(n - 1) + n (每次選取的元素只能將序列劃分為
一段,即自身是 最小元素或最大元素)
因此T(n) = n * (n-1) / 2 相當于O(n^2)
三、o(1), o(n), o(logn), o(nlogn)
由于平時接觸算法比較少,今天看資料看到了o(1),都不知道是什么意思,查資料之后才理解。
描述算法復雜度時,常用o(1), o(n), o(logn), o(nlogn)表示對應算法的時間復雜度,是算法的時空復雜度的表示。不僅僅用于表示時間復雜度,也用于表示空間復雜度。
O后面的括號中有一個函數(shù),指明某個算法的耗時/耗空間與數(shù)據(jù)增長量之間的關(guān)系。其中的n代表輸入數(shù)據(jù)的量。
比如時間復雜度為O(n),就代表數(shù)據(jù)量增大幾倍,耗時也增大幾倍。比如常見的遍歷算法。再比如時間復雜度O(n^2),就代表數(shù)據(jù)量增大n倍時,耗時增大n的平方倍,這是比線性更高的時間復雜度。比如冒泡排序,就是典型的O(n^2)的算法,對n個數(shù)排序,需要掃描n×n次。
再比如O(logn),當數(shù)據(jù)增大n倍時,耗時增大logn倍(這里的log是以2為底的,比如,當數(shù)據(jù)增大256倍時,耗時只增大8倍,是比線性還要低的時間復雜度)。二分查找就是O(logn)的算法,每找一次排除一半的可能,256個數(shù)據(jù)中查找只要找8次就可以找到目標。
O(nlogn)同理,就是n乘以logn,當數(shù)據(jù)增大256倍時,耗時增大256*8=2048倍。這個復雜度高于線性低于平方。歸并排序就是O(nlogn)的時間復雜度。
O(1)就是最低的時空復雜度了,也就是耗時/耗空間與輸入數(shù)據(jù)大小無關(guān),無論輸入數(shù)據(jù)增大多少倍,耗時/耗空間都不變。 哈希算法就是典型的O(1)時間復雜度,無論數(shù)據(jù)規(guī)模多大,都可以在一次計算后找到目標(不考慮沖突的話)
四、軟件設計師考試 | 第三章 數(shù)據(jù)結(jié)構(gòu) | 排序
假設含 n 個記錄的文件內(nèi)容為 {R1,R2,...,Rn} ,相應的關(guān)鍵字為 {k1,k2,...,kn} 。經(jīng)過排序確定一種排列 {Rj1,Rj2,...,Rjn} ,使得它們的關(guān)鍵字滿足以下遞增(或遞減)關(guān)系: kj1<=kj2<=...<=kjn(或kj1>=kj2>=...>=kjn) 。
排序方法的穩(wěn)定與不穩(wěn)定:
內(nèi)部排序和外部排序:
方法: 在插入第 i 個記錄時, R1,R2,...,Ri-1 已經(jīng)排好序,這時將 Ri 的關(guān)鍵字 ki 依次與關(guān)鍵字 ki-1,ki-2 等進行比較,從而找到應該插入的位置并將 Ri 插入,插入位置及其后的記錄依次向后移動。
直接插入排序 是一種 穩(wěn)定 的排序方法 , 時間復雜度為O(n^2),空間復雜度為O(1)。
方法: 首先將第一個記錄的關(guān)鍵字和第二個記錄的關(guān)鍵字進行比較,若為逆序,則交換這兩個記錄的值,然后比較第二個記錄和第三個記錄的關(guān)鍵字,依此類推,直到第 n-1 個記錄和第 n 個記錄的關(guān)鍵字比較過為止。上述過程稱為第一趟冒泡排序,然后再進行多次冒泡排序,直到冒泡排序過程中沒有進行相鄰位置的元素交換處理為止。
冒泡排序 是一種 穩(wěn)定 的排序方法 , 時間復雜度為O(n^2),空間復雜度為O(1)。
方法: 通過 n-i (1<=i<=n) 再次關(guān)鍵字之間的比較,從 n-i+1 個記錄中選出關(guān)鍵字最小的記錄,并和第 i 個記錄進行交換,當 i 等于 n 時所有記錄有序排列。
簡單選擇排序 是一種 不穩(wěn)定 的排序方法 , 時間復雜度為O(n^2),空間復雜度為O(1)。
又稱為“縮小增量排序”,它是對直接插入排序方法的改進。
方法: 先將整個待排序記錄分割成若干子序列,然后分別進行直接插入排序,待整個序列中的記錄基本有序時,再對全體記錄進行一次直接插入排序。具體做法是:先取一個小于 n 的整數(shù) d1 作為第一個增量,把文件的全部記錄分成 d1 個組,即將所有距離為 d1 倍數(shù)序號的記錄放在同一個組中,在各組內(nèi)進行直接插入排序;然后取第二個增量 d2 (d2<d1) ,重復上述分組和排序工作,依此類推,直到所取的增量 di=1 (di<di-1<...<dc<d1) ,即所有記錄放在同一組進行直接插入排序為止。
希爾排序 是一種 不穩(wěn)定 的排序方法 , 時間復雜度為O(n^1.3),空間復雜度為O(1)。
方法: 附設兩個位置指示變量 i 和 j ,它們的初值分別指向序列的第一個記錄和最后一個記錄。設樞軸記錄(通常是第一個記錄)的關(guān)鍵字為 pivot ,則首先從 j 所指位置起向前搜索,找到第一個關(guān)鍵字小于 pivot 的記錄時將記錄向前移到 i 指示的位置,然后從 i 所指位置起向后搜索,找到第一個關(guān)鍵字大于 pivot 的記錄時將該記錄后移到 j 所指位置,重復該過程直至 i 與 j 相等為止。
快速排序 是一種 不穩(wěn)定 的排序方法 , 時間復雜度為O(nlogn),空間復雜度為O(logn)。
方法: 對一組待排序記錄的關(guān)鍵字,首先按堆的定義排成一個序列(即建立初始堆),從而可以輸出堆頂?shù)淖畲箨P(guān)鍵字(對于大根堆而言),然后將剩余的關(guān)鍵字再調(diào)整成新堆,便得到次大的關(guān)鍵字,如此反復,直到全部關(guān)鍵字排成有序序列為止。
堆排序 是一種 不穩(wěn)定 的排序方法 , 時間復雜度為O(nlogn),空間復雜度為O(1)。
方法: 將兩個或兩個以上的有序文件合并成一個新的有序文件。實現(xiàn)方法是:把一個有 n 個記錄的無序文件看成是由 n 個長度為 1 的有序子文件組成的文件,然后進行兩兩歸并,得到 n/2 個長度為 2 或 1 的有序文件,再兩兩歸并,如此重復,直到最后形成包含 n 個記錄的有序文件為止。
歸并排序 是一種 穩(wěn)定 的排序方法 , 時間復雜度為O(nlogn),空間復雜度為O(n)。
方法: 設立 r 個隊列,隊列的編號分別為 0、1、2、...、r-1 。首先按最低有效位的值把 n 個關(guān)鍵字分配到這 r 個隊列中;然后按照隊列編號從小到大將各隊列中的關(guān)鍵字依次收集起來;接著再按次低有效位的值把剛收集起來的關(guān)鍵字分配到 r 個隊列中。重復上述分配和收集過程,直到按照最高有效位分配和收集。這樣就得到一個從小到大有序的關(guān)鍵字序列。
對于 n 個記錄,執(zhí)行一次分配和收集的時間為 O(n+r) 。如果關(guān)鍵字有 d 位,則要執(zhí)行 d 便。所以總的運算時間為 O(d(n+r)) 。
基數(shù)排序 是一種 穩(wěn)定 的排序方法 , 時間復雜度為O(d(n+rd)),空間復雜度為O(rd)。
各個排序方法的性能比較:
外部排序是對大型文件的排序,待排序的記錄存放在外存。
常用的外部排序方法是歸并排序。
以上就是關(guān)于nlogn的排序相關(guān)問題的回答。希望能幫到你,如有更多相關(guān)問題,您也可以聯(lián)系我們的客服進行咨詢,客服也會為您講解更多精彩的知識和內(nèi)容。
推薦閱讀:
fifaonline3隊套排行榜(fifaonline3最強隊套)
win7刪除winload如何恢復(win7系統(tǒng)刪除的文件怎么找回)