寫(xiě)在前面
背景
小哼的班上只有5個(gè)同學(xué)照激，這5個(gè)同學(xué)分別考了5分鲫惶、3分、5分实抡、2分欠母、8分(最高分10分)，接下來(lái)將分?jǐn)?shù)按照從大到小排序吆寨，排序后的結(jié)果是：8 5 5 3 2 赏淌，寫(xiě)一段程序，讓計(jì)算機(jī)讀入5個(gè)數(shù)然后將這5個(gè)數(shù)從大到小輸出啄清。
直接上代碼
#include <stdio.h>
int main(int argc, const char * argv[]) {
int a[11];
//設(shè)置a[t]的默認(rèn)值為0
for (int i=0; i<11; i++) {
a[i] = 0;
}
int t;
for (int i=0; i<5; i++) {
scanf("%d", &t);
a[t]++; //設(shè)置考t分的人數(shù)
}
for (int i=10; i>=0; i--) {
for (int j=0; j<a[i]; j++) {
printf("%d", i);
}
}
printf("\n");
return 0;
}
解讀
最高分是10分六水，所以創(chuàng)建了11個(gè)元素的數(shù)組，其中a[t]=n; 表示考t分的有n人辣卒。
默認(rèn)情況下a[t]=0;
根據(jù)輸入的t值掷贾，使a[t]自增1;
然后通過(guò)對(duì)a[]的倒序遍歷，如果a[t]為0荣茫，則不輸出; 如果a[t]=n>0,則輸入n次t;
變形
輸入n個(gè)0~1000之間的整數(shù)想帅，將它們從大到小排序。
#include <stdio.h>
int main(int argc, const char * argv[]) {
// insert code here...
int n;
scanf("%d", &n); //n表示要排序的數(shù)字個(gè)數(shù)
int a[1001];
//(1)
for (int i=0; i<1001; i++) {
a[i] = 0;
}
int t;
//(2)
for (int i=0; i<n; i++) {
scanf("%d", &t);
a[t] ++;
}
//(3)
for (int i=1000; i>=0; i--) {
for (int j=0; j<a[i]; j++) {
printf("%d ", i);
}
}
printf("\n");
return 0;
}
時(shí)間復(fù)雜度
代碼中標(biāo)記(1)處啡莉，一共循環(huán)了M次港准，M為桶的個(gè)數(shù)。標(biāo)記(2)處一共循環(huán)了N次咧欣，N為待排序數(shù)的個(gè)數(shù)浅缸，標(biāo)記(3)處共循環(huán)了(M+N)次，所以總的時(shí)間復(fù)雜度是O(M+N+M+N)=O(2*(M+N))魄咕，忽略常數(shù)衩椒，最終桶排序的時(shí)間復(fù)雜度是O(M+N).
總結(jié)與反思
這是一個(gè)非常快的排序算法，但它不是真正的桶排序算法毛萌，真正的桶排序算法之后會(huì)講梢什。這篇講的是簡(jiǎn)化版的桶排序算法，其本質(zhì)還不能算是一個(gè)真正意義上的排序算法朝聋∥宋纾看一個(gè)例子: 5個(gè)人的名字和分?jǐn)?shù)：huhu 5分，哈哈 3分冀痕， xixi 5分荔睹，hengheng 5分， river 8分言蛇。請(qǐng)按照分?jǐn)?shù)從高到低僻他，輸入他們的名字，如果用上面的簡(jiǎn)化版桶排序算法僅僅是把分?jǐn)?shù)進(jìn)行了排序腊尚，最終輸入的僅僅是分?jǐn)?shù)吨拗，但沒(méi)有對(duì)名字進(jìn)行排序。
期待下一節(jié)：冒泡排序婿斥。
