下面介紹的排序都為:非比較排序法
這里個(gè)人認(rèn)為在某些特定的地方非比較排序的速度非常明顯;
比如 : 對(duì)待排數(shù)據(jù)中有順序分類,使用鴿巢總體分類,然后對(duì)不同類別的待排小數(shù)據(jù)集合采用 插入,快排等排序方式
Counting sort :計(jì)數(shù)排序
描述:迭代待排序數(shù)組出元素x,確定小于此元素[z]個(gè)數(shù),然后把x放到它在的最終輸出數(shù)組[z]上。
特性:與待排值有關(guān);穩(wěn)定的排序算法;待排序數(shù)據(jù)要求過(guò)于嚴(yán)格,無(wú)實(shí)際用處;
算法的步驟如下:
1. 找出待排序的數(shù)組中最大和最小的元素
2. 統(tǒng)計(jì)數(shù)組中每個(gè)值為i的元素出現(xiàn)的次數(shù),存入數(shù)組C的第i項(xiàng)
3. 對(duì)所有的計(jì)數(shù)累加(從C中的第一個(gè)元素開(kāi)始,每一項(xiàng)和前一項(xiàng)相加)
4. 反向填充目標(biāo)數(shù)組:將每個(gè)元素i放在新數(shù)組的第C(i)項(xiàng),每放一個(gè)元素就將C(i)減去1
Radix sort:基數(shù)排序
描述:將所有待比較數(shù)值(正整數(shù))統(tǒng)一為同樣的數(shù)位長(zhǎng)度,數(shù)位較短的數(shù)前面補(bǔ)零. 然后, 從最低位開(kāi)始, 依次進(jìn)行一次排序.這樣從最低位排序一直到最高位排序完成以后, 數(shù)列就變成一個(gè)有序序列.
排序方式:LSD 由右向左排;MSD 由左向右排
特性:非比較排序;待排數(shù)據(jù)需要統(tǒng)一格式;
假設(shè)需排序數(shù)列的取值范圍從1...k,我們于是建一個(gè)K+1元的數(shù)組 a[],并賦初值為0,然后便開(kāi)始排序工作:
算法的步驟如下:
1. 按輸入順序讀入數(shù)列,如果所讀的元素為i(1<=i<=k),我們就將a[i]的值加一,這樣直到讀完所有的元素。
2. 讀出元素并排序:我們遍歷整個(gè)數(shù)組,如果a[i]=j(j>=0),我們就輸出j次i(表示元素i在原先數(shù)列中出現(xiàn)了j次),這樣輸出的序列就是已排序的。
3. 由于一般排序算法涉及到元素之間的比較,如果化成比較樹(shù)可以知道,這樣的排序算法復(fù)雜度的下限是O(N*lnN),而計(jì)數(shù)排序沒(méi)有比較元素,所以所需排序時(shí)間就少了,我們可以看到計(jì)數(shù)排序的復(fù)雜度為O(n*k),其中k(k的定義同上)為合并排列所需的時(shí)間,是個(gè)常數(shù)。
4. 此算法適合所需排列的元素取值范圍不大的情況下,否則會(huì)造成空間的消耗,比如,一共100個(gè)元素,其取值范圍從1-100000,顯然這個(gè)時(shí)候用基數(shù)排序是不合適的。
Bucket sort:桶排序
描述:工作的原理是將陣列分到有限數(shù)量的桶子里。每個(gè)桶子再個(gè)別排序(有可能再使用別的排序算法或是以遞回方式繼續(xù)使用桶排序進(jìn)行排序)。
桶排序以下列程序進(jìn)行:
1. 設(shè)置一個(gè)定量的陣列當(dāng)作空桶子。
2. 尋訪序列,并且把項(xiàng)目一個(gè)一個(gè)放到對(duì)應(yīng)的桶子去。
3. 對(duì)每個(gè)不是空的桶子進(jìn)行排序。
4. 從不是空的桶子里把項(xiàng)目再放回原來(lái)的序列中。
Pigeonhole sort:鴿巢排序
描述:是一種時(shí)間復(fù)雜度為O(n)且在不可避免遍歷每一個(gè)元素并且排序的情況下效率最好的一種排序算法. 但它只有在差值(或者可被映射在差值)很小的范圍內(nèi)的數(shù)值排序的情況下實(shí)用.
算法的步驟如下:與桶排同
整理 www.aygfsteel.com/Good-Game
這里個(gè)人認(rèn)為在某些特定的地方非比較排序的速度非常明顯;
比如 : 對(duì)待排數(shù)據(jù)中有順序分類,使用鴿巢總體分類,然后對(duì)不同類別的待排小數(shù)據(jù)集合采用 插入,快排等排序方式
Counting sort :計(jì)數(shù)排序
描述:迭代待排序數(shù)組出元素x,確定小于此元素[z]個(gè)數(shù),然后把x放到它在的最終輸出數(shù)組[z]上。
特性:與待排值有關(guān);穩(wěn)定的排序算法;待排序數(shù)據(jù)要求過(guò)于嚴(yán)格,無(wú)實(shí)際用處;
算法的步驟如下:
1. 找出待排序的數(shù)組中最大和最小的元素
2. 統(tǒng)計(jì)數(shù)組中每個(gè)值為i的元素出現(xiàn)的次數(shù),存入數(shù)組C的第i項(xiàng)
3. 對(duì)所有的計(jì)數(shù)累加(從C中的第一個(gè)元素開(kāi)始,每一項(xiàng)和前一項(xiàng)相加)
4. 反向填充目標(biāo)數(shù)組:將每個(gè)元素i放在新數(shù)組的第C(i)項(xiàng),每放一個(gè)元素就將C(i)減去1
Radix sort:基數(shù)排序
描述:將所有待比較數(shù)值(正整數(shù))統(tǒng)一為同樣的數(shù)位長(zhǎng)度,數(shù)位較短的數(shù)前面補(bǔ)零. 然后, 從最低位開(kāi)始, 依次進(jìn)行一次排序.這樣從最低位排序一直到最高位排序完成以后, 數(shù)列就變成一個(gè)有序序列.
排序方式:LSD 由右向左排;MSD 由左向右排
特性:非比較排序;待排數(shù)據(jù)需要統(tǒng)一格式;
假設(shè)需排序數(shù)列的取值范圍從1...k,我們于是建一個(gè)K+1元的數(shù)組 a[],并賦初值為0,然后便開(kāi)始排序工作:
算法的步驟如下:
1. 按輸入順序讀入數(shù)列,如果所讀的元素為i(1<=i<=k),我們就將a[i]的值加一,這樣直到讀完所有的元素。
2. 讀出元素并排序:我們遍歷整個(gè)數(shù)組,如果a[i]=j(j>=0),我們就輸出j次i(表示元素i在原先數(shù)列中出現(xiàn)了j次),這樣輸出的序列就是已排序的。
3. 由于一般排序算法涉及到元素之間的比較,如果化成比較樹(shù)可以知道,這樣的排序算法復(fù)雜度的下限是O(N*lnN),而計(jì)數(shù)排序沒(méi)有比較元素,所以所需排序時(shí)間就少了,我們可以看到計(jì)數(shù)排序的復(fù)雜度為O(n*k),其中k(k的定義同上)為合并排列所需的時(shí)間,是個(gè)常數(shù)。
4. 此算法適合所需排列的元素取值范圍不大的情況下,否則會(huì)造成空間的消耗,比如,一共100個(gè)元素,其取值范圍從1-100000,顯然這個(gè)時(shí)候用基數(shù)排序是不合適的。
Bucket sort:桶排序
描述:工作的原理是將陣列分到有限數(shù)量的桶子里。每個(gè)桶子再個(gè)別排序(有可能再使用別的排序算法或是以遞回方式繼續(xù)使用桶排序進(jìn)行排序)。
桶排序以下列程序進(jìn)行:
1. 設(shè)置一個(gè)定量的陣列當(dāng)作空桶子。
2. 尋訪序列,并且把項(xiàng)目一個(gè)一個(gè)放到對(duì)應(yīng)的桶子去。
3. 對(duì)每個(gè)不是空的桶子進(jìn)行排序。
4. 從不是空的桶子里把項(xiàng)目再放回原來(lái)的序列中。
Pigeonhole sort:鴿巢排序
描述:是一種時(shí)間復(fù)雜度為O(n)且在不可避免遍歷每一個(gè)元素并且排序的情況下效率最好的一種排序算法. 但它只有在差值(或者可被映射在差值)很小的范圍內(nèi)的數(shù)值排序的情況下實(shí)用.
算法的步驟如下:與桶排同
整理 www.aygfsteel.com/Good-Game