前言：
現(xiàn)在安卓面試，對(duì)于算法的問(wèn)題也越來(lái)越多了，要求也越來(lái)越多，特別是排序，基本必考題，而且還動(dòng)不動(dòng)就要手寫(xiě)，所以陸續(xù)要寫(xiě)算法的文章，也正好當(dāng)自己學(xué)習(xí)。o(╥﹏╥)o
Android技能書(shū)系列：
Android基礎(chǔ)知識(shí)
Android技能樹(shù) — 動(dòng)畫(huà)小結(jié)
Android技能樹(shù) — Activity小結(jié)
Android技能樹(shù) — View事件體系小結(jié)
Android技能樹(shù) — Android存儲(chǔ)路徑及IO操作小結(jié)
Android技能樹(shù) — 多進(jìn)程相關(guān)小結(jié)
Android技能樹(shù) — Drawable小結(jié)
數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)知識(shí)
Android技能樹(shù) — 數(shù)組,鏈表,散列表基礎(chǔ)小結(jié)
算法基礎(chǔ)知識(shí)
Android技能樹(shù) — 排序算法基礎(chǔ)小結(jié)
本文主要講算法基礎(chǔ)知識(shí)及排序算法。
基礎(chǔ)知識(shí)：
穩(wěn)定性：
我們經(jīng)常聽(tīng)到說(shuō)XXX排序算法是穩(wěn)定性算法，XXX排序算法是不穩(wěn)定性算法，那穩(wěn)定性到底是啥呢？
舉個(gè)最簡(jiǎn)單的例子：我們知道冒泡排序中最重要的是二二進(jìn)行比較，然后按照大小來(lái)?yè)Q位置：
if(arr[j]>arr[j+1]){
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
我們可以看到這里的大小判定是前一個(gè)比后一個(gè)大，就換位置，如果相等就不會(huì)進(jìn)入到if的執(zhí)行代碼中，所以我們二個(gè)相同的數(shù)挨在一起，不會(huì)進(jìn)行移動(dòng)，所以冒泡排序是穩(wěn)定的排序算法，但是如果我們把上面的代碼改動(dòng)一下if里面的判斷：
if(arr[j]>=arr[j+1]){
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
我們添加了一個(gè)等號(hào)，那這個(gè)時(shí)候就不是穩(wěn)定排序算法了，因?yàn)槲覀兛梢钥吹较嗟鹊臅r(shí)候它也換了位置了。
證明某個(gè)排序是不穩(wěn)定很簡(jiǎn)單，比如你只要傳入{2,2}，只要換了位置就是不穩(wěn)定，證明不穩(wěn)定只要一種情況下是不穩(wěn)定的，那么就是不穩(wěn)定排序算法。
復(fù)雜度
復(fù)雜度包括了時(shí)間復(fù)雜度和空間復(fù)雜度，但是通常我們單純說(shuō)復(fù)雜度的時(shí)候都指時(shí)間復(fù)雜度。
時(shí)間復(fù)雜度
用1+2+3+...+100為例：
普通寫(xiě)法：
int sum = 0, n = 100;//執(zhí)行1次
for(int i =1 ; i <= 100 ; i++){ //執(zhí)行n+1次
sum = sum + i; //執(zhí)行n次
}
Log.v("demo","sum:"+sum); //執(zhí)行1次
我們可以看到一共執(zhí)行了2n+3次。（我們這里是2*100+3）
高斯算法：
int sum = 0,n = 100; //執(zhí)行1次
sum = (1+n)*n /2; //執(zhí)行1次
Log.v("demo","sum:"+sum); //執(zhí)行1次
我們可以看到一共執(zhí)行了3次。
但是當(dāng)我們的n很大的時(shí)候，比如變成了1000，第一種算法就是2*1000+3，但是第二種還是3次。
在進(jìn)行算法分析時(shí)，語(yǔ)句總的執(zhí)行次數(shù)T(n)是關(guān)于問(wèn)題規(guī)模n的函數(shù)，進(jìn)而分析T(n)隨n的變化情況并確定T(n)的數(shù)量級(jí)。算法的時(shí)間復(fù)雜度，也就是算法的時(shí)間量度，記作：T(n) = O(f(n))。它表示隨問(wèn)題規(guī)模n的增大，算法執(zhí)行時(shí)間的增長(zhǎng)率和f(n)的增長(zhǎng)率相同，稱(chēng)作算法的漸近時(shí)間復(fù)雜度，簡(jiǎn)稱(chēng)為時(shí)間復(fù)雜度。其中f(n)是問(wèn)題規(guī)模n的某個(gè)函數(shù)。
我們已經(jīng)根據(jù)上面的解釋看到了：
T(n) = O(f(n))；
所以第一種是：2*n + 3 = O(f(n)),第二種是3 = O(f(n))；我們可以看到是增長(zhǎng)率和f(n)的增長(zhǎng)率相同。
我們以前學(xué)高數(shù)都知道：比如f(x) = x^3 + 2x ,隨著x的變大，其實(shí)基本都是x^3的值，而2x的的值后面影響越來(lái)越小，所以有高階的時(shí)候，其他低階都可以隨著x的變大而忽略，同理前面的相乘的系數(shù)也是一樣，所以：
那我們上面的第一種就變成了O(n)（ps:只保留最高位，系數(shù)變?yōu)?,），第二種變?yōu)榱薕(1)（ps:常數(shù)都變?yōu)?）
常見(jiàn)的時(shí)間復(fù)雜度：
最壞/最好/平均情況
比如我們玩猜數(shù)字，讓你在1-n范圍內(nèi)猜某個(gè)數(shù)字，而你是從頭到尾報(bào)數(shù)，如果猜的數(shù)正好是1，則最好情況下復(fù)雜度是1，如果猜的數(shù)是n,則最壞是n,平均的話就是n/2。排序也是一樣，比如2,1,3,4,5,6,7,8,9你只需要調(diào)換2,1就可以，但是如果是9,8,7,6,5,4,3,2,1讓你從小到大排序，你需要調(diào)換很多次。
空間復(fù)雜度
引用《大話數(shù)據(jù)結(jié)構(gòu)》中的例子，比如你要計(jì)算某一年是不是閏年，你可以寫(xiě)一個(gè)算法:
if(year%4==0 && year%100 != 0){
System.out.println("該年是閏年");
}else if(year % 400 == 0){
System.out.println("該年是閏年");
}else{
System.out.println("該年是平年");
}
但是如果你在內(nèi)存中存儲(chǔ)了一個(gè)2150元素的數(shù)組，然后這個(gè)數(shù)組中是index是閏年的數(shù)組設(shè)置為1，其他設(shè)置為0，這樣別人比如問(wèn)你2000年是不是閏年，你直接查看該數(shù)組index為2000里面的值是不是1即可。這樣通過(guò)一筆空間上的開(kāi)銷(xiāo)來(lái)?yè)Q取了計(jì)算時(shí)間。
一個(gè)算法的優(yōu)劣主要從算法的執(zhí)行時(shí)間和所需要占用的存儲(chǔ)空間兩個(gè)方面衡量。
排序算法：
排序方法分為兩大類(lèi): 一類(lèi)是內(nèi)部排序, 指的是待排序記錄存放在計(jì)算機(jī)存儲(chǔ)器中進(jìn)行的排序過(guò)程；另一類(lèi)是外部排序, 指的是待排序記錄的數(shù)量很大，以至于內(nèi)存一次不能容納全部記錄，在排序過(guò)程中尚需對(duì)外存進(jìn)行訪問(wèn)的排序過(guò)程。
內(nèi)部排序：
冒泡排序：
冒泡排序算法的運(yùn)作如下：（從后往前）
1.比較相鄰的元素。如果第一個(gè)比第二個(gè)大，就交換他們兩個(gè)。
2.對(duì)每一對(duì)相鄰元素作同樣的工作，從開(kāi)始第一對(duì)到結(jié)尾的最后一對(duì)。在這一點(diǎn)，最后的元素應(yīng)該會(huì)是最大的數(shù)。
3.針對(duì)所有的元素重復(fù)以上的步驟，除了最后一個(gè)。
4.持續(xù)每次對(duì)越來(lái)越少的元素重復(fù)上面的步驟，直到?jīng)]有任何一對(duì)數(shù)字需要比較。
我們以最簡(jiǎn)單的數(shù)組{3,2,1}來(lái)看：
我們可以看到一種二個(gè)大的藍(lán)色步驟（ps：3 - 1），然后每個(gè)藍(lán)色里面的交換步驟是一步步變少(ps:2,1)。
所以我們就知道是二個(gè)for循環(huán)了：
/**
我們的藍(lán)色大框一共執(zhí)行（3-1）次，
也就是（nums.length -1）次
*/
for (int i = length -1; i > 0; i--) {
/**
我們藍(lán)色大框交換步驟從（3-1）次開(kāi)始，
且每個(gè)藍(lán)色大框里面的交換步驟在逐步減一，
正好就是上面的藍(lán)色大框的（i變量）
*/
for (int j = 0; j < i; j++) {
//對(duì)比邏輯代碼
}
}
然后在里面加上判斷，如果前一個(gè)比后一個(gè)大，交換位置即可。
public void bubbleSort(int[] nums) {
//傳進(jìn)來(lái)的數(shù)組只有0或者1個(gè)元素，則不需要排序
int length = nums.length;
if (length < 2) {
return;
}
for (int i = length -1; i > 0; i--) {
for (int j = 0; j < i; j++) {
if (nums[j] > nums[j + 1]) {
int data = nums[j];
nums[j] = nums[j + 1];
nums[j + 1] = data;
}
}
}
}
快速排序：
我們會(huì)先找一個(gè)關(guān)鍵數(shù)據(jù)，通常為第一個(gè)數(shù)，比如我們這里的5，然后把數(shù)字小于5的數(shù)字都放在5的左邊，大于5的數(shù)字都放在5右邊，然后對(duì)于左邊的數(shù)字使用相同的方法，取第一個(gè)為關(guān)鍵數(shù)據(jù)，對(duì)其排序，然后一直這么重復(fù)。
偽代碼：
quickSort ( nums ){
//小于2個(gè)的數(shù)組直接返回，因?yàn)閭€(gè)數(shù)為0或者1的肯定是有序數(shù)組
if(nums.length < 2){
return nums;
}
//取數(shù)組第一個(gè)數(shù)為參考值
data = nums[0];
//左邊的數(shù)組
smallNums = （遍歷nums中比data小的數(shù)）
//右邊的數(shù)組
bigNums = （遍歷nums中比data大的數(shù)）
//使用遞歸,對(duì)左邊和右邊的數(shù)組分別再使用我們寫(xiě)的這個(gè)方法。
return quickSort(smallNums) + data + quickSort(bigNums);
}
我們一步步來(lái)看如何實(shí)現(xiàn)具體的代碼：(我會(huì)先根據(jù)思路寫(xiě)一個(gè)步驟很多的寫(xiě)法，用于介紹，再寫(xiě)一個(gè)好的。)
其實(shí)要實(shí)現(xiàn)功能，這個(gè)很簡(jiǎn)單，我們可以新建二個(gè)數(shù)組，然后再完全遍歷整個(gè)原始數(shù)組，把比參考值小的和大的分別放入二個(gè)數(shù)組。
//取第一個(gè)數(shù)為參考值
int data = nums[0];
//我們先獲取比參考值大的數(shù)及小的數(shù)各自是多少。
int smallSize = 0, bigSize = 0;
for (int i = 1; i < nums.length; i++) {
if (nums[i] <= data) {
smallSize++;
} else {
bigSize++;
}
}
//建立相應(yīng)的數(shù)組，等會(huì)用來(lái)放左邊和右邊的數(shù)組
int[] smallNums = new int[smallSize];
int[] bigNums = new int[bigSize];
//遍歷nums數(shù)組，把各自大于或者小于參考值的放入各自左邊和右邊的數(shù)組。
int smallIndex = 0;
int bigIndex = 0;
for (int i = 1; i < nums.length; i++) {
if (nums[i] > data) {
bigNums[bigIndex] = nums[i];
bigIndex++;
}else{
smallNums[smallIndex] = nums[i];
smallIndex++;
}
}
//左邊和右邊再各自使用遞歸調(diào)用
smallNums = quickSort(smallNums);
bigNums = quickSort(bigNums);
//然后再把smallNums的所有數(shù)值賦給data左邊，然后nums中間為data,然后再bigNums把data右邊。
for (int i = 0; i < smallNums.length; i++) {
nums[i] = smallNums[i];
}
nums[smallNums.length] = data;
for (int i = smallSize + 1; i < bigNums.length + smallSize + 1; i++) {
nums[i] = bigNums[i - smallSize - 1];
}
當(dāng)然這也是可以實(shí)現(xiàn)的，可是感覺(jué)代碼很多，而且每次調(diào)用quickSort進(jìn)行遞歸的時(shí)候，都要新建二個(gè)數(shù)組，這樣后面遞歸調(diào)用次數(shù)越多，新建的數(shù)組對(duì)象也會(huì)很多。我們可不可以思路不變，參考值左邊是小的值，參考值右邊是大的值，但是不新建數(shù)組。答案是當(dāng)然！?。ㄟ@逼裝的太累了，休息一下。）
- 我們?cè)谧筮呴_(kāi)始的地方標(biāo)記為 i ,右邊為 j ,然后因?yàn)?i 的位置已經(jīng)是我們的參考值了，所以從 j 那邊開(kāi)始移動(dòng)，
- 因?yàn)槲覀兊哪繕?biāo)是左邊的數(shù)是比參考值小，右邊的比參考值大，所以從 j 開(kāi)始往左移動(dòng)，當(dāng)找到一個(gè)比5小的數(shù)字，然后停住，
- 然后 i 從左邊開(kāi)始往右移動(dòng)，然后找到比參考值大的數(shù)，然后停住，
- 交換 i 跟 j 指向的數(shù)
- 重復(fù) 2,3,4 直到 i 跟 j 重合（比如index為h的地方），然后交換我們的參考值跟這個(gè) h 交換數(shù)據(jù)。
剩下的左邊和右邊的數(shù)組也都通過(guò)遞歸執(zhí)行這個(gè)方法即可。
public static void QuickSort(int[] nums, int start, int end) {
//如果start >= end了，說(shuō)明數(shù)組就一個(gè)數(shù)了。不需要排序
if(start >= end){
return;
}
//取第一個(gè)數(shù)為參考值
int data = nums[start];
int i = start, j = end;
//當(dāng) i 和 j 還沒(méi)有碰到一起時(shí)候，一直重復(fù)移動(dòng) j 和 i 等操作
while (i != j) {
//當(dāng) j 位置比參考值大的時(shí)候，繼續(xù)往左邊移動(dòng)，直到找到一個(gè)比參考值小的數(shù)才停下
while (nums[j] >= data && i < j) {
j--;
}
//當(dāng) i 位置比參考值小的時(shí)候，繼續(xù)往右邊移動(dòng)，直到找到一個(gè)比參考值大的數(shù)才停下
while (nums[i] <= data && i < j) {
i++;
}
//交換二邊的數(shù)
if (i < j) {
int t = nums[i];
nums[i] = nums[j];
nums[j] = t;
}
}
//當(dāng)退出上面的循環(huán)，說(shuō)明 i 和 j 的位置交匯了，更換參考值與 i 位置的值。
nums[start] = nums[i];
nums[i] = data;
//左邊的數(shù)組通過(guò)遞歸繼續(xù)調(diào)用，這時(shí)候因?yàn)閰⒖贾翟?i 的位置，所以左邊是從start 到 i -1
QuickSort(nums, start, i - 1);
//右邊的數(shù)組通過(guò)遞歸繼續(xù)調(diào)用，這時(shí)候因?yàn)閰⒖贾翟?i 的位置，所以右邊是從 i -1 到 end
QuickSort(nums, i + 1, end);
}
直接插入排序：
可以看到，我們是默認(rèn)把第一個(gè)數(shù)字當(dāng)做是排好序的數(shù)組（廢話，一個(gè)數(shù)字當(dāng)然是排好序的），然后每次后一個(gè)跟前面的進(jìn)行比較排序，然后重復(fù)。所以我們可以看到最外面的一共是N-1層。然后每一層里面的比較次數(shù)是跟當(dāng)前層數(shù)數(shù)量相同。
比如第二層。我們的數(shù)字2要和前面的1,3比較，那就要先跟3比較（當(dāng)然如果此處比3大就不需要比較了，因?yàn)榍懊嬉呀?jīng)是個(gè)有序數(shù)組了，你比這個(gè)有序數(shù)組最大的值都大，前面的就不需要比了。）如果比3小就要跟1比較，正好比較2次，跟層數(shù)相同。
所以基本代碼肯定是：
for(int i = 1; i < n ; i ++){
if( 當(dāng)前待比較的數(shù) >= 前面的有序數(shù)組最后一個(gè)數(shù)){
continue; //這就沒(méi)必要比較了。
}
for(int j = i-1 ; j >=0 ; j--){
// 當(dāng)前待比較數(shù) 與 前面的有序數(shù)組中的數(shù)一個(gè)個(gè)進(jìn)行比較。然后插在合適的位置。
}
}
針對(duì)這個(gè)排序，代碼本來(lái)只需要像下面這個(gè)一樣即可：
public static void InsertSort(int[] nums) {
for (int i = 1; i < nums.length; i += 1) {
if (nums[i - 1] <= nums[i]) {
continue;
}
int va = i;
int data = nums[i];
for (int j = i - 1; j >= 0; j--) {
if (nums[j] > data) {
va = j;
nums[j + 1] = nums[j];
}
}
nums[va] = data;
}
}
因?yàn)槲覀冞@里的數(shù)字是連續(xù)的，所以間隔是1，但是為了下一個(gè)排序的講解方便，我們假設(shè)它們的間隔是可能不是1，所以改造成下面這個(gè)：
public static void InsertSort(int[] nums, int gap) {
for (int i = gap; i < nums.length; i += gap) {
if (nums[i - gap] > nums[i]) {
int va = i;
int data = nums[i];
for (int j = i - gap; j >= 0; j -= gap) {
if (nums[j] > data) {
va = j;
nums[j + gap] = nums[j];
}
}
nums[va] = data;
}
}
}
希爾排序:
希爾排序是直接插入排序算法的一種更高效的改進(jìn)版本。
我們假設(shè)現(xiàn)在是1-6個(gè)數(shù)字，我們?nèi)?shù)組的<數(shù)量/2>為間隔數(shù)（ps:所以為6/2 = 3），然后按照這個(gè)間隔數(shù)分別分組：
這樣我們可以當(dāng)場(chǎng)有三組數(shù)組{3,4,}，{1,6}，{5,2}
然后對(duì)每組數(shù)組使用直接插入排序。然后我們把間隔數(shù)再除以2（PS:為 3/2 = 1,取為1）。
然后再使用直接插入排序就可以得到最后的結(jié)果了。
所以還記不記得我們上面的直接插入排序代碼寫(xiě)成了public static void InsertSort(int[] nums, int gap),就是為了考慮上面的多個(gè)間隔不為1的數(shù)組。
所以只要考慮我們的循環(huán)了幾次，每次間隔數(shù)是多少就可以了：
public void ShellSort(int[] nums) {
int length = nums.length;
for (int gap = length / 2; gap > 0; gap /= 2) {
InsertSort(nums, gap);
}
}
是不是發(fā)現(xiàn)超級(jí)簡(jiǎn)單。
（ps:這里記錄一下，比如有10個(gè)數(shù)字，因?yàn)槔碚撋鲜敲看纬?，比如應(yīng)該是5,2,1； 但是有些文章是寫(xiě)著5,3,1，有些文章寫(xiě)著5,2,1。我寫(xiě)的代碼也是5,2,1。。。o(╥﹏╥)o到底哪個(gè)更準(zhǔn)確點(diǎn)。）
選擇排序：
選擇排序很簡(jiǎn)單，就是每次遍歷，找出最小的一個(gè)放在前面（或者最大的一個(gè)放在后面），然后接著把剩下的再遍歷一個(gè)個(gè)的找出來(lái)排序。
public void selectSort(int[] nums) {
int min;
int va;
for (int i = 0; i < nums.length; i++) {
min = nums[i];
va = i;
for (int j = i + 1; j < nums.length; j++) {
if (nums[j] < min) {
min = nums[j];
va = j;
}
}
int temp = nums[i];
nums[i] = min;
nums[va] = temp;
}
}
堆排序：
這里我暫時(shí)空著，因?yàn)楦鏄?shù)有關(guān)系，所以我準(zhǔn)備先寫(xiě)一篇二叉樹(shù)的數(shù)據(jù)結(jié)構(gòu)，然后再寫(xiě)這個(gè)排序。有興趣的可以自己去搜下。
歸并排序：
歸并算法，指的是將兩個(gè)順序序列合并成一個(gè)順序序列的方法。
比如有數(shù)列{6，202，100，301，38，8，1}
初始狀態(tài)：6,202,100,301,38,8,1
第一次歸并后：{6,202},{100,301},{8,38},{1}，比較次數(shù)：3；
第二次歸并后：{6,100,202,301}，{1,8,38}，比較次數(shù)：4；
第三次歸并后：{1,6,8,38,100,202,301},比較次數(shù)：4；
這個(gè)引入網(wǎng)絡(luò)上的圖片了：
根據(jù)這個(gè)我們可以看到，我們要先不停的取中間拆分，左右二邊拆開(kāi)，一直拆到為一個(gè)元素的時(shí)候停止，然后再合并。
public void mergeSort(int[] nums, int L, int R) {
//如果只有一個(gè)元素，那就不用排序了
if (L == R) {
return;
} else {
int M = (R + L) / 2;//每次取中間值
mergeSort(nums, L, M);//通過(guò)遞歸再把左邊的按照這個(gè)方式繼續(xù)不停的左右拆分
mergeSort(nums, M + 1, R);//通過(guò)遞歸再把右邊的按照這個(gè)方式繼續(xù)不停的左右拆分
merge(nums, L, M + 1, R);//合并拆分的部分
}
}
我們繼續(xù)通過(guò)圖片來(lái)說(shuō)明上圖最后合并的操作：
然后重復(fù)這個(gè)操作。如果比如左邊的都比較完了，右邊還剩好幾個(gè)，只需要把右邊剩下的全部都移入即可。
public void merge(int[] nums, int L, int M, int R) {
int[] leftNums = new int[M - L];
int[] rightNums = new int[R - M + 1];
for (int i = L; i < M; i++) {
leftNums[i - L] = nums[i];
}
for (int i = M; i <= R; i++) {
rightNums[i - M] = nums[i];
}
int i = 0;
int j = 0;
int k = L;
//左邊還沒(méi)有全部比較完，右邊還沒(méi)有全部比較完
while (i < leftNums.length && j < rightNums.length) {
if (leftNums[i] >= rightNums[j]) {
nums[k] = rightNums[j];
j++;
k++;
} else {
nums[k] = leftNums[i];
i++;
k++;
}
}
//二邊的比完之后，如果左邊還有剩下，就把左邊的全部移入數(shù)組尾部
while (i < leftNums.length) {
nums[k] = leftNums[i];
i++;
k++;
}
//二邊的比完之后，如果右邊還有剩下，就把右邊的全部移入數(shù)組尾部
while (j < rightNums.length) {
nums[k] = rightNums[j];
j++;
k++;
}
}
基數(shù)排序：
先說(shuō)明一個(gè)簡(jiǎn)單的桶排序吧：
比如我們要給{5,3,5,2,8}排序，我們初始化一組內(nèi)容為0的數(shù)組（做為桶），只要把他們當(dāng)做數(shù)組的index值，比如第一個(gè)是5，我們就nums[5] ++ ; 這樣我們只要對(duì)這個(gè)數(shù)組遍歷，取出里面的值，只要不為0就打印出來(lái)。
但是這樣這里就會(huì)有一個(gè)問(wèn)題了，就是如果我的數(shù)組里面最大的數(shù)是100000，那豈不是我初始化的數(shù)組長(zhǎng)度是100000了，明顯不能這樣。我們知道一個(gè)數(shù)字肯定是由{0-9}這些數(shù)組成，只是處于不同的位數(shù)而已，所以我們可以還是按照{(diào)0-9}來(lái)放入某個(gè)桶，但是是先按照個(gè)位數(shù)排序，然后按照十位數(shù)，百位數(shù)，千位數(shù).....等來(lái)一樣樣來(lái)放。
-
比如我們現(xiàn)在是{25,8,1000,158}四個(gè)數(shù)
第一次，我們比較的是個(gè)位數(shù)：
所以我們從左到右，從上到下的新數(shù)組的順序是{1000,25,8,158}
-
第二次，我們比較的是十位數(shù)：
所以新數(shù)組是{1000,8,25,158}
3.第三次，我們比較百位數(shù)：
所以新數(shù)組還是{1000,8,25,158}
- 第四次，我們比較千位數(shù)：
這時(shí)候我們就可以看到最終排序是{8,25,158,1000}
ps:如果還有萬(wàn)位數(shù)等，持續(xù)進(jìn)行以上的動(dòng)作直至最高位數(shù)為止
我們既然知道了，要一直最外層循環(huán)要進(jìn)行最高數(shù)的次數(shù)，所以我們第一步是找出最大的數(shù)有幾位：
//可以通過(guò)遞歸找最大值：
public static int findMax(int[] arrays, int L, int R) {
//如果該數(shù)組只有一個(gè)數(shù)，那么最大的就是該數(shù)組第一個(gè)值了
if (L == R) {
return arrays[L];
} else {
int a = arrays[L];
int b = findMax(arrays, L + 1, R);//找出整體的最大值
if (a > b) {
return a;
} else {
return b;
}
}
}
//也可以通過(guò)for循環(huán)找最大值：
public static int findMax(int[] arrays, int L, int R) {
int length = arrays.length;
int max = arrays[0];
for (int i = 1; i < length; i++) {
if (arrays[i] > max) {
max = arrays[i];
}
}
return max;
}
然后主要的排序代碼：
public static void radixSort(int[] arrays) {
int max = findMax(arrays, 0, arrays.length - 1);
//需要遍歷的次數(shù)由數(shù)組最大值的位數(shù)來(lái)決定
for (int i = 1; max / i > 0; i = i * 10) {
int[][] buckets = new int[arrays.length][10];
//獲取每一位數(shù)字(個(gè)、十、百、千位...分配到桶子里)
for (int j = 0; j < arrays.length; j++) {
int num = (arrays[j] / i) % 10;
//將其放入桶子里
buckets[j][num] = arrays[j];
}
//回收桶子里的元素
int k = 0;
//有10個(gè)桶子
for (int j = 0; j < 10; j++) {
//對(duì)每個(gè)桶子里的元素進(jìn)行回收
for (int l = 0; l < arrays.length; l++) {
//如果桶子里面有元素就回收(數(shù)據(jù)初始化會(huì)為0)
if (buckets[l][j] != 0) {
arrays[k++] = buckets[l][j];
}
}
}
}
}
外部排序：
一般來(lái)說(shuō)外排序分為兩個(gè)步驟：預(yù)處理和合并排序。首先，根據(jù)可用內(nèi)存的大小，將外存上含有n個(gè)紀(jì)錄的文件分成若干長(zhǎng)度為t的子文件（或段）；其次，利用內(nèi)部排序的方法，對(duì)每個(gè)子文件的t個(gè)紀(jì)錄進(jìn)行內(nèi)部排序。這些經(jīng)過(guò)排序的子文件（段）通常稱(chēng)為順串(run)，順串生成后即將其寫(xiě)入外存。這樣在外存上就得到了m個(gè)順串（m=[n/t]）。最后，對(duì)這些順串進(jìn)行歸并，使順串的長(zhǎng)度逐漸增大，直到所有的待排序的記錄成為一個(gè)順串為止。
結(jié)語(yǔ)：
最后附上百度上的圖：
文章哪里不對(duì)，幫忙指出，謝謝。。o(￣︶￣)o
參考：
《大話數(shù)據(jù)結(jié)構(gòu)》
《算法圖解》
《啊哈，算法》
