基數(shù)排序

屬于分配式排序,又稱(chēng)桶子法,通過(guò)鍵值的各個(gè)位上的值,將要排序的元素分配至某些桶中,達(dá)到排序的作用.

基數(shù)排序?qū)儆诜€(wěn)定性排序,是效率高的穩(wěn)定性排序法

是桶排序的擴(kuò)展,將整數(shù)按照位數(shù)進(jìn)行切割,再按各個(gè)位數(shù)進(jìn)行比較

是用空間換時(shí)間的經(jīng)典算法

在使用8kw個(gè)數(shù)據(jù)進(jìn)行測(cè)試時(shí)

需要8kw*11個(gè)數(shù)組 *4個(gè)字節(jié) /1024k/1024m/1024g = 3.3G

不難看出基數(shù)排序?qū)臻g的要求非常高

排序思路

eg:{53,3,542,748,14,214}

第一輪:

1,取出每個(gè)元素的個(gè)位數(shù)

2,判斷這個(gè)數(shù)應(yīng)該放在對(duì)應(yīng)的哪一個(gè)桶

3,按照桶的順序依次放回原數(shù)組

//個(gè)位小的在放回去后會(huì)在前面

第二輪:

1,取出每個(gè)元素的十位數(shù)

2,判斷這個(gè)數(shù)應(yīng)該放在哪一個(gè)桶,如果沒(méi)有十位則補(bǔ)零

3,按照桶順序依次放回原數(shù)組

//十位小的在放回去后會(huì)在前面

…

//此時(shí)在依次放入桶中時(shí),最高位相同的數(shù),十位小的會(huì)被先放入

直到最高位放入桶中

此時(shí)再按最高位放入隊(duì)列

記錄每個(gè)桶中放置了多少數(shù)據(jù)

代碼實(shí)現(xiàn)

定義一個(gè)二維數(shù)組,表示10個(gè)桶,每個(gè)桶為一個(gè)一維數(shù)組

定義一個(gè)10個(gè)元素的一維數(shù)組用以保存從0-9的桶中數(shù)量

按位循環(huán)遍歷數(shù)組中每個(gè)元素直到遍歷到最高位結(jié)束

public void bucketsort(int[] arr) {int[][] arr1 = new int[10][arr.length];int max = arr[0];for (int i = 0; i < arr.length; i++) {max = Math.max(max, arr[i]);}for (int i = 0; i < Integer.toString(max).length(); i++) {int[] count = new int[10];for (int i1 = 0; i1 < arr.length; i1++) {int temp = arr[i1] / (int) (Math.pow(10, i)) % 10;arr1[temp][count[temp]] = arr[i1];count[temp]++;}int t = 0;for (int i1 = 0; i1 < 10; i1++) {for (int k = 0; k < count[i1]; k++) {arr[t] = arr1[i1][k];t++;}}}
}

總結(jié)

并不復(fù)雜的思路,典型的空間換時(shí)間算法