各種排序算法的比較（各種排序算法的比較和特點(diǎn)）

大家好！今天讓創(chuàng)意嶺的小編來大家介紹下關(guān)于各種排序算法的比較的問題，以下是小編對此問題的歸納整理，讓我們一起來看看吧。

開始之前先推薦一個(gè)非常厲害的Ai人工智能工具，一鍵生成原創(chuàng)文章、方案、文案、工作計(jì)劃、工作報(bào)告、論文、代碼、作文、做題和對話答疑等等

只需要輸入關(guān)鍵詞，就能返回你想要的內(nèi)容，越精準(zhǔn)，寫出的就越詳細(xì)，有微信小程序端、在線網(wǎng)頁版、PC客戶端

官網(wǎng)：https://ai.de1919.com。

創(chuàng)意嶺作為行業(yè)內(nèi)優(yōu)秀的企業(yè)，服務(wù)客戶遍布全球各地，如需了解SEO相關(guān)業(yè)務(wù)請撥打電話175-8598-2043，或添加微信：1454722008

本文目錄:

• 1、哪些排序法是基于比較排序法？

• 2、常用的數(shù)據(jù)排序算法有哪些,各有什么特點(diǎn)?舉例結(jié)合一種排序算法并應(yīng)用數(shù)組進(jìn)行數(shù)據(jù)排序。

• 3、用代碼實(shí)現(xiàn)幾種排序算法的時(shí)間復(fù)雜度比較

• 4、數(shù)據(jù)結(jié)構(gòu)中各種排序的時(shí)間復(fù)雜度與空間復(fù)雜度比較！

一、哪些排序法是基于比較排序法？

幾種常見的基于比較的排序算法：

1. 選擇排序

2. 冒泡排序

3. 插入排序

4. 希爾排序

5. 歸并排序

6. 快速排序

7. 堆排序

8. 二叉排序樹排序

二、常用的數(shù)據(jù)排序算法有哪些,各有什么特點(diǎn)?舉例結(jié)合一種排序算法并應(yīng)用數(shù)組進(jìn)行數(shù)據(jù)排序。

排序簡介

排序是數(shù)據(jù)處理中經(jīng)常使用的一種重要運(yùn)算,在計(jì)算機(jī)及其應(yīng)用系統(tǒng)中,花費(fèi)在排序上的時(shí)間在系統(tǒng)運(yùn)行時(shí)間中占有很大比重;并且排序本身對推動算法分析的發(fā)展也起很大作用。目前已有上百種排序方法，但尚未有一個(gè)最理想的盡如人意的方法，本章介紹常用的如下排序方法，并對它們進(jìn)行分析和比較。

1、插入排序（直接插入排序、折半插入排序、希爾排序）；

2、交換排序（起泡排序、快速排序）；

3、選擇排序（直接選擇排序、堆排序）；

4、歸并排序；

5、基數(shù)排序；

學(xué)習(xí)重點(diǎn)

1、掌握排序的基本概念和各種排序方法的特點(diǎn)，并能加以靈活應(yīng)用；

2、掌握插入排序(直接插入排序、折半插入排序、希爾排序)、交換排序（起泡排序、快速排序）、選擇排序（直接選擇排序、堆排序）、二路歸并排序的方法及其性能分析方法；

3、了解基數(shù)排序方法及其性能分析方法。

排序（sort）或分類

　所謂排序，就是要整理文件中的記錄，使之按關(guān)鍵字遞增(或遞減)次序排列起來。其確切定義如下：

輸入：n個(gè)記錄R1，R2，…，Rn，其相應(yīng)的關(guān)鍵字分別為K1，K2，…，Kn。

輸出：Ril，Ri2，…，Rin，使得Ki1≤Ki2≤…≤Kin。(或Ki1≥Ki2≥…≥Kin)。

1．被排序?qū)ο?-文件

被排序的對象--文件由一組記錄組成。

記錄則由若干個(gè)數(shù)據(jù)項(xiàng)(或域)組成。其中有一項(xiàng)可用來標(biāo)識一個(gè)記錄，稱為關(guān)鍵字項(xiàng)。該數(shù)據(jù)項(xiàng)的值稱為關(guān)鍵字(Key)。

注意：

　 在不易產(chǎn)生混淆時(shí)，將關(guān)鍵字項(xiàng)簡稱為關(guān)鍵字。

2．排序運(yùn)算的依據(jù)--關(guān)鍵字

