綜述
冒泡排序是一種簡單的排序算法.它重復(fù)地走訪過要排序的數(shù)列,一次比較兩個元素,如果它們的順序錯誤就把它們交換過來.
走訪數(shù)列的工作是重復(fù)地進(jìn)行直到?jīng)]有再需要交換,也就是說該數(shù)列已經(jīng)排序完成.
這個算法的名字由來是因為越小的元素會經(jīng)由交換慢慢“浮”到數(shù)列的頂端.
算法描述
1.比較相鄰的元素.如果前一個比后二個大,就交換它們兩個;
2.對每一對相鄰元素作同樣的工作,從開始第一對到結(jié)尾的最后一對,這樣在最后的元素應(yīng)該會是最大的數(shù);
3.針對所有的元素重復(fù)以上的步驟,除了最后一個;
4.持續(xù)每次對越來越少的元素重復(fù)上面的步驟,直到?jīng)]有任何一對數(shù)字需要比較.
示意圖
性質(zhì)
排序類別:交換排序
是否是穩(wěn)定排序:穩(wěn)定
是否是原地排序:是
時間復(fù)雜度:O(N^2)
空間復(fù)雜度:O(1)
要點
冒泡排序是一種交換排序.
交換排序:兩兩比較待排序的關(guān)鍵字,并交換不滿足次序要求的那對數(shù),直到整個表都滿足次序要求為止.
算法思想
它重復(fù)地走訪過要排序的數(shù)列,一次比較兩個元素,如果他們的順序錯誤就把他們交換過來.走訪數(shù)列的工作是重復(fù)地進(jìn)行直到?jīng)]有再需要交換,也就是說該數(shù)列已經(jīng)排序完成.
這個算法的名字由來是因為越小的元素會經(jīng)由交換慢慢“浮”到數(shù)列的頂端,故名冒泡排序.
假設(shè)有一個大小為 N 的無序序列.冒泡排序就是要每趟排序過程中通過兩兩比較,找到第 i 個小(大)的元素,將其往上排.
要將以上流程轉(zhuǎn)化為代碼,我們需要像機器一樣去思考,不然編譯器可看不懂.
假設(shè)要對一個大小為 N 的無序序列進(jìn)行升序排序(即從小到大).
(1)每趟排序過程中需要通過比較找到第 i 個小的元素.
所以,我們需要一個外部循環(huán),從數(shù)組首端(下標(biāo) 0)開始,一直掃描到倒數(shù)第二個元素(即下標(biāo) N - 2),剩下最后一個元素,必然為最大.
(2)假設(shè)是第 i 趟排序,可知,前 i-1 個元素已經(jīng)有序.現(xiàn)在要找第 i 個元素,只需從數(shù)組末端開始,掃描到第 i 個元素,將它們兩兩比較即可.
所以,需要一個內(nèi)部循環(huán),從數(shù)組末端開始(下標(biāo) N - 1),掃描到(下標(biāo) i + 1).
時間復(fù)雜度分析
1.若文件的初始狀態(tài)是正序的,一趟掃描即可完成排序.所需的關(guān)鍵字比較次數(shù)C和記錄移動次數(shù)M均達(dá)到最小值:Cmin=N-1, Mmin=0.所以,冒泡排序最好時間復(fù)雜度為O(N).
2.若初始文件是反序的,需要進(jìn)行 N -1 趟排序.每趟排序要進(jìn)行(N-i)次關(guān)鍵字的比較(1 ≤ i ≤ N - 1),且每次比較都必須移動記錄三次來達(dá)到交換記錄位置.
在這種情況下,比較和移動次數(shù)均達(dá)到最大值:
Cmax = N(N-1)/2 = O(N^2)
Mmax = 3N(N-1)/2 = O(N^2)
冒泡排序的最壞時間復(fù)雜度為O(N^2).
因此,冒泡排序的平均時間復(fù)雜度為O(N^2).
總結(jié)起來,其實就是一句話:當(dāng)數(shù)據(jù)越接近正序時,冒泡排序性能越好.
穩(wěn)定性分析
冒泡排序就是把小的元素往前調(diào)或者把大的元素往后調(diào).比較是相鄰的兩個元素比較,交換也發(fā)生在這兩個元素之間.
所以相同元素的前后順序并沒有改變,所以冒泡排序是一種穩(wěn)定排序算法.
優(yōu)化方式
優(yōu)化一
假設(shè)我們現(xiàn)在排序ar[]={1,2,3,4,5,6,7,8,10,9}這組數(shù)據(jù),按照上面的排序方式,第一趟排序后將10和9交換已經(jīng)有序,接下來的8趟排序就是多余的,什么也沒做.所以我們可以在交換的地方加一個標(biāo)記,如果那一趟排序沒有交換元素,說明這組數(shù)據(jù)已經(jīng)有序,不用再繼續(xù)下去.
優(yōu)化二
優(yōu)化一僅僅適用于連片有序而整體無序的數(shù)據(jù)(例如:1, 2,3,4,7,6,5).但是對于前面大部分是無序而后邊小半部分有序的數(shù)據(jù)(1,2,5,7,4,3,6,8,9,10)排序效率也不可觀,對于種類型數(shù)據(jù),我們可以繼續(xù)優(yōu)化:即我們可以記下最后一次交換的位置,后邊沒有交換,必然是有序的,然后下一次排序從第一個比較到上次記錄的位置結(jié)束即可.
優(yōu)化三
優(yōu)化二的效率有很大的提升,還有一種優(yōu)化方法可以繼續(xù)提高效率.大致思想就是一次排序可以確定兩個值,正向掃描找到最大值交換到最后,反向掃描找到最小值交換到最前面.
例如:排序數(shù)據(jù)1,2,3,4,5,6,0
Python實現(xiàn)及優(yōu)化
def bubblesort1(dest_list=[]):
if len(dest_list) <= 1:
return dest_list
for i in range(len(dest_list) - 1):
print('第{}趟排序為:'.format(str(i + 1)))
for j in range(len(dest_list) - 1 - i):
print('第{}次排序為:'.format(str(j + 1)), dest_list)
if dest_list[j] > dest_list[j + 1]:
dest_list[j], dest_list[j + 1] = dest_list[j + 1], dest_list[j]
return dest_list
dest = [5, 3, 4, 6, 2, 1, 7]
result = bubblesort1(dest)
print('最后的結(jié)果是:', result)
'''
第1趟排序為:
第1次排序為: [5, 3, 4, 6, 2, 1, 7]
第2次排序為: [3, 5, 4, 6, 2, 1, 7]
第3次排序為: [3, 4, 5, 6, 2, 1, 7]
第4次排序為: [3, 4, 5, 6, 2, 1, 7]
第5次排序為: [3, 4, 5, 2, 6, 1, 7]
第6次排序為: [3, 4, 5, 2, 1, 6, 7]
第2趟排序為:
第1次排序為: [3, 4, 5, 2, 1, 6, 7]
第2次排序為: [3, 4, 5, 2, 1, 6, 7]
第3次排序為: [3, 4, 5, 2, 1, 6, 7]
第4次排序為: [3, 4, 2, 5, 1, 6, 7]
第5次排序為: [3, 4, 2, 1, 5, 6, 7]
第3趟排序為:
第1次排序為: [3, 4, 2, 1, 5, 6, 7]
第2次排序為: [3, 4, 2, 1, 5, 6, 7]
第3次排序為: [3, 2, 4, 1, 5, 6, 7]
第4次排序為: [3, 2, 1, 4, 5, 6, 7]
第4趟排序為:
第1次排序為: [3, 2, 1, 4, 5, 6, 7]
第2次排序為: [2, 3, 1, 4, 5, 6, 7]
第3次排序為: [2, 1, 3, 4, 5, 6, 7]
第5趟排序為:
第1次排序為: [2, 1, 3, 4, 5, 6, 7]
第2次排序為: [1, 2, 3, 4, 5, 6, 7]
第6趟排序為:
第1次排序為: [1, 2, 3, 4, 5, 6, 7]
最后的結(jié)果是: [1, 2, 3, 4, 5, 6, 7]
'''
"""
優(yōu)化方式一
對冒泡排序常見的改進(jìn)方法是加入標(biāo)志性變量exchange,用于標(biāo)志某一趟排序過程中是否有數(shù)據(jù)交換。
如果進(jìn)行某一趟排序時并沒有進(jìn)行數(shù)據(jù)交換,則說明所有數(shù)據(jù)已經(jīng)有序,可立即結(jié)束排序,避免不必要的比較過程。
"""
def bubblesort2(dest_list=[]):
if len(dest_list) <= 1:
return dest_list
for i in range(len(dest_list)):
exchange = False
print('第{}趟排序:'.format(str(i + 1)))
for j in range(len(dest_list) - 1 - i):
print('第{}次排序為:'.format(str(j + 1)), dest_list)
if dest_list[j] > dest_list[j + 1]:
dest_list[j], dest_list[j + 1] = dest_list[j + 1], dest_list[j]
exchange = True
if not exchange:
break
return dest_list
dest = [2, 1, 4, 3, 5, 6, 7]
result = bubblesort2(dest)
print('最后的結(jié)果是:', result)
'''
第1趟排序:
第1次排序為: [2, 1, 4, 3, 5, 6, 7]
第2次排序為: [1, 2, 4, 3, 5, 6, 7]
第3次排序為: [1, 2, 4, 3, 5, 6, 7]
第4次排序為: [1, 2, 3, 4, 5, 6, 7]
第5次排序為: [1, 2, 3, 4, 5, 6, 7]
第6次排序為: [1, 2, 3, 4, 5, 6, 7]
第2趟排序:
第1次排序為: [1, 2, 3, 4, 5, 6, 7]
第2次排序為: [1, 2, 3, 4, 5, 6, 7]
第3次排序為: [1, 2, 3, 4, 5, 6, 7]
第4次排序為: [1, 2, 3, 4, 5, 6, 7]
第5次排序為: [1, 2, 3, 4, 5, 6, 7]
最后的結(jié)果是: [1, 2, 3, 4, 5, 6, 7]
'''
"""
優(yōu)化方式二
優(yōu)化一僅僅適用于連片有序而整體無序的數(shù)據(jù)(例如：1, 2,3 ,4 ,7,6,5)。
但是對于前面大部分是無序而后邊小半部分有序的數(shù)據(jù)(1,2,5,7,4,3,6,8,9,10)排序效率也不可觀,對于這種類型數(shù)據(jù),我們可以繼續(xù)優(yōu)化。
我們可以記下最后一次交換的位置,后邊沒有交換,必然是有序的,然后下一次排序從第一個比較到上次記錄的位置結(jié)束即可。
"""
def bubblesort3(dest_list=[]):
if len(dest_list) <= 1:
return dest_list
k = len(dest_list) - 1 # 確定比較次數(shù)
for i in range(len(dest_list)):
exchange = False
pos = 0 # 用來記錄最后一次交換的位置
print('第{}趟排序:'.format(str(i + 1)))
for j in range(k):
print('第{}次排序為:'.format(str(j + 1)), dest_list)
if dest_list[j] > dest_list[j + 1]:
dest_list[j], dest_list[j + 1] = dest_list[j + 1], dest_list[j]
exchange = True
pos = j # 交換元素,記錄最后一次交換的位置
if not exchange: # 如果沒有交換過元素,則已經(jīng)有序
break
k = pos # 下一次比較到記錄位置即可
return dest_list
dest = [2, 1, 4, 3, 5, 6, 7]
result = bubblesort3(dest)
print('最后的結(jié)果是:', result)
'''
第1趟排序:
第1次排序為: [2, 1, 4, 3, 5, 6, 7]
第2次排序為: [1, 2, 4, 3, 5, 6, 7]
第3次排序為: [1, 2, 4, 3, 5, 6, 7]
第4次排序為: [1, 2, 3, 4, 5, 6, 7]
第5次排序為: [1, 2, 3, 4, 5, 6, 7]
第6次排序為: [1, 2, 3, 4, 5, 6, 7]
第2趟排序:
第1次排序為: [1, 2, 3, 4, 5, 6, 7]
第2次排序為: [1, 2, 3, 4, 5, 6, 7]
最后的結(jié)果是: [1, 2, 3, 4, 5, 6, 7]
'''
"""
優(yōu)化方式三
大致思想就是一次排序可以確定兩個值,正向掃描找到最大值交換到最后,反向掃描找到最小值交換到最前面。
"""
def bubblesort4(dest_list=[]):
if len(dest_list) <= 1:
return dest_list
k = len(dest_list) - 1 # 確定比較次數(shù)
n = 0 # 同時找最大值的最小需要兩個下標(biāo)遍歷
for i in range(len(dest_list)):
exchange = False
pos = 0 # 用來記錄最后一次交換的位置
print('第{}趟排序:'.format(str(i + 1)))
for j in range(n, k):
if dest_list[j] > dest_list[j + 1]:
dest_list[j], dest_list[j + 1] = dest_list[j + 1], dest_list[j]
exchange = True
pos = j # 交換元素,記錄最后一次交換的位置
print('第{}次排序為:'.format(str(j + 1)), dest_list)
if not exchange: # 如果沒有交換過元素,則已經(jīng)有序
break
k = pos # 下一次比較到記錄位置即可
# print('進(jìn)行倒序?qū)ふ?..')
for m in range(k, n, -1):
if dest_list[m] < dest_list[m - 1]:
dest_list[m], dest_list[m - 1] = dest_list[m - 1], dest_list[m]
exchange = True
# print('第{}次排序為:'.format(str(k - n - m + 1)), dest_list)
n += 1
if not exchange: # 如果沒有交換過元素,則已經(jīng)有序
break
return dest_list
dest = [1, 2, 3, 4, 5, 6, 0]
result = bubblesort4(dest)
print('最后的結(jié)果是:', result)
'''
第1趟排序:
第1次排序為: [1, 2, 3, 4, 5, 6, 0]
第2次排序為: [1, 2, 3, 4, 5, 6, 0]
第3次排序為: [1, 2, 3, 4, 5, 6, 0]
第4次排序為: [1, 2, 3, 4, 5, 6, 0]
第5次排序為: [1, 2, 3, 4, 5, 6, 0]
第6次排序為: [1, 2, 3, 4, 5, 0, 6]
第2趟排序:
第2次排序為: [0, 1, 2, 3, 4, 5, 6]
第3次排序為: [0, 1, 2, 3, 4, 5, 6]
第4次排序為: [0, 1, 2, 3, 4, 5, 6]
第5次排序為: [0, 1, 2, 3, 4, 5, 6]
最后的結(jié)果是: [0, 1, 2, 3, 4, 5, 6]
'''
C語言實現(xiàn)及優(yōu)化
#include <stdio.h>
/* 1.從當(dāng)前元素起,向后依次比較每一對相鄰元素,若逆序則交換 */
/* 2.對所有元素均重復(fù)以上步驟,直至最后一個元素 */
void bubbleSort(int arr[],int len)
{
int i = 0;
int count = 0;
int tmp = 0;
for(i = 0; i < len - 1; i++)//確定排序趟數(shù)
{
int j = 0;
for(j = 0; j < len - 1 - i; j++)//確定比較次數(shù)
{
if(arr[j]>arr[j + 1])
{
//交換
tmp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = tmp;
count ++;
}
}
}
printf("最后交換的次數(shù)是:%d\n", count);
}
/*
優(yōu)化一
假設(shè)我們現(xiàn)在排序ar[]={1,2,3,4,5,6,7,8,10,9}這組數(shù)據(jù),按照上面的排序方式,第一趟排序后將10和9交換已經(jīng)有序,接下來的8趟排序就是多余的,什么也沒做.
所以我們可以在交換的地方加一個標(biāo)記,如果那一趟排序沒有交換元素,說明這組數(shù)據(jù)已經(jīng)有序,不用再繼續(xù)下去.
*/
void bubbleSort2(int arr[], int len)
{
int i=0, j=0, count=0;
for(i=0;i<len;i++) /* 外循環(huán)為排序趟數(shù),len個數(shù)進(jìn)行l(wèi)en-1趟 */
{
int flag = 0;
for(j=0;j<len-i-1;j++) /* 內(nèi)循環(huán)為每趟比較的次數(shù),第i趟比較len-i次 */
{
if(arr[j]>arr[j+1]) /* 相鄰元素比較,若逆序則交換(升序為左大于右,降序反之)*/
{
int temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
flag = 1;
count ++;
}
}
if(flag)
printf("最后交換的次數(shù)是:%d\n", count);
return;
}
printf("最后交換的次數(shù)是:%d\n", count);
}
/*
優(yōu)化二
優(yōu)化一僅僅適用于連片有序而整體無序的數(shù)據(jù)(例如:1, 2,3,4,7,6,5).
但是對于前面大部分是無序而后邊小半部分有序的數(shù)據(jù)(1,2,5,7,4,3,6,8,9,10)排序效率也不可觀,對于種類型數(shù)據(jù),我們可以繼續(xù)優(yōu)化.
既我們可以記下最后一次交換的位置,后邊沒有交換,必然是有序的,然后下一次排序從第一個比較到上次記錄的位置結(jié)束即可.
*/
void bubbleSort3(int arr[], int len)
{
int i = 0;
int count = 0;
int tmp = 0;
int flag = 0;
int pos = 0;//用來記錄最后一次交換的位置
int k = len - 1;
for(i = 0; i < len - 1; i++)//確定排序趟數(shù)
{
pos = 0;
int j = 0;
flag = 0;
for(j = 0; j < k; j++)//確定比較次數(shù)
{
if(arr[j]>arr[j + 1])
{
//交換
tmp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = tmp;
flag = 1;//加入標(biāo)記
pos = j;//交換元素,記錄最后一次交換的位置
count ++;
}
}
if(flag == 0)//如果沒有交換過元素,則已經(jīng)有序
{
printf("最后交換的次數(shù)是:%d\n", count);
return;
}
k = pos;//下一次比較到記錄位置即可
}
printf("最后交換的次數(shù)是:%d\n", count);
return;
}
/*
優(yōu)化三
優(yōu)化二的效率有很大的提升,還有一種優(yōu)化方法可以繼續(xù)提高效率.
大致思想就是一次排序可以確定兩個值,正向掃描找到最大值交換到最后,反向掃描找到最小值交換到最前面.例如:排序數(shù)據(jù)1,2,3,4,5,6,0
*/
void bubbleSort4(int arr[], int len)
{
int i = 0;
int j = 0;
int n = 0;//同時找最大值的最小需要兩個下標(biāo)遍歷
int flag = 0;
int pos = 0;//用來記錄最后一次交換的位置
int k = len - 1;
for(i = 0; i < len - 1; i++)//確定排序趟數(shù)
{
pos = 0;
flag = 0;
//正向?qū)ふ易畲笾? for(j = n; j < k; j++)//確定比較次數(shù)
{
if(arr[j]>arr[j + 1])
{
//交換
int tmp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = tmp;
flag = 1;//加入標(biāo)記
pos = j;//交換元素,記錄最后一次交換的位置
}
}
if(flag == 0)//如果沒有交換過元素,則已經(jīng)有序,直接結(jié)束
{
return;
}
k = pos;//下一次比較到記錄位置即可
//反向?qū)ふ易钚≈? for(j = k; j > n; j--)
{
int tmp = arr[j];
arr[j] = arr[j - 1];
arr[j - 1] = tmp;
flag = 1;
}
n++;
if(flag == 0)//如果沒有交換過元素,則已經(jīng)有序,直接結(jié)束
{
return;
}
}
}
int main()
{
int i=0;
int dest[] = { 1, 2, 5, 7, 4, 3, 6, 8, 9, 10 };
bubbleSort(dest, 7);
for(i=0;i<7;i++)
printf("%d ", dest[i]);
printf("\n");
int dest1[] = { 1, 2, 5, 7, 4, 3, 6, 8, 9, 10 };
bubbleSort2(dest1, 7);
for(i=0;i<7;i++)
printf("%d ", dest1[i]);
printf("\n");
int dest2[] = { 1, 2, 5, 7, 4, 3, 6, 8, 9, 10 };
bubbleSort3(dest2, 10);
for(i=0;i<10;i++)
printf("%d ", dest2[i]);
printf("\n");
int dest3[] = { 1, 2, 5, 7, 4, 3, 6, 8, 9, 10 };
bubbleSort4(dest2, 10);
for(i=0;i<10;i++)
printf("%d ", dest3[i]);
printf("\n");
return 0;
}
