幾種排序算法效率的比較

《幾種排序算法效率的比較》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。

1、1.穩(wěn)定性比較插入排序、冒泡排序、二叉樹排序、二路歸并排序及其他線形排序是穩(wěn)定的選擇排序、希爾排序、快速排序、堆排序是不穩(wěn)定的2.時(shí)間復(fù)雜性比較插入排序、冒泡排序、選擇排序的時(shí)間復(fù)雜性為O(n2)其它非線形排序的時(shí)間復(fù)雜性為O(nlog2n)線形排序的時(shí)間復(fù)雜性為O(n);3.輔助空間的比較線形排序、二路歸并排序的輔助空間為O(n),其它排序的輔助空間為O(1);4.其它比較插入、冒泡排序的速度較慢，但參加排序的序列局部或整體有序時(shí)，這種排序能達(dá)到較快的速度。反而在這種情況下，快速排序反而慢了。當(dāng)n較小時(shí)，對(duì)穩(wěn)定性不作要求時(shí)宜用選擇排序，

2、對(duì)穩(wěn)定性有要求時(shí)宜用插入或冒泡排序。若待排序的記錄的關(guān)鍵字在一個(gè)明顯有限范圍內(nèi)時(shí),且空間允許是用桶排序。當(dāng)n較大時(shí)，關(guān)鍵字元素比較隨機(jī)，對(duì)穩(wěn)定性沒(méi)要求宜用快速排序。當(dāng)n較大時(shí)，關(guān)鍵字元素可能出現(xiàn)本身是有序的，對(duì)穩(wěn)定性有要求時(shí)，空間允許的情況下。宜用歸并排序。當(dāng)n較大時(shí)，關(guān)鍵字元素可能出現(xiàn)本身是有序的，對(duì)穩(wěn)定性沒(méi)有要求時(shí)宜用堆排序。*************************************************************************************重溫經(jīng)典排序思想--C語(yǔ)言常用排序全解?/

3、*=============================================================================相關(guān)知識(shí)介紹（所有定義只為幫助讀者理解相關(guān)概念，并非嚴(yán)格定義）：1、穩(wěn)定排序和非穩(wěn)定排序簡(jiǎn)單地說(shuō)就是所有相等的數(shù)經(jīng)過(guò)某種排序方法后，仍能保持它們?cè)谂判蛑暗南鄬?duì)次序，我們就說(shuō)這種排序方法是穩(wěn)定的。反之，就是非穩(wěn)定的。比如：一組數(shù)排序前是a1,a2,a3,a4,a5，其中a2=a4，經(jīng)過(guò)某種排序后為a1,a2,a4,a3,a5，則我們說(shuō)這種排序是穩(wěn)定的，因?yàn)閍2排序前在a4的前面，排序后

4、它還是在a4的前面。假如變成a1,a4,a2,a3,a5就不是穩(wěn)定的了。2、內(nèi)排序和外排序在排序過(guò)程中，所有需要排序的數(shù)都在內(nèi)存，并在內(nèi)存中調(diào)整它們的存儲(chǔ)順序，稱為內(nèi)排序；在排序過(guò)程中，只有部分?jǐn)?shù)被調(diào)入內(nèi)存，并借助內(nèi)存調(diào)整數(shù)在外存中的存放順序排序方法稱為外排序。3、算法的時(shí)間復(fù)雜度和空間復(fù)雜度所謂算法的時(shí)間復(fù)雜度，是指執(zhí)行算法所需要的計(jì)算工作量。一個(gè)算法的空間復(fù)雜度，一般是指執(zhí)行這個(gè)算法所需要的內(nèi)存空間。====================================================================

5、============*//*================================================功能：選擇排序輸入：數(shù)組名稱（也就是數(shù)組首地址）、數(shù)組中元素個(gè)數(shù)================================================*//*====================================================算法思想簡(jiǎn)單描述：在要排序的一組數(shù)中，選出最小的一個(gè)數(shù)與第一個(gè)位置的數(shù)交換；然后在剩下的數(shù)當(dāng)中再找最小的與第二個(gè)位置的數(shù)交換，如此循環(huán)到倒數(shù)第二

6、個(gè)數(shù)和最后一個(gè)數(shù)比較為止。選擇排序是不穩(wěn)定的。算法復(fù)雜度O(n2)--[n的平方]=====================================================*/voidselect_sort(int*x,intn){inti,j,min,t;for(i=0;i

7、??{???????min=j;/*如果后面的數(shù)比前面的小，則記下它的下標(biāo)*/???}??}??????if(min!=i)/*如果min在循環(huán)中改變了，就需要交換數(shù)據(jù)*/??{???t=*(x+i);???*(x+i)=*(x+min);???*(x+min)=t;??}}}/*================================================功能：直接插入排序輸入：數(shù)組名稱（也就是數(shù)組首地址）、數(shù)組中元素個(gè)數(shù)================================================*

8、//*====================================================算法思想簡(jiǎn)單描述：在要排序的一組數(shù)中，假設(shè)前面(n-1)[n>=2]個(gè)數(shù)已經(jīng)是排好