冒泡排序

1.原理

左邊大于右邊交換一趟排下來最大的交換到右邊來(接下來所以文章用升序舉例)

• 從左到右，相鄰元素進(jìn)行比較。

• 每次比較一輪，就會找到序列中最大的一個（最小的一個——降序）。這個數(shù)就會從序列的最右邊冒出來。

• 以從小到大排序為例，第一輪比較后，所有數(shù)中最大的那個數(shù)就會浮到最右邊；

• 第二輪比較后，所有數(shù)中第二大的那個數(shù)就會浮到倒數(shù)第二個位置……就這樣一輪一輪地比較，最后實現(xiàn)從小到大排序。

2.圖解

3.代碼

代碼如下：

//普通版本
void Bubble_sort1(int* arr, int size)
{for (int i = 0; i < size; i++){//開始:i=0      j<size-1(j+1才size-1，符合下標(biāo))//size-1-i是因為每一趟就會少一個數(shù)比較for (int j = 0; j < size - i - 1; j++)	//{if (arr[j] > arr[j + 1])			//前面大于后面，把大的交換到右邊{int tem = arr[j];arr[j] = arr[j + 1];arr[j + 1] = tem;}}}
}

4.優(yōu)化

• 設(shè)置flag，如果有序了，就不用往下循環(huán)了，提前退出

//優(yōu)化版本
void Bubble_sort2(int* arr, int size)
{for (int i = 0; i < size; i++){int flag = 0;							//默認(rèn)有序for (int j = 0; j < size - i - 1; j++)	size-1-i是因為每一趟就會少一個數(shù)比較{if (arr[j] > arr[j + 1])			//前面大于后面，把大的交換到右邊{int tem = arr[j];arr[j] = arr[j + 1];arr[j + 1] = tem;//發(fā)生交換，說明無序flag = 1;}}//如果前面都沒有發(fā)生交換，說明已經(jīng)有序了if (flag == 0){break;			//不用繼續(xù)了，已經(jīng)有序，提前退出}}
}

我給這個案例測試：
1 2 3 4 5 6 7 9 8 就9和8沒有升序

普通版本：

優(yōu)化版本：

顯然速度稍微得到提升！

5.時空復(fù)雜度