　用來作排序運(yùn)算依據(jù)的關(guān)鍵字，可以是數(shù)字類型，也可以是字符類型。

　 關(guān)鍵字的選取應(yīng)根據(jù)問題的要求而定。

【例】在高考成績統(tǒng)計(jì)中將每個(gè)考生作為一個(gè)記錄。每條記錄包含準(zhǔn)考證號、姓名、各科的分?jǐn)?shù)和總分?jǐn)?shù)等項(xiàng)內(nèi)容。若要惟一地標(biāo)識一個(gè)考生的記錄，則必須用"準(zhǔn)考證號"作為關(guān)鍵字。若要按照考生的總分?jǐn)?shù)排名次，則需用"總分?jǐn)?shù)"作為關(guān)鍵字。

排序的穩(wěn)定性

　 當(dāng)待排序記錄的關(guān)鍵字均不相同時(shí)，排序結(jié)果是惟一的，否則排序結(jié)果不唯一。

　在待排序的文件中，若存在多個(gè)關(guān)鍵字相同的記錄，經(jīng)過排序后這些具有相同關(guān)鍵字的記錄之間的相對次序保持不變，該排序方法是穩(wěn)定的；若具有相同關(guān)鍵字的記錄之間的相對次序發(fā)生變化，則稱這種排序方法是不穩(wěn)定的。

注意：

　 排序算法的穩(wěn)定性是針對所有輸入實(shí)例而言的。即在所有可能的輸入實(shí)例中，只要有一個(gè)實(shí)例使得算法不滿足穩(wěn)定性要求，則該排序算法就是不穩(wěn)定的。

排序方法的分類

1．按是否涉及數(shù)據(jù)的內(nèi)、外存交換分

　在排序過程中，若整個(gè)文件都是放在內(nèi)存中處理，排序時(shí)不涉及數(shù)據(jù)的內(nèi)、外存交換，則稱之為內(nèi)部排序(簡稱內(nèi)排序)；反之，若排序過程中要進(jìn)行數(shù)據(jù)的內(nèi)、外存交換，則稱之為外部排序。

注意：

　 ① 內(nèi)排序適用于記錄個(gè)數(shù)不很多的小文件

?、?外排序則適用于記錄個(gè)數(shù)太多，不能一次將其全部記錄放人內(nèi)存的大文件。

2．按策略劃分內(nèi)部排序方法

　可以分為五類：插入排序、選擇排序、交換排序、歸并排序和分配排序。

排序算法分析

1．排序算法的基本操作

　大多數(shù)排序算法都有兩個(gè)基本的操作：

(1) 比較兩個(gè)關(guān)鍵字的大??；

(2) 改變指向記錄的指針或移動記錄本身。

注意：

　 第(2)種基本操作的實(shí)現(xiàn)依賴于待排序記錄的存儲方式。

2．待排文件的常用存儲方式

（1） 以順序表(或直接用向量)作為存儲結(jié)構(gòu)

排序過程：對記錄本身進(jìn)行物理重排（即通過關(guān)鍵字之間的比較判定，將記錄移到合適的位置）

（2） 以鏈表作為存儲結(jié)構(gòu)

排序過程：無須移動記錄，僅需修改指針。通常將這類排序稱為鏈表(或鏈?zhǔn)?排序；

（3） 用順序的方式存儲待排序的記錄，但同時(shí)建立一個(gè)輔助表(如包括關(guān)鍵字和指向記錄位置的指針組成的索引表)

排序過程：只需對輔助表的表目進(jìn)行物理重排（即只移動輔助表的表目，而不移動記錄本身）。適用于難于在鏈表上實(shí)現(xiàn)，仍需避免排序過程中移動記錄的排序方法。

3．排序算法性能評價(jià)

（1） 評價(jià)排序算法好壞的標(biāo)準(zhǔn)

評價(jià)排序算法好壞的標(biāo)準(zhǔn)主要有兩條：

?、?執(zhí)行時(shí)間和所需的輔助空間

　② 算法本身的復(fù)雜程度

（2） 排序算法的空間復(fù)雜度

若排序算法所需的輔助空間并不依賴于問題的規(guī)模n，即輔助空間是O(1)，則稱之為就地排序(In-PlaceSou)。

非就地排序一般要求的輔助空間為O(n)。

（3） 排序算法的時(shí)間開銷

