目錄
- 交換排序 一：冒泡排序
- 1、冒泡排序定義
- 2、名字由來以及注意點
- 3、演算法示例
- ① 排序之前：
- ② 排序程序：
- ③ 排序結果：
- ④代碼每一趟執行的程序
- 4、常見代碼實作，以及代碼的優化
- ①常見的代碼實作：
- ②代碼的優化：
- 5、演算法分析
- ①空間復雜度：
- ②時間復雜度：
- ③演算法穩定性：
交換排序 一：冒泡排序
交換排序的定義: 交換交換，換的是兩個元素的位置，根據序列中，兩個元素關鍵字的比較結果，對兩個元素在序列中的位置進行交換，
交換排序，最常見的就是冒泡排序和快速排序
1、冒泡排序定義
冒泡排序的基本思想就是：序列從前到后（一般都是從前到后）或者從后到前去兩兩比較相鄰元素的值，
如果逆序，就交換一下，一直這樣走下去，直到序列比較完，這就是第一趟冒泡，
下一趟冒泡的時候，前一趟已經確定了的最小的（或是最大的）元素就不用參加比較了，
如此重復，最多需要 N - 1 次就可以把所有的元素排序好
2、名字由來以及注意點
冒泡名字的由來：是大的元素，會在排序程序中通過交換“浮現”到序列頂端，程序就像水中水泡冒泡一樣，因此得名，
但是不能有誤區;
那就是序列升序的時候，用冒泡來比喻最形象
降序的時候，用沉底比喻更不錯
這個也不必糾結，結合代碼馬上就能夠理解了，
3、演算法示例
定義陣列如下：
int arr[] = {3,44,38,15,47,43};① 排序之前：
② 排序程序：
第一趟，從頭開始，依次比較兩個元素的大小，前面的元素 > 后面的，則交換兩個元素；
- 下一趟繼續上述的步驟，只是剛剛已經確認過的最后元素已經是最大了，就不用繼續參與比較了
- 后續趟數的比較同理，直到序列是有序的
③ 排序結果：
（最多）重復 N - 1次之后，就排序完成了
④代碼每一趟執行的程序
4、常見代碼實作，以及代碼的優化
①常見的代碼實作：
void Bubble_Sort(int *arr, int length)
{
if (arr == NULL || length <= 0)
{
return;
}
bool IsSwap = false;
for (int i = 0; i < length; i++)
{
for (int j = 0; j < length - 1 - i; j++)
{
if (arr[j] > arr[j + 1]) // 兩兩比較
{
int temp = arr[j + 1];
arr[j + 1] = arr[j];
arr[j] = temp;
}
}
printf("第%d步排序結果：", i + 1); // 輸出每步排序結果
for (int k = 0; k < length; k++)
{
printf("%5d", arr[k]);
}
printf("\n");
}
}②代碼的優化：
但是我們可以發現后續的步驟是已經就排好了的；
如果使用上述的普通方法，后續的步驟依舊是會有比較的
但是從結果的角度看，完全沒有必要呀~，雖然計算機很快，但是這依然是一種沒必要的浪費
思路：因此就可以從此處優化：增加flag標志位，根據有無資料交換，去決定是繼續冒泡還是結束冒泡
void Bubble_Sort(int *arr, int length)
{
if (arr == NULL || length <= 0)
{
return;
}
bool IsSwap = false;
for (int i = 0; i < length; i++)
{
IsSwap = false; //增加flag標志位，根據有無資料交換，去決定是繼續冒泡還是結束冒泡
for (int j = 0; j < length - 1 - i; j++)
{
if (arr[j] > arr[j + 1]) // 兩兩比較
{
int temp = arr[j + 1];
arr[j + 1] = arr[j];
arr[j] = temp;
IsSwap = true;
}
}
if (IsSwap == false)
{
break;
}
printf("第%d步排序結果：", i + 1); // 輸出每步排序結果
for (int k = 0; k < length; k++)
{
printf("%5d", arr[k]);
}
printf("\n");
}
}隨后，我們來看優化的結果：
到了第三步的時候，由于沒有發生資料的交換，所以就結束冒泡，直接回傳排序的結果了，并沒有繼續走剩下的四步
5、演算法分析
①空間復雜度：
O(1)；因為輔助空間是常數級別的
②時間復雜度：
最好的情況：初始的時候，序列就是正序的，所以時間復雜度是 O(n)
最壞的情況：初始的時候，序列是完全逆序的，所以時間復雜度是O(n^2)
平均時間復雜度：綜上，平均時間復雜度是O(n^2)
③演算法穩定性：
對于演算法的穩定性而言，我們先假設，在此時序列中有兩個相鄰的值為 13 的元素（其它重復元素同理，不是相鄰的話在冒泡的程序中也會有相鄰的狀態），根據判斷條件 i > j , 且 A[i] == A[j] ，在做冒泡排序的時候，13 和 另外一個13之間不會發生位置的交換；
所以，冒泡排序是一種穩定的排序演算法，
文中代碼在Github可下載： https://github.com/FYY-YOUNG
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/242811.html
標籤：其他
上一篇：jsp,taglib匯入http://www.springframework.org/tags/form錯誤,無法在web.xml或使用此應用程式部署的jar檔案中決議絕對uri