目錄

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)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。