c语言排序算法实际案例,[C语言] 部分经典排序算法详解(有图解)
目錄
1.內(nèi)容概括
2.主要算法
3.技術(shù)的具體應(yīng)用
4.算法實際應(yīng)用
5.總結(jié)
0.前言
在上一篇文章《[C語言] 數(shù)組的實際應(yīng)用三則》中我們提到了數(shù)組的一些基礎(chǔ)知識,并通過三個實際例子來加深對數(shù)組的理解
本文則重點講解數(shù)組與排序算法的不解之緣
1.內(nèi)容概括
講解數(shù)組的幾種常見的排序方法
2.主要算法
本文中主要講解三種排序方法:冒泡排序、選擇排序、插入排序
我們先假設(shè)存在一個數(shù)組a[4],其元素分別為a2,a4,a3,a1
其中a1
2.1冒泡排序
算法思路圖解:
冒泡排序.jpg
算法文字描述:
①從第一個元素開始,將第一個元素與下一個元素進行比較,如果前一個元素比下一個元素更大,則互換這而位置
②然后開始比較第二個和第三個的大小,判斷是否需要互換,然后是第三個與第四個
③重復(fù)上述操作可以將最大(當(dāng)然也可以是最小)的數(shù)字放在數(shù)組最后
④然后逐步將第二大,第三大的數(shù)字依次沉底
⑤反復(fù)上述過程,直至排序完成
2.2選擇排序
算法思路圖解:
選擇排序.jpg
算法文字描述:
①從第一個元素開始,將第一個元素賦值給min,然后跟后面的元素一次比較
②如果min比后面的某個元素大,則互換第一個元素與比min小的這個元素,然后將把比原來的min小的元素賦值給min
③重復(fù)上述操作不斷向后比較,直至比對完最后一個元素
④當(dāng)比對完最后一個元素后就會發(fā)現(xiàn)第一位的元素已經(jīng)被替換為數(shù)組中最小的那個元素
⑤下一次循環(huán)從第二位開始,循環(huán)結(jié)束后,第二位則為第二小的元素
⑥重復(fù)上述過程即可
2.3插入排序
算法思路圖解:
插入排序.jpg
算法文字描述:
①從第一個元素開始,將第一個元素與下一個元素相比較
②如果第一個元素大于第二個,則互換二者位置
③當(dāng)發(fā)生互換位置后,關(guān)注那個被往前(往下標(biāo)較小的方向)調(diào)的元素,將這個元素與前一個元素相比(如果有前一個元素的話)
④如果這個往前調(diào)的元素比前一個元素更小,則繼續(xù)往前換
⑤重復(fù)④過程,直至前一個元素更小
⑥視線回到①中往后調(diào)的那個元素,重新向后比較
⑦重復(fù)上述過程即可
3.主要算法具體實現(xiàn)
3.1冒泡排序
for (int j = 3; j > 0; j--) {
for (int i = 0; i < j; i++) {
if (p[i] > p[i + 1])
{
temp = p[i];
p[i] = p[i + 1];
p[i + 1] = temp;
}
}
}
或者也可以是
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3 - i; j++) {
if (p[i] > p[i + 1])
{
temp = p[i];
p[i] = p[i + 1];
p[i + 1] = temp;
}
}
}
算法特點:
整體比較簡單易懂,使用兩個for循環(huán)嵌套
兩層for循環(huán)分別負(fù)責(zé)不同的部分,具體情況視寫法而定
由于要互換兩個變量的值,一般需要一個中間變量(當(dāng)然如果是變量存的是數(shù)字,也可以靠數(shù)學(xué)方法解決)
a = a+b;
b = a-b;
a = a-b;
這樣也能互換二者的值
3.2選擇排序
for (int i = 0; i < 3; i++) {
min = p[i];
k = i;//k代表取出來的那個數(shù)字的位置
int j = i + 1;
for (; j < 4; j++) {
if (min > p[j]) {
p[k] = p[j];//p[j]表示正在用阿里對比的那個
p[j] = min;//相當(dāng)于調(diào)換位置
min = p[k];//min得換為新的最小的
}
}
}
算法特點:
其實每次要做的事情就是比較二者大小并判斷是否需要互換,只不過該算法中專門設(shè)置了一個變量min,用min去進行比較
每次循環(huán)結(jié)束,都能獲得一個次小值
if語句中確實地將數(shù)組中兩個元素互換,然后改變了min的值,事實上這樣僅為了方便理解,其實沒有必要
其實只需要將min的值改變,然后在將原來min的值(數(shù)組里還放著沒動)賦給比min小的那個元素的位置即可
3.3插入排序
int temp = 0;
int total = 3;
for (int i = 0; i < total; i++) {
if (p[i] > p[i + 1]) {
//后面的更小則換位置
temp = p[i];
p[i] = p[i + 1];
p[i + 1] = temp;
int k = i;
bool flag = true;//用來判斷需不需要繼續(xù)往前換
//換完位置后繼續(xù)判斷
while (k > 0 && flag ) {
if (p[k] < p[k - 1]) {
temp = p[k];
p[k] = p[k -1];
p[k - 1] = temp;
k--;
}
else {
//不用繼續(xù)往前換,退出循環(huán)
flag = false;
}
}
}
}
算法特點:
其實插入排序的思路和冒泡排序很相似,只不過每次互換后,往前調(diào)的元素還需要繼續(xù)往前比較
簡而言之,就是確保往前調(diào)的元素能直接找到正確的位置
4.算法實際應(yīng)用
這里的應(yīng)用例子就是《數(shù)組的實際應(yīng)用三則》中的猜數(shù)字游戲
上文中提到的該游戲的正確答案是亂序,而為了降低難度,我們現(xiàn)在將其改為順序排列
改為順序排列的方式就是使用上文提到的三種排序方法
int num = 0;
for (int i = 0; i < 4; i++) {
num = rand() % 10;
//printf("%d", num);
//保證四個數(shù)字不重復(fù)
for (int j = 0; j < i; ) {
if (num == p[j]) {
num = rand() % 10;
j = 0;
}
else {
j++;
}
}
p[i] = num;
}
//上面為產(chǎn)生4個隨機數(shù),依次放入數(shù)組中,下面為是否需要排序
int temp = 0;
printf("請選擇難度:(低難度1,高難度2)");
scanf_s("%d", &temp);
//如果選擇低難度,則采用冒泡排序按順序排好
if (temp == 1) {
//BubbleSort(p);//冒泡排序
SelectionSort(p);//選擇排序
//InsertioSort(p);//插入排序
}
這里的p實際是一個指針,如果不是很懂指針的同學(xué),可以暫時將這個p當(dāng)做一個數(shù)組的名字即可
實際程序運行的時候,就可以通過輸入1或2,來判斷是否運行排序程序
另外,除了將數(shù)字放入數(shù)組成功后再進行排序,還可以在插入的時候就進行排序:
for (int i = 0; i < 4; i++) {
num = rand() % 10;
numArray[i] = num;
if (i == 0) {
//如果是第一個,不比較直接放入
a[i] = num;
total++;
}
else {
//如果不是第一個,得開始比較
int site = total - 1;//從最后一個開始往前比較(total為總數(shù),減1為最后一位)
while (site >= 0) {
if (a[site] > num) {
//說明當(dāng)前的最后一個元素必然得往后移
a[site + 1] = a[site];
}
else {
//a[site] <= num
//放在這個元素的后面
a[site + 1] = num;
total++;
break;
}
if (site == 0) {
//如果site指向第一個元素,則沒法再比較了
a[site] = num;
total++;
break;
}
site--;
}
}
}
主要代碼思想:
①第一個元素直接放入元素第一個位置
②從第二個元素開始,每個元素插入前都要從后往前,與數(shù)組已經(jīng)存在的元素逐個進行大小比較
③如果待插入元素小于已存在元素,已經(jīng)存在元素就要向后挪(就是賦值到后面一個的內(nèi)存空間)
④直至遇到一個小于待插入元素的元素,則待插入元素放在該元素后面
⑤重復(fù)②-④步驟,直至插入完成
注意:
強調(diào)從后往前比較的原因在于,從后往前,要做的是將待插入元素和已存在元素依次比較,如果需要向后挪動的話,就立即挪動
如果從前往后比較,其實道理也一樣,但問題在于,找出可以插入的位置后,需要將后面所有的已存在元素挪動,為了完成這個動作需要專門寫一個較為復(fù)雜的f循環(huán),總體結(jié)構(gòu)不一定好看
當(dāng)然以上結(jié)論為鄙人的個人看法,事實未必一定如此,讀者有興趣的話,可以自行進行嘗試和比較
5.總結(jié)
(1)本文主要解讀了三種(加上最后一種實際上有四種)與數(shù)組有關(guān)的排序方法,由于動圖不容易制作,因此選擇圖解+文字說明的方式,讀者應(yīng)該也能比較清晰地了解相應(yīng)的排序方法的理論過程
(2)將排序算法轉(zhuǎn)化的這個過程,其實更重要的是理解排序算法是如何運作的,然后就是根據(jù)自己對于算法、代碼的理解進行編寫即可,不需要死記硬背(死記硬背毫無用處)
(3)下一篇文章應(yīng)該會開始講解指針的相關(guān)內(nèi)容,指針與數(shù)組也有說不清道不明的關(guān)系,本文也算是為之后的內(nèi)容鋪平道路而做的準(zhǔn)備吧
《新程序員》:云原生和全面數(shù)字化實踐50位技術(shù)專家共同創(chuàng)作,文字、視頻、音頻交互閱讀總結(jié)
以上是生活随笔為你收集整理的c语言排序算法实际案例,[C语言] 部分经典排序算法详解(有图解)的全部內(nèi)容,希望文章能夠幫你解決所遇到的問題。
- 上一篇: c语言程序设计橙皮,橙皮_中药词典C_中
- 下一篇: c语言cin n1 n2,牛客等级之题N