NO IMAGE

定義:每一趟依次比較相鄰的兩個數,將小數放在前面,大數放在後面,直到一趟只剩下一個元素。
時間複雜度:O(n^2)。

氣泡排序是最常用的小型資料排序方式,下面是用C語言實現的,及其兩種優化方式。

第一種優化方式是設定一個標記位來標記是否發生了交換,如果沒有發生交換就提前結束;

第二種優化方式是記錄最後發生交換的位置,作為下一趟比較結束的位置。

#include <stdio.h>
/*
* 列印陣列
* */
void printArray(int arr[], int n) {
int i = 0;
for (i = 0; i < n;   i) {
printf("%d ", arr[i]);
}
printf("\n");
}
/*
* 氣泡排序
* */
void bubbleSort(int arr[], int n) {
int i = 0;
int j = 0;
int tmp = 0;
for (i = 0; i < n;   i) {
for (j = 0; j < n - 1 - i;   j) {
if (arr[j] < arr[j   1]) {
tmp = arr[j];
arr[j] = arr[j   1];
arr[j   1] = tmp;
}
}
}	
}
/*
* 氣泡排序優化一
* 設定一個標記來標誌一趟比較是否發生交換
* 如果沒有發生交換,則陣列已經有序
* */
void bubbleSort1(int arr[], int n) {
int i = 0;
int j = 0;
int tmp = 0;
int flag = 0; 
for (i = 0; i < n;   i) {
flag = 0;
for (j = 0; j < n - 1 - i;   j) {
if (arr[j] < arr[j   1]) {
flag = 1;
tmp = arr[j];
arr[j] = arr[j   1];
arr[j   1] = tmp;
}
}
if (flag == 0) {
break;
}
}	
}
/*
* 氣泡排序優化二
* 用一個變數記錄下最後一個發生交換的位置,後面沒有發生交換的已經有序
* 所以可以用這個值來作為下一次比較結束的位置
* */
void bubbleSort2(int arr[], int n) {
int i = 0;
int j = 0;
int k = 0;
int tmp = 0;
int flag = n; 
for (i = 0; i < flag;   i) {
k = flag;
flag = 0;
for (j = 0; j < k;   j) {
if (arr[j] < arr[j   1]) {
flag = j;
tmp = arr[j];
arr[j] = arr[j   1];
arr[j   1] = tmp;
}
}
}	
}
int main() {
int arr[] = {9, 5, 8, 4, 7, 3, 2, 0, 6, 1};
printArray(arr, 10);
bubbleSort2(arr, 10);
printArray(arr, 10);
return 0;
}