目錄

一、原理

二、代碼演示

三、代碼優化

---

一、原理

假設：

int arr[] = { 9,8,7,6,5,4,3,2,1,0 };

將 arr 內的元素進行升序排列，得到一個新的數組

int arr[] = { 0，1，2，3，4，5，6，7，8，9 };

這個過程中，我們可以使用冒泡排序。

?如上圖所示，冒泡排序便是數組元素之間進行倆倆交換，類似于之前比大小中的打擂臺，設立一個擂主進行打擂，完成條件進行交換便是打擂成功，直到最后抵達它應該所在的位置便是結束打擂。

此時開始設立第二個擂主進行打擂，而且新設立的擂主不能打上一任的擂主和之前的擂主，且上一任的擂主必須保持原地不動，而打一次通關，則需要看需要打敗的人數，以及之前的擂主和上一任擂主。

以此類推，得到最后的結果。

且最后，每一任擂主需要進行的打擂次數便是交換次數，有幾個擂主便是需要進行幾趟的冒泡排序。

最后我們便得到以下代碼。

二、代碼演示

int dio(int arr[], int sz)
{int i = 0; for (i = 0; i < sz; i++){//需要進行一趟冒泡排序int j = 0;for (j = 0; j < sz - 1 - i; j++)//之前的擂主不動，且不能和上之前的擂主進行決斗//且前幾任擂主和冒泡排序的趟數有關{if (arr[j] > arr[j + 1])//達成條件后進行交換{//經典的交換代碼int temp = arr[j + 1];arr[j + 1] = arr[j];arr[j] = temp;}}}
}
void print(int *arr, int sz)
{int i = 0;for (i = 0; i < sz; i++){printf("%d ",arr[i]);}
}
int main()
{int arr[] = {1,3,5,2,8,7,9,6,4,0,10, };int sz = sizeof(arr) / sizeof(arr[0]);dio(arr,sz);//調用函數進行冒泡排序print(arr, sz);//打印冒泡排序后的數組return 0;
}

三、代碼優化

以上的代碼有個缺點，那便是遇見了顯而易見的，只需要極少的交換次數便能夠完成的排序時，也需要進行多趟的冒泡排序，需要每一個元素都進行比較和排序，這導致效率極其的低下，所以我們在此多添加一個內容。

int arr[] = {9，1，2，3，4，5，6，7，8，10 };

那便是一個假設，若滿足了交換的內容，則假設失效，若沒有滿足，則假設成功。

int dio(int arr[], int sz)
{int i = 0; int flag = 1;//進行假設,假設有序for (i = 0; i < sz; i++){//需要進行一趟冒泡排序int j = 0;for (j = 0; j < sz - 1 - i; j++)//上一任的擂主不動，且不能和上一任擂主進行決斗{if (arr[j] > arr[j + 1])//達成條件后進行交換{//經典的交換代碼int temp = arr[j + 1];arr[j + 1] = arr[j];arr[j] = temp;flag = 0;//假設失敗}}if (flag == 1){break;}}
}
void print(int *arr, int sz)
{int i = 0;for (i = 0; i < sz; i++){printf("%d ",arr[i]);}
}
int main()
{int arr[] = {1,3,5,2,8,7,9,6,4,0,10, };int sz = sizeof(arr) / sizeof(arr[0]);dio(arr,sz);//調用函數進行冒泡排序print(arr, sz);//打印冒泡排序后的數組return 0;
}

?