C語言中的冒泡排序問題
冒泡排序的原理
冒泡排序的步驟
假設(shè)我們現(xiàn)在有一個無序數(shù)組 arr[] = { 2,9,1,3,7,6 }; 我們要用冒泡排序法讓其變得有序,到底該怎么做呢?我們先來看一下思路
在這一次(注意!是一次?。┟芭菖判蛑?,我們讓這個無序數(shù)組中最大的數(shù)9排到了最后,以此類推,我們總共需要進行多少次這樣的排序呢?對的,答案是5次。
好的,那么這是我們對冒泡排序外部的分析,那么一次冒泡排序在數(shù)組里面要進行多少次比較呢?
讓我們想一想,第一次我們冒泡排序?qū)⒆畲蟮臄?shù)9排到了最后,那么第二次還需要對9進行比較嗎?
所以數(shù)組內(nèi)部元素排序的比較是會隨著外部冒泡排序次數(shù)而改變的。所以我們應(yīng)該創(chuàng)建兩個變量,一個用來控制外部排序次數(shù),一個用來控制內(nèi)部比較次數(shù)。接下來就上代碼吧
冒泡排序代碼
在這里要注意的是對于i和j的限制條件,要清楚i和j分別代表啥,并且弄清楚排序次數(shù)和比較次數(shù)就沒有問題了呀
冒泡排序兩種不同循環(huán)方法
在數(shù)據(jù)結(jié)構(gòu)與算法這門課程中,排序算法至關(guān)重要。
冒泡排序就是其中之一,其代碼我們必須爛熟于心。
原理
從表頭向表尾循環(huán),
比較相鄰的兩個元素大小,若前元素大于后元素,則交換兩者位置。
然后繼續(xù)向下比較
如下表
大的數(shù)字會慢慢置入表尾,猶如冒泡一般,大泡更快速度向水面靠近,故稱之為冒泡排序
上圖所示
當(dāng)冒泡到第四趟以后就沒必要往下面繼續(xù)循環(huán)
不然會增加復(fù)雜度
我們可以增加一個標(biāo)志flag
每趟冒泡之前會將flag初始化為0
假如冒泡的過程中有元素的交換,就將flag賦值為1;
在每趟冒泡之后會有檢驗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; } } }
總結(jié)
以上為個人經(jīng)驗,希望能給大家一個參考,也希望大家多多支持腳本之家。
相關(guān)文章
C++ 設(shè)置和獲取當(dāng)前工作路徑的實現(xiàn)代碼
這篇文章主要介紹了C++ 設(shè)置和獲取當(dāng)前工作路徑的實現(xiàn)代碼,防止DLL加載不到配置和文件,需要的朋友可以參考下2017-09-09C語言數(shù)據(jù)結(jié)構(gòu)之單鏈表的實現(xiàn)
鏈表是一種物理存儲結(jié)構(gòu)上非連續(xù)、非順序的存儲結(jié)構(gòu),數(shù)據(jù)元素的邏輯順序是通過鏈表中的指針鏈接次序?qū)崿F(xiàn)的。本文將用C語言實現(xiàn)單鏈表,需要的可以參考一下2022-06-06