1. 內(nèi)部排序與外部排序的區(qū)別：

　　排序過程中涉及的存儲(chǔ)器不同，內(nèi)部排序所操作的數(shù)據(jù)都存放于內(nèi)存；而外部排序所操作的數(shù)據(jù)量太大以至于不能全部放于內(nèi)存，會(huì)涉及到外存訪問。

　　

　　2. 內(nèi)部排序算法的穩(wěn)定性：

　　待排序的數(shù)據(jù)中如果有兩個(gè)相等的數(shù)據(jù)，經(jīng)過排序算法之后的先后順序依據(jù)不變的話，則稱該排序方法是穩(wěn)定的，否則就是不穩(wěn)定的。

?

　　3.內(nèi)部排序算法的分類：

3.1 按內(nèi)部排序過程中所需的工作量來(lái)區(qū)分可分為三類：

(1)?? 簡(jiǎn)單的排序方法, 其時(shí)間復(fù)雜度為n*n

(2)?? 先進(jìn)的排序方法, 其時(shí)間復(fù)雜度為nlogn

(3)?? 基數(shù)排序，其時(shí)間復(fù)雜度為d*n

?

3.2 按內(nèi)部排序過程中所依據(jù)的不同原則可分為五類：

(1)插入排序：? 直接插入排序? ?折半插入排序? ? 2-路插入排序? ? ?表插入排序? ? ? 希爾排序

(2)交換排序：? 起泡排序? ? ?快速排序

(3)選擇排序：? 簡(jiǎn)單選擇排序? ? 樹形選擇排序? ? ?堆排序

(4)歸并排序：? 2-路歸并排序??

(5)基數(shù)排序：? ?鏈?zhǔn)交鶖?shù)排序

?

　　下表是各內(nèi)部排序方法的總覽：

?

　　3.3

　　另外，對(duì)于單個(gè)記錄所占空間太大時(shí)，排序過程中不合適直接進(jìn)行記錄間的交換，而有些內(nèi)部排序方法如堆排序、快速排序，無(wú)法像表插入排序、鏈?zhǔn)交鶖?shù)排序那樣，以修改指針代替記錄移動(dòng)，這種情況下，可以另設(shè)一個(gè)地址向量，當(dāng)移動(dòng)和比較記錄時(shí)，利用地址向量中的值實(shí)現(xiàn)，與此方法相關(guān)的算法見 地址排序(重排算法)

?

　　 3.4?最后，探討下，”內(nèi)部排序可能達(dá)到的最快速度？”

?　　上述討論的排序方法(除基數(shù)排序外)，都是基于“關(guān)鍵字間的比較”實(shí)現(xiàn)的，這類操作可以用一個(gè)判定樹描述，利用二叉樹相關(guān)的基礎(chǔ)性質(zhì)知，借助于“比較”進(jìn)行排序的算法在最壞情況下能達(dá)到的最好的時(shí)間復(fù)雜度就是nlog2n

轉(zhuǎn)載于:https://www.cnblogs.com/aimmiao/p/9346410.html

總結(jié)

以上是生活随笔為你收集整理的内部排序(总结篇)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。