語法是語言的特色,而算法卻是靈魂
算法不分語言
入門的算法要數排序算法
今天的算法講解將以c語言為例子將以下幾個排序算法
1. 桶排序
2. 插入排序
3. 冒泡排序
4. 快速排序
首先給大家介紹一個最簡單粗暴的排序算法
桶排序
桶排序要先知道要排序的數的范圍
然後要這麼多的桶去裝這些可能出現數的次數
//這裡的范圍是0~999
int b[1000];
這個數組就是用來裝出現次數的
然後輸入數字,然後這個相應的桶的次數就加1
輸出時遍歷全部桶,然後桶的數字是幾就輸出幾次這個數字
代碼如下
#include
int main(){
int num;
//弄一個大桶裝所有可能出現的數,用來記錄每個數字出現的次數,桶的個數是可能出現的最大值
int b[1000]={0}; int i,j; for(i=0;i<10;i++){ scanf("%d",&num); //該數字出現次數+1 b[num]++; } for(i=0;i<1000;i++){ //桶有裝有幾個數就輸出幾次 for(j=0;
這方法夠簡單夠粗暴吧
其實這方法還可以優化一下
我們雖然是知道范圍,但輸入的數的范圍可能要比給出的范圍少得多,這樣的話遍歷全部桶就很浪費時間了
所以我們可以找到輸入數字的最大值和最小值,只需遍歷最大值和最小值之間的桶就行了,因為其他桶都是0,不用輸出所以代碼就可以改為
#include
int main(){
int num;
//弄一個大桶裝所有可能出現的數,用來記錄每個數字出現的次數,桶的個數是可能出現的最大值
int b[1000]={0}; int max=0; int min=1000; int i,j; for(i=0;i<10;i++){ scanf("%d",&num); //該數字出現次數+1 b[num]++; / 到最大值,後面輸出可以節省時間,最大值後面的桶都是0,也可以再找最小值,最小值前面的桶都是0 if(num>max){ max=num; } if(num
桶的編碼對應的是它記錄的數字然後有人就問如果有負數怎麼辦負數的話,把全部桶平移一下就好,輸出時把桶的編碼再減去平移值
比如范圍是-10~9
可以開個數組int b[20];
輸入的話就是b[num+10]++
輸出的話printf(“%d “,i-10);
這個算法大概就是這樣了,雖然說是簡單,但是我們通常情況下是不知道確切的范圍的,如果以最大范圍去開辟桶就會很浪費空間然後接下來講第二種算法插入排序插入排序的基本思想是,從第二個數開始,插入到前面有序序列的位置
比如說3個數,分別是5,4,2
然後從第二個數開始
4比5小,應該插到5的前面
然後5後退一位
現在的序列編程4,5,2然後到第三個數2
2應該插到4前面
所以4和5都要後退一位
現在就變成2,4,5的有序序列了具體代碼是這樣#include
int main(){
int a[1000];
int b;
int i;
for(i=0;i<10;i++){
scanf("%d",&a[i]);
//還可以在輸入的時候就排序了
}
for(i=1;i<10;i++){
int temp=a[i];
int n=i-1;
//跟前面的比較,小的話就向前,並且該位向後移動一位
while(n>-1&&temp第二個for循環i=1就是從第二個數開始可能需要大家一點抽象思維去想象比如排隊
是按號排隊的
他遲到了
然後他就拿這號從最後一位一直向前問
後面的都比他大,終於找到一個比他小的
他不可能排他前面,所以只能排他後面
然後他就插隊進去了
他後面的人都被他擠後了一位接下來介紹另一種排序算法冒泡排序冒泡排序的思想是,每次把最小的數冒到左邊
就像氣泡一樣越接近水面的泡泡越大
繼續是以剛剛的數列5,4,2為例
從第一個數開始
5比4大,然後就交換
4比2大然後就交換
然後現在的序列是2,5,4
然後到第二個數開始
5比4大,交換位置
然後這個序列就排好了具體代碼如下#include
int main(){
int a[1000];
int i,j,temp;
for(i=0;i<10;i++){
scanf("%d",&a[i]);
}
for(i=0;i<9;i++){
//跟後面的所有數進行比較,大的就交換
for(j=i+1;j<10;j++){
//交換
if(a[i]>a[j]){
temp=a[i];
a[i]=a[j];
a[j]=temp;
}
}
}
for(i=0;i<10;i++){
printf("%d ",a[i]);
}
return 0;
} 這種排序方法是初學者必須掌握的一種排序方法最後講一種高級一點的算法快速排序掌握這種方法可以說是初學者的分水嶺這種排序方法包含了遞歸和分治的思想遞歸我們最熟悉的就是猴子吃桃最後一天剩一個,每天吃總數的一半,吃了五天,然後問你最開始有多少個桃子然後就是從最後一天開始算,一直算到第一天分治就是,講一個問題分開處理但分開處理是沒有影響的就比如掃地可以掃地分為掃客廳和掃房間快速排序的思想是從給一個數組,然後在數組中找一個基准值兩邊派一個士兵去幫我找數要從右邊的士兵開始右邊的士兵要找一個比基准值小的數找到後停下來等左邊的士兵左邊的士兵要找一個比基准值大的數找到後就停下來,交換這兩個數的位置交換後繼續找,直到他們相遇相遇時這個數一定比基准值小大家直到為啥嗎我們有一個很關鍵的一步從右邊開始右邊停下的位置一定是小於基准值的相遇後相遇的數和基准值交換,我們這裡取最左邊的數為基准值交換之後,基准值的左邊都是比基准值小的,基准值右邊都是比基准值大的然後就按相同的規則排基准值的左邊和右邊排序時不僅要傳入數組,還要傳入范圍一旦排到左邊界等於右邊了就不用排了,就可以return返回了代碼如下#include
int main(){
int a[1000];
int i;
for(i=0;i<10;i++){
scanf("%d",&a[i]);
}
quicksort(a,0,9);
for(i=0;i<10;i++){
printf("%d ",a[i]);
}
return 0;
}
void quicksort(int a[],int left,int right){
if(left>=right){
return;
}
int low=left;
int high=right;
//這個基准值可以隨便取,只要在left和right范圍內就好
int key=a[left];
while(low!=high){
//順序很重要,要先從右邊開始找
//因為最後交換時左邊的要都比基准小
//右邊大於基准值就跳過
while(low=key){
high--;
}
//左邊小於基准值就跳過
while(low如果大家理解了這種算法,對c語言的造詣就會深一層
這篇關於快速排序博客有配圖更加形象這裡講的都是從小到大的排序,大家可以思考一下用這幾種算法如何從大到小排序