在我們生活中排序是經(jīng)常出現(xiàn)的，比如我們網(wǎng)上買東西的時(shí)候需要按照價(jià)格排序，創(chuàng)建的數(shù)據(jù)需要按照創(chuàng)建的時(shí)間排序等等，可以說排序是無處不在的。
舉一個(gè)簡單的栗子：比如一個(gè)分?jǐn)?shù)數(shù)組為[5,3,5,2,8]，滿分是10分，接下來我們按照從大到小排序，排序后的結(jié)果是[8,5,5,3,2].
提示：首先我們借助一個(gè)一維數(shù)組就可以搞定。
思路：首先我們申請一個(gè)大小為11的數(shù)組int[]arr = new int[11],好了，現(xiàn)在我們已經(jīng)有11個(gè)變量，編號一次是arr[0]-arr[10];你可以初始化為這十個(gè)變量值為0，在這里我們用的是java，java初始化的時(shí)候默認(rèn)是0.初始化為0的含義是表示這些分?jǐn)?shù)還沒有人得過。比如arr[0]=0表示沒有人得過0分；arr[1]=0表示沒有人得過1分；arr[10]=0表示沒有得過10分。
下面開始處理每一個(gè)人的分?jǐn)?shù)，第一個(gè)是5分，我們就將對應(yīng)的arr[5]的值在原來的基礎(chǔ)上增加1.即arr[5]=1。表示5分?jǐn)?shù)出現(xiàn)過一次。同理所有的數(shù)據(jù)一次這樣處理。
java代碼實(shí)現(xiàn)如下：
public class BubleSort {
public static void main(String[] args) {
int [] arr = {5,3,5,2,8};
int max = 10;
sortASC(arr,max);
sortDESC(arr,max);
}
//從小到大排序
private static void sortASC(int[] arr,int max) {
int [] help = new int[max+1];
for (int i=0;i<arr.length;i++) {
int num = arr[i];
help[num]+=1;
}
//循環(huán)遍歷help
for (int i=0;i<help.length;i++) {
int num = help[i];
for (int t=1;t<=num;t++) {
if (num !=0) {
System.out.print(i+" ");
}
}
}
System.out.println();
}
//從小到大排序
private static void sortDESC(int[] arr,int max) {
int [] help = new int[max+1];
for (int i=0;i<arr.length;i++) {
int num = arr[i];
help[num]+=1;
}
//循環(huán)遍歷help
for (int i = help.length-1;i>=0;i--) {
int num = help[i];
for (int t=1;t<=num;t++) {
if (num !=0) {
System.out.print(i+" ");
}
}
}
System.out.println();
}
}
這種排序的方法我們暫且叫做桶排序，其實(shí)真正的桶排序比這個(gè)要復(fù)雜，這個(gè)只是一個(gè)簡單栗子而已，使用的范圍也不大，因?yàn)檫@個(gè)排序太浪費(fèi)空間了，如果我的max很大是不是要申請的內(nèi)存空間很大。簡單的桶排序時(shí)間復(fù)雜度O(m+n)
