C語言中的冒泡排序問題

更新時(shí)間：2022年12月27日 09:01:24 作者：我的博爾赫斯

這篇文章主要介紹了C語言中的冒泡排序問題，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教

冒泡排序的原理

冒泡排序的步驟

假設(shè)我們現(xiàn)在有一個(gè)無序數(shù)組 arr[] = { 2,9,1,3,7,6 }; 我們要用冒泡排序法讓其變得有序，到底該怎么做呢？我們先來看一下思路

在這一次（注意！是一次！）冒泡排序中，我們讓這個(gè)無序數(shù)組中最大的數(shù)9排到了最后，以此類推，我們總共需要進(jìn)行多少次這樣的排序呢？對(duì)的，答案是5次。

好的，那么這是我們對(duì)冒泡排序外部的分析，那么一次冒泡排序在數(shù)組里面要進(jìn)行多少次比較呢？

讓我們想一想，第一次我們冒泡排序?qū)⒆畲蟮臄?shù)9排到了最后，那么第二次還需要對(duì)9進(jìn)行比較嗎？

所以數(shù)組內(nèi)部元素排序的比較是會(huì)隨著外部冒泡排序次數(shù)而改變的。所以我們應(yīng)該創(chuàng)建兩個(gè)變量，一個(gè)用來控制外部排序次數(shù)，一個(gè)用來控制內(nèi)部比較次數(shù)。接下來就上代碼吧

冒泡排序代碼

在這里要注意的是對(duì)于i和j的限制條件，要清楚i和j分別代表啥，并且弄清楚排序次數(shù)和比較次數(shù)就沒有問題了呀

冒泡排序兩種不同循環(huán)方法

在數(shù)據(jù)結(jié)構(gòu)與算法這門課程中，排序算法至關(guān)重要。

冒泡排序就是其中之一，其代碼我們必須爛熟于心。

原理

從表頭向表尾循環(huán)，

比較相鄰的兩個(gè)元素大小，若前元素大于后元素，則交換兩者位置。

然后繼續(xù)向下比較

如下表

大的數(shù)字會(huì)慢慢置入表尾，猶如冒泡一般，大泡更快速度向水面靠近，故稱之為冒泡排序

上圖所示

當(dāng)冒泡到第四趟以后就沒必要往下面繼續(xù)循環(huán)

不然會(huì)增加復(fù)雜度

我們可以增加一個(gè)標(biāo)志flag

每趟冒泡之前會(huì)將flag初始化為0

假如冒泡的過程中有元素的交換，就將flag賦值為1；

在每趟冒泡之后會(huì)有檢驗(yàn)flag是否為0

如果為0，代表沒有元素交換，break；

//第一種循環(huán)方法
void BubbleSort(ElementType A[],int N){    
 
for(int p=N-1;p>0;p--){
        int flag=0;    
        for(int i=1;i<=p;i++){
            if(A[i-1]>A[i]){    //如果前面元素大于后面元素就交換 
               int temp=A[i-1];    //swap(A[i-1],A[i]);
                A[i-1]=A[i];
                A[i]=temp;
                flag=1;
            }
        }
        if(flag==0){        //一輪冒泡后并沒有發(fā)生交換則說明數(shù)組已經(jīng)有序
            break;          //這樣做可以減少循環(huán)次數(shù)
        }
    }
}
//第二種循環(huán)方法
void BubbleSort(ElementType A[],int N){
    
    for(int i=0;i<N;i++){
        int flag=0;
        for(int j=0;j<N-i-1;j++){
            if(A[i-1]>A[i]){    //如果前面元素大于后面元素就交換
                int temp=A[i-1];    //swap(A[i-1],A[i]);
                A[i-1]=A[i];
                A[i]=temp;
                flag=1;
            }
        }
        if(flag==0){
            break;
        }
    }
}