大多數(shù)排序算法的時(shí)間開銷主要是關(guān)鍵字之間的比較和記錄的移動。有的排序算法其執(zhí)行時(shí)間不僅依賴于問題的規(guī)模，還取決于輸入實(shí)例中數(shù)據(jù)的狀態(tài)。

文件的順序存儲結(jié)構(gòu)表示

#define n l00 //假設(shè)的文件長度，即待排序的記錄數(shù)目

typedef int KeyType； //假設(shè)的關(guān)鍵字類型

typedef struct{ //記錄類型

KeyType key； //關(guān)鍵字項(xiàng)

InfoType otherinfo；//其它數(shù)據(jù)項(xiàng)，類型InfoType依賴于具體應(yīng)用而定義

}RecType；

typedef RecType SeqList[n+1]；//SeqList為順序表類型，表中第0個(gè)單元一般用作哨兵

注意：

　若關(guān)鍵字類型沒有比較算符，則可事先定義宏或函數(shù)來表示比較運(yùn)算。

【例】關(guān)鍵字為字符串時(shí)，可定義宏"#define LT(a，b)(Stromp((a)，(b))<0)"。那么算法中"a<b"可用"LT(a，b)"取代。若使用C++，則定義重載的算符"<"更為方便。

按平均時(shí)間將排序分為四類：

（1）平方階(O(n2))排序

　一般稱為簡單排序，例如直接插入、直接選擇和冒泡排序；

（2）線性對數(shù)階(O(nlgn))排序

　如快速、堆和歸并排序；

（3）O(n1+￡)階排序

　￡是介于0和1之間的常數(shù)，即0<￡<1，如希爾排序；

（4）線性階(O(n))排序

　如桶、箱和基數(shù)排序。

各種排序方法比較

簡單排序中直接插入最好，快速排序最快，當(dāng)文件為正序時(shí)，直接插入和冒泡均最佳。

影響排序效果的因素

　因?yàn)椴煌呐判蚍椒ㄟm應(yīng)不同的應(yīng)用環(huán)境和要求，所以選擇合適的排序方法應(yīng)綜合考慮下列因素：

①待排序的記錄數(shù)目n；

②記錄的大小(規(guī)模)；

③關(guān)鍵字的結(jié)構(gòu)及其初始狀態(tài)；

④對穩(wěn)定性的要求；

⑤語言工具的條件；

⑥存儲結(jié)構(gòu)；

⑦時(shí)間和輔助空間復(fù)雜度等。

不同條件下，排序方法的選擇

(1)若n較小(如n≤50)，可采用直接插入或直接選擇排序。

　當(dāng)記錄規(guī)模較小時(shí)，直接插入排序較好；否則因?yàn)橹苯舆x擇移動的記錄數(shù)少于直接插人，應(yīng)選直接選擇排序?yàn)橐恕?/p>

(2)若文件初始狀態(tài)基本有序(指正序)，則應(yīng)選用直接插人、冒泡或隨機(jī)的快速排序?yàn)橐耍?/p>

(3)若n較大，則應(yīng)采用時(shí)間復(fù)雜度為O(nlgn)的排序方法：快速排序、堆排序或歸并排序。

　快速排序是目前基于比較的內(nèi)部排序中被認(rèn)為是最好的方法，當(dāng)待排序的關(guān)鍵字是隨機(jī)分布時(shí)，快速排序的平均時(shí)間最短；

　堆排序所需的輔助空間少于快速排序，并且不會出現(xiàn)快速排序可能出現(xiàn)的最壞情況。這兩種排序都是不穩(wěn)定的。

　若要求排序穩(wěn)定，則可選用歸并排序。但本章介紹的從單個(gè)記錄起進(jìn)行兩兩歸并的 排序算法并不值得提倡，通?？梢詫⑺椭苯硬迦肱判蚪Y(jié)合在一起使用。先利用直接插入排序求得較長的有序子文件，然后再兩兩歸并之。因?yàn)橹苯硬迦肱判蚴欠€(wěn)定的，所以改進(jìn)后的歸并排序仍是穩(wěn)定的。

4)在基于比較的排序方法中，每次比較兩個(gè)關(guān)鍵字的大小之后，僅僅出現(xiàn)兩種可能的轉(zhuǎn)移，因此可以用一棵二叉樹來描述比較判定過程。

　當(dāng)文件的n個(gè)關(guān)鍵字隨機(jī)分布時(shí)，任何借助于"比較"的排序算法，至少需要O(nlgn)的時(shí)間。

