在我們生活中排序是經(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ù)組就可以搞定呼猪。
思路：首先我們申請(qǐng)一個(gè)大小為11的數(shù)組int[]arr = new int[11],好了，現(xiàn)在我們已經(jīng)有11個(gè)變量砸琅，編號(hào)一次是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分雳灵，我們就將對(duì)應(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很大是不是要申請(qǐng)的內(nèi)存空間很大拢蛋。簡單的桶排序時(shí)間復(fù)雜度O(m+n)
