氣泡排序是一種複雜度為O(n2)的低效排序演算法。它透過不斷比較元素並交換位置使一個元素到達有序集合的正確位置上。
氣泡排序的過程是把相鄰的資料元素進行交換,從而逐步將待排序序列變成有序序列。氣泡排序的基本思想是:從頭掃描待排序序列,在掃描的過程中順次比較相鄰兩個元素的大小。
下面以升序為例介紹排序過程。
(1)在第一輪排序中,對n個記錄進行如下操作。
①對相鄰的兩個記錄的關鍵字進行比較,逆序時就交換位置。
②在掃描的過程中,不斷向後移動相鄰兩個記錄中關鍵字較大的記錄。
(2)進行第二輪氣泡排序,對前n-1個記錄進行同樣的操作,其結果是使次大的記錄被放在第n-2個記錄的位置上。
(3)繼續進行排序工作,在後面幾輪的升序處理也反覆遵循了上述過程,直到排好順序為止。如果在某一輪冒泡過程中沒有發現一個逆序,就可以馬上結束氣泡排序。整個冒泡過程最多可以進行n-1輪,如圖演示了一個完整的氣泡排序過程。
使用C語言實現氣泡排序的演算法程式碼如下所示:
/*對陣列 r 做氣泡排序,length為陣列的長度*/
typedef int KeyType;
typedef struct {
KeyType key;
} RecordType ;
void BubbleSort(RecordType r[], int length ){
n=length;
change=TRUE;
for ( i=1 ; i<= n-1 && change ;++i ) {
change=FALSE;
for ( j=1 ; j<= n-i ; ++j)
if (r[j].key> r[j+1].key ) {
x= r[j];
r[j]= r[j+1];
r[j+1]= x;
}
} /* BubbleSort */
氣泡排序是一種複雜度為O(n2)的低效排序演算法。它透過不斷比較元素並交換位置使一個元素到達有序集合的正確位置上。
氣泡排序的過程是把相鄰的資料元素進行交換,從而逐步將待排序序列變成有序序列。氣泡排序的基本思想是:從頭掃描待排序序列,在掃描的過程中順次比較相鄰兩個元素的大小。
下面以升序為例介紹排序過程。
(1)在第一輪排序中,對n個記錄進行如下操作。
①對相鄰的兩個記錄的關鍵字進行比較,逆序時就交換位置。
②在掃描的過程中,不斷向後移動相鄰兩個記錄中關鍵字較大的記錄。
(2)進行第二輪氣泡排序,對前n-1個記錄進行同樣的操作,其結果是使次大的記錄被放在第n-2個記錄的位置上。
(3)繼續進行排序工作,在後面幾輪的升序處理也反覆遵循了上述過程,直到排好順序為止。如果在某一輪冒泡過程中沒有發現一個逆序,就可以馬上結束氣泡排序。整個冒泡過程最多可以進行n-1輪,如圖演示了一個完整的氣泡排序過程。
使用C語言實現氣泡排序的演算法程式碼如下所示:
/*對陣列 r 做氣泡排序,length為陣列的長度*/
typedef int KeyType;
typedef struct {
KeyType key;
} RecordType ;
void BubbleSort(RecordType r[], int length ){
n=length;
change=TRUE;
for ( i=1 ; i<= n-1 && change ;++i ) {
change=FALSE;
for ( j=1 ; j<= n-i ; ++j)
if (r[j].key> r[j+1].key ) {
x= r[j];
r[j]= r[j+1];
r[j+1]= x;
change=TRUE;
}
}
} /* BubbleSort */