　箱排序和基數(shù)排序只需一步就會引起m種可能的轉(zhuǎn)移，即把一個(gè)記錄裝入m個(gè)箱子之一，因此在一般情況下，箱排序和基數(shù)排序可能在O(n)時(shí)間內(nèi)完成對n個(gè)記錄的排序。但是，箱排序和基數(shù)排序只適用于像字符串和整數(shù)這類有明顯結(jié)構(gòu)特征的關(guān)鍵字，而當(dāng)關(guān)鍵字的取值范圍屬于某個(gè)無窮集合(例如實(shí)數(shù)型關(guān)鍵字)時(shí)，無法使用箱排序和基數(shù)排序，這時(shí)只有借助于"比較"的方法來排序。

　若n很大，記錄的關(guān)鍵字位數(shù)較少且可以分解時(shí)，采用基數(shù)排序較好。雖然桶排序?qū)﹃P(guān)鍵字的結(jié)構(gòu)無要求，但它也只有在關(guān)鍵字是隨機(jī)分布時(shí)才能使平均時(shí)間達(dá)到線性階，否則為平方階。同時(shí)要注意，箱、桶、基數(shù)這三種分配排序均假定了關(guān)鍵字若為數(shù)字時(shí)，則其值均是非負(fù)的，否則將其映射到箱(桶)號時(shí)，又要增加相應(yīng)的時(shí)間。

(5)有的語言(如Fortran，Cobol或Basic等)沒有提供指針及遞歸，導(dǎo)致實(shí)現(xiàn)歸并、快速(它們用遞歸實(shí)現(xiàn)較簡單)和基數(shù)(使用了指針)等排序算法變得復(fù)雜。此時(shí)可考慮用其它排序。

(6)本章給出的排序算法，輸人數(shù)據(jù)均是存儲在一個(gè)向量中。當(dāng)記錄的規(guī)模較大時(shí)，為避免耗費(fèi)大量的時(shí)間去移動記錄，可以用鏈表作為存儲結(jié)構(gòu)。譬如插入排序、歸并排序、基數(shù)排序都易于在鏈表上實(shí)現(xiàn)，使之減少記錄的移動次數(shù)。但有的排序方法，如快速排序和堆排序，在鏈表上卻難于實(shí)現(xiàn)，在這種情況下，可以提取關(guān)鍵字建立索引表，然后對索引表進(jìn)行排序。然而更為簡單的方法是：引人一個(gè)整型向量t作為輔助表，排序前令t[i]=i(0≤i<n)，若排序算法中要求交換R[i]和R[j]，則只需交換t[i]和t[j]即可；排序結(jié)束后，向量t就指示了記錄之間的順序關(guān)系：

R[t[0]].key≤R[t[1]].key≤…≤R[t[n-1]].key

若要求最終結(jié)果是：

R[0].key≤R[1].key≤…≤R[n-1].key

則可以在排序結(jié)束后，再按輔助表所規(guī)定的次序重排各記錄，完成這種重排的時(shí)間是O(n)。

三、用代碼實(shí)現(xiàn)幾種排序算法的時(shí)間復(fù)雜度比較

一、簡單排序算法

由于程序比較簡單，所以沒有加什么注釋。所有的程序都給出了完整的運(yùn)行代碼，并在我的VC環(huán)境

下運(yùn)行通過。因?yàn)闆]有涉及MFC和WINDOWS的內(nèi)容，所以在BORLAND C++的平臺上應(yīng)該也不會有什么

問題的。在代碼的后面給出了運(yùn)行過程示意，希望對理解有幫助。

1.冒泡法：

這是最原始，也是眾所周知的最慢的算法了。他的名字的由來因?yàn)樗墓ぷ骺磥硐笫敲芭荩?/p>

#include <iostream>

using namespace std;

void BubbleSort(int * pData, int Count)

{

int iTemp;

for (int i=0; i<Count; i++)

{

for (int j=Count-1; j>i; j--)

{

if (pData[j]<pData[j-1])

{

iTemp = pData[j-1];

pData[j-1] = pData[j];

pData[j] = iTemp;

}

}

}

}

void main()

{

int data[7] = {10,9,8,7,6,5,4};

BubbleSort(data,7);

for (int i=0; i<7; i++)

{

cout<<data[i]<<" ";

}

cout<<endl;

system("PAUSE");

}

倒序(最糟情況)

第一輪：10，9，8，7->10，9，7，8->10，7，9，8->7，10，9，8(交換3次)

第二輪：7，10，9，8->7，10，8，9->7，8，10，9(交換2次)

第一輪：7，8，10，9->7，8，9，10(交換1次)

循環(huán)次數(shù)：6次

交換次數(shù)：6次

其他：

第一輪：8，10，7，9->8，10，7，9->8，7，10，9->7，8，10，9(交換2次)

第二輪：7，8，10，9->7，8，10，9->7，8，10，9(交換0次)

第一輪：7，8，10，9->7，8，9，10(交換1次)

循環(huán)次數(shù)：6次

交換次數(shù)：3次

上面我們給出了程序段，現(xiàn)在我們分析它：這里，影響我們算法性能的主要部分是循環(huán)和交換，

顯然，次數(shù)越多，性能就越差。從上面的程序我們可以看出循環(huán)的次數(shù)是固定的，為1+2+...+n-1。

寫成公式就是1/2*(n-1)*n。

現(xiàn)在注意，我們給出O方法的定義：

若存在一常量K和起點(diǎn)n0，使當(dāng)n>=n0時(shí)，有f(n)<=K*g(n)，則f(n) = O(g(n))。（呵呵，不要說沒學(xué)好數(shù)學(xué)呀，對于編程數(shù)學(xué)是非常重要的！?。。?/p>

現(xiàn)在我們來看1/2*(n-1)*n，當(dāng)K=1/2，n0=1，g(n)=n*n時(shí)，1/2*(n-1)*n<=1/2*n*n=K*g(n)。所以f(n)

=O(g(n))=O(n*n)。所以我們程序循環(huán)的復(fù)雜度為O(n*n)。

再看交換。從程序后面所跟的表可以看到，兩種情況的循環(huán)相同，交換不同。其實(shí)交換本身同數(shù)據(jù)源的

有序程度有極大的關(guān)系，當(dāng)數(shù)據(jù)處于倒序的情況時(shí)，交換次數(shù)同循環(huán)一樣（每次循環(huán)判斷都會交換），

復(fù)雜度為O(n*n)。當(dāng)數(shù)據(jù)為正序，將不會有交換。復(fù)雜度為O(0)。亂序時(shí)處于中間狀態(tài)。正是由于這樣的

原因，我們通常都是通過循環(huán)次數(shù)來對比算法。

2.交換法：

交換法的程序最清晰簡單，每次用當(dāng)前的元素一一的同其后的元素比較并交換。

#include <iostream.h>

void ExchangeSort(int* pData，int Count)

{

int iTemp;

for(int i=0;i<Count-1;i++)

{ //共（count-1)輪，每輪得到一個(gè)最小值

for(int j=i+1;j<Count;j++)

{ //每次從剩下的數(shù)字中尋找最小值，于當(dāng)前最小值相比，如果小則交換

if(pData[j]9，10，8，7->8，10，9，7->7，10，9，8(交換3次)

第二輪：7，10，9，8->7，9，10，8->7，8，10，9(交換2次)

第一輪：7，8，10，9->7，8，9，10(交換1次)

循環(huán)次數(shù)：6次

交換次數(shù)：6次

其他：

第一輪：8，10，7，9->8，10，7，9->7，10，8，9->7，10，8，9(交換1次)

第二輪：7，10，8，9->7，8，10，9->7，8，10，9(交換1次)

第一輪：7，8，10，9->7，8，9，10(交換1次)

循環(huán)次數(shù)：6次

交換次數(shù)：3次

從運(yùn)行的表格來看，交換幾乎和冒泡一樣糟。事實(shí)確實(shí)如此。循環(huán)次數(shù)和冒泡一樣

也是1/2*(n-1)*n，所以算法的復(fù)雜度仍然是O(n*n)。由于我們無法給出所有的情況，所以

只能直接告訴大家他們在交換上面也是一樣的糟糕（在某些情況下稍好，在某些情況下稍差）。

3.選擇法：

現(xiàn)在我們終于可以看到一點(diǎn)希望：選擇法，這種方法提高了一點(diǎn)性能（某些情況下）

這種方法類似我們?nèi)藶榈呐判蛄?xí)慣：從數(shù)據(jù)中選擇最小的同第一個(gè)值交換，在從省下的部分中

選擇最小的與第二個(gè)交換，這樣往復(fù)下去。

#include <iostream.h>

void SelectSort(int* pData，int Count)

{

int iTemp;

int iPos;

for(int i=0;i<Count-1;i++)

{

iTemp = pData;

iPos = i;

for(int j=i+1;j<Count;j++)

{

if(pData[j]<iTemp)

{

iTemp = pData[j];

iPos = j;

}

}

pData[iPos] = pData;

pData = iTemp;

}

}

void main()

{

int data[] = {10，9，8，7，6，5，4};

SelectSort(data，7);

for (int i=0;i<7;i++)

cout<<data<<" ";

cout<<"\n";

}

倒序(最糟情況)

第一輪：10，9，8，7->(iTemp=9)10，9，8，7->(iTemp=8)10，9，8，7->(iTemp=7)7，9，8，10(交換1次)

第二輪：7，9，8，10->7，9，8，10(iTemp=8)->(iTemp=8)7，8，9，10(交換1次)

第一輪：7，8，9，10->(iTemp=9)7，8，9，10(交換0次)

循環(huán)次數(shù)：6次

交換次數(shù)：2次

其他：

第一輪：8，10，7，9->(iTemp=8)8，10，7，9->(iTemp=7)8，10，7，9->(iTemp=7)7，10，8，9(交換1次)

第二輪：7，10，8，9->(iTemp=8)7，10，8，9->(iTemp=8)7，8，10，9(交換1次)

第一輪：7，8，10，9->(iTemp=9)7，8，9，10(交換1次)

循環(huán)次數(shù)：6次

交換次數(shù)：3次

遺憾的是算法需要的循環(huán)次數(shù)依然是1/2*(n-1)*n。所以算法復(fù)雜度為O(n*n)。

我們來看他的交換。由于每次外層循環(huán)只產(chǎn)生一次交換（只有一個(gè)最小值）。所以f(n)<=n

所以我們有f(n)=O(n)。所以，在數(shù)據(jù)較亂的時(shí)候，可以減少一定的交換次數(shù)。

4.插入法：

插入法較為復(fù)雜，它的基本工作原理是抽出牌，在前面的牌中尋找相應(yīng)的位置插入，然后繼續(xù)下一張

#include <iostream.h>

void InsertSort(int* pData，int Count)

{

int iTemp;

int iPos;

for(int i=1;i<Count;i++)

{

iTemp = pData[i]; //保存要插入的數(shù)

iPos = i-1; //被插入的數(shù)組數(shù)字個(gè)數(shù)

while((iPos>=0) && (iTemp9，10，8，7(交換1次)(循環(huán)1次)

第二輪：9，10，8，7->8，9，10，7(交換1次)(循環(huán)2次)

第一輪：8，9，10，7->7，8，9，10(交換1次)(循環(huán)3次)

循環(huán)次數(shù)：6次

交換次數(shù)：3次

其他：

第一輪：8，10，7，9->8，10，7，9(交換0次)(循環(huán)1次)

第二輪：8，10，7，9->7，8，10，9(交換1次)(循環(huán)2次)

第一輪：7，8，10，9->7，8，9，10(交換1次)(循環(huán)1次)

循環(huán)次數(shù)：4次

交換次數(shù)：2次

上面結(jié)尾的行為分析事實(shí)上造成了一種假象，讓我們認(rèn)為這種算法是簡單算法中最好的，其實(shí)不是，

因?yàn)槠溲h(huán)次數(shù)雖然并不固定，我們?nèi)钥梢允褂肙方法。從上面的結(jié)果可以看出，循環(huán)的次數(shù)f(n)<=

1/2*n*(n-1)<=1/2*n*n。所以其復(fù)雜度仍為O(n*n)（這里說明一下，其實(shí)如果不是為了展示這些簡單

排序的不同，交換次數(shù)仍然可以這樣推導(dǎo)）?，F(xiàn)在看交換，從外觀上看，交換次數(shù)是O(n)（推導(dǎo)類似

選擇法），但我們每次要進(jìn)行與內(nèi)層循環(huán)相同次數(shù)的‘=’操作。正常的一次交換我們需要三次‘=’

而這里顯然多了一些，所以我們浪費(fèi)了時(shí)間。

最終，我個(gè)人認(rèn)為，在簡單排序算法中，選擇法是最好的。

二、高級排序算法

高級排序算法中我們將只介紹這一種，同時(shí)也是目前我所知道（我看過的資料中）的最快的。

它的工作看起來仍然象一個(gè)二叉樹。首先我們選擇一個(gè)中間值middle程序中我們使用數(shù)組中間值，然后

把比它小的放在左邊，大的放在右邊（具體的實(shí)現(xiàn)是從兩邊找，找到一對后交換）。然后對兩邊分別使

用這個(gè)過程（最容易的方法——遞歸）。

1.快速排序：

#include <iostream.h>

void run(int* pData，int left，int right)

{

int i，j;

int middle，iTemp;

i = left;

j = right;

middle = pData[left];

do{

while((pData[i]<middle) && (i<right))//從左掃描大于中值的數(shù)

i++;　

while((pData[j]>middle) && (j>left))//從右掃描大于中值的數(shù)

j--;

if(i<=j)//找到了一對值

{

//交換

iTemp = pData[i];

pData[i] = pData[j];

pData[j] = iTemp;

i++;

j--;

}

}while(i<=j);//如果兩邊掃描的下標(biāo)交錯，就停止（完成一次）

//當(dāng)左邊部分有值(left<j)，遞歸左半邊

if(left<j)

run(pData，left，j);

//當(dāng)右邊部分有值(right>i)，遞歸右半邊

if(right>i)

run(pData，i，right);

}

void QuickSort(int* pData，int Count)

{

run(pData，0，Count-1);

}

void main()

{

int data[] = {10，9，8，7，6，5，4};

QuickSort(data，7);

for (int i=0;i<7;i++)

cout<<data<<" ";

cout<<"\n";

}

這里我沒有給出行為的分析，因?yàn)檫@個(gè)很簡單，我們直接來分析算法：首先我們考慮最理想的情況

1.數(shù)組的大小是2的冪，這樣分下去始終可以被2整除。假設(shè)為2的k次方，即k=log2(n)。

2.每次我們選擇的值剛好是中間值，這樣，數(shù)組才可以被等分。

第一層遞歸，循環(huán)n次，第二層循環(huán)2*(n/2)......

所以共有n+2(n/2)+4(n/4)+...+n*(n/n) = n+n+n+...+n=k*n=log2(n)*n

所以算法復(fù)雜度為O(log2(n)*n)

其他的情況只會比這種情況差，最差的情況是每次選擇到的middle都是最小值或最大值，那么他將變

成交換法（由于使用了遞歸，情況更糟）。但是你認(rèn)為這種情況發(fā)生的幾率有多大？？呵呵，你完全

不必?fù)?dān)心這個(gè)問題。實(shí)踐證明，大多數(shù)的情況，快速排序總是最好的。

如果你擔(dān)心這個(gè)問題，你可以使用堆排序，這是一種穩(wěn)定的O(log2(n)*n)算法，但是通常情況下速度要慢

四、數(shù)據(jù)結(jié)構(gòu)中各種排序的時(shí)間復(fù)雜度與空間復(fù)雜度比較！

冒泡排序是穩(wěn)定的，算法時(shí)間復(fù)雜度是O(n ^2)。 2.2 選擇排序（Selection Sort） 選擇排序的基本思想是對待排序的記錄序列進(jìn)行n-1遍的處理，第i遍處理是將L[i..n]中最小者與L[i]交換位置。這樣，經(jīng)過i遍處理之后，前i個(gè)記錄的位置已經(jīng)是正確的了。 選擇排序是不穩(wěn)定的，算法復(fù)雜度是O(n ^2 )。 2.3 插入排序 （Insertion Sort） 插入排序的基本思想是，經(jīng)過i-1遍處理后,L[1..i-1]己排好序。第i遍處理僅將L[i]插入L[1..i-1]的適當(dāng)位置，使得L[1..i] 又是排好序的序列。要達(dá)到這個(gè)目的，我們可以用順序比較的方法。首先比較L[i]和L[i-1]，如果L[i-1]≤ L[i]，則L[1..i]已排好序，第i遍處理就結(jié)束了；否則交換L[i]與L[i-1]的位置，繼續(xù)比較L[i-1]和L[i-2]，直到找到某一個(gè)位置j(1≤j≤i-1)，使得L[j] ≤L[j+1]時(shí)為止。圖1演示了對4個(gè)元素進(jìn)行插入排序的過程，共需要(a),(b),(c)三次插入。 直接插入排序是穩(wěn)定的，算法時(shí)間復(fù)雜度是O(n ^2) 。 2.4 堆排序 堆排序是一種樹形選擇排序，在排序過程中，將A[n]看成是完全二叉樹的順序存儲結(jié)構(gòu)，利用完全二叉樹中雙親結(jié)點(diǎn)和孩子結(jié)點(diǎn)之間的內(nèi)在關(guān)系來選擇最小的元素。 堆排序是不穩(wěn)定的，算法時(shí)間復(fù)雜度O(nlog n)。 2.5 歸并排序 設(shè)有兩個(gè)有序（升序）序列存儲在同一數(shù)組中相鄰的位置上，不妨設(shè)為A[l..m]，A[m+1..h]，將它們歸并為一個(gè)有序數(shù)列，并存儲在A[l..h]。 其時(shí)間復(fù)雜度無論是在最好情況下還是在最壞情況下均是O(nlog2n)。 2.6 快速排序 快速排序是對冒泡排序的一種本質(zhì)改進(jìn)。它的基本思想是通過一趟掃描后，使得排序序列的長度能大幅度地減少。在冒泡排序中，一次掃描只能確保最大數(shù)值的數(shù)移到正確位置，而待排序序列的長度可能只減少1?？焖倥判蛲ㄟ^一趟掃描，就能確保某個(gè)數(shù)（以它為基準(zhǔn)點(diǎn)吧）的左邊各數(shù)都比它小，右邊各數(shù)都比它大。然后又用同樣的方法處理它左右兩邊的數(shù)，直到基準(zhǔn)點(diǎn)的左右只有一個(gè)元素為止。 快速排序是不穩(wěn)定的，最理想情況算法時(shí)間復(fù)雜度O(nlog2n)，最壞O(n ^2)。 2.7 希爾排序 在直接插入排序算法中，每次插入一個(gè)數(shù)，使有序序列只增加1個(gè)節(jié)點(diǎn)，并且對插入下一個(gè)數(shù)沒有提供任何幫助。如果比較相隔較遠(yuǎn)距離（稱為 增量）的數(shù)，使得數(shù)移動時(shí)能跨過多個(gè)元素，則進(jìn)行一次比較就可能消除多個(gè)元素交換。D.L.shell于1959年在以他名字命名的排序算法中實(shí)現(xiàn)了這一思想。算法先將要排序的一組數(shù)按某個(gè)增量d分成若干組，每組中記錄的下標(biāo)相差d.對每組中全部元素進(jìn)行排序，然后再用一個(gè)較小的增量對它進(jìn)行，在每組中再進(jìn)行排序。當(dāng)增量減到1時(shí)，整個(gè)要排序的數(shù)被分成一組，排序完成。 希爾排序是不穩(wěn)定的，其時(shí)間復(fù)雜度為O(n ^2)。 排序類別 時(shí)間復(fù)雜度 空間復(fù)雜度 穩(wěn)定 1 插入排序 O(n2) 1 √ 2 希爾排序 O(n2) 1 × 3 冒泡排序 O(n2) 1 √ 4 選擇排序 O(n2) 1 × 5 快速排序 O(Nlogn) O(logn) × 6 堆排序 O(Nlogn) 1 × 7 歸并排序 O(Nlogn) O(n) √

0

順序查找， O(n) 二分， O(logn)需要排序分塊 分塊查找？ 不知道..英文是什么？ 直接插入 O(n^2) 快速排序 最壞情況O(n^2) 平均O(nlogn) 起泡 和插入很像吧 O(n^2) 希爾，O(n^x) 1<x<2 需要比較復(fù)雜的分析方法選擇 沒聽過堆排序 最壞情況和平均都是O(nlogn) 其他：歸并(merge) O(nlogn) radix() （看怎么來理解n，也可以說O(n)也可以O(shè)(nlogn),需要調(diào)用穩(wěn)定的子排序算法） basket O(n) 這兩個(gè)屬于非比較排序。 給予比較操作（> 或< ）的排序算法理論最低復(fù)雜度是O(nlogn) 證明： 所有可能情況為n! 構(gòu)造決策樹需要n!子節(jié)點(diǎn) <為二分操作，所以樹為二叉樹，高度為O(logn!)=O(nlogn)

以上就是關(guān)于各種排序算法的比較相關(guān)問題的回答。希望能幫到你，如有更多相關(guān)問題，您也可以聯(lián)系我們的客服進(jìn)行咨詢，客服也會為您講解更多精彩的知識和內(nèi)容。

推薦閱讀：

紡織品ce認(rèn)證（各種紡織品認(rèn)證）

C4D入門必備：超全的C4D建模教程，掌握各種建模的方式方法

抖音各種類型視頻占比（抖音視頻的類型占比）

手機(jī)畫平面圖軟件app（手機(jī)畫平面圖軟件）

微信企業(yè)微信是什么