冒泡排序

冒泡排序為交換排序的一種：

1. 基本思想：所謂交換，就是根據序列中兩個記錄鍵值的比較結果來對換這兩個記錄在序列中的位置。
2. 交換排序的特點是：將鍵值較大的記錄向序列的尾部移動，鍵值較小的記錄向序列的前部移動。

而冒泡排序升序時每遍歷一次會將未排好的集合中大的值移動到后面（或小的移到前面），直到排好序。

動圖展示：

冒泡排序的特性總結：

1. 冒泡排序是一種非常容易理解的排序
2. 時間復雜度：O(N ^ 2)
3. 空間復雜度：O(1)
4. 穩定性：穩定

冒泡排序排整型數據參考代碼（VS2022C語言環境）：

#include <stdio.h>
#include <stdbool.h>void swap(int* a, int* b)
{int temp = *a;*a = *b;*b = temp;
}//			要排序的數組	 數組大小
int bubbleSort(int* arr, int sz)
{// 1.n個數中，每次交換前需要比較兩個數字，則比較次數為n - 1for (int i = 0; i < sz - 1; ++i){bool flag = true;						// 3.檢查是否有序// 2.在 “1.” 的基礎之上，i每循環一次，必定有一個數排好到后面，則 “- i" 來優化for (int j = 0; j < sz - 1 - i; ++j){if (arr[j] > arr[j + 1]){flag = false;					// 3.表示無序swap(&arr[j], &arr[j + 1]);}}if (flag == true)						// 3.有序直接退出循環{break;}}
}int main()
{int arr[10] = { 3, 9, 2, 7, 8, 5, 6, 1, 10, 4 };int sz = 10;bubbleSort(arr, sz);for (int i = 0; i < sz; ++i){printf("%d ", arr[i]);}return 0;
}

冒泡排序C語言通用連續類型排序代碼

上述C語言冒泡排序代碼只支持整型排序，這里將其擴展為通用的連續類型排序代碼。

參考C語言內置的qsort排序：

可以得到函數為：

void swap(char* a, char* b, size_t width)
{for (int i = 0; i < width; ++i){char temp = *(a + i);*(a + i) = *(b + i);*(b + i) = temp;}
}//			要排序的數組	   數組大小	   每個元素寬度		比較的函數指針
int bubbleSort(void* base, size_t sz, size_t width, int (*compare)(const void* e1, const void* e2))
{// 1.n個數中，每次交換前需要比較兩個數字，則比較次數為n - 1for (int i = 0; i < sz - 1; ++i){bool flag = true;						// 3.檢查是否有序// 2.在 “1.” 的基礎之上，i每循環一次，必定有一個數排好到后面，則 “- i" 來優化for (int j = 0; j < sz - 1 - i; ++j){if (compare((char*)base + j * width, (char*)base + j * width + width) > 0){flag = false;					// 3.表示無序swap((char*)base + j * width, (char*)base + j * width + width, width);}}if (flag == true)						// 3.有序直接退出循環{break;}}
}

事實上，我們只需要對其兩個地方大幅度更改，就可以得到通用的排序：

對比較的方式更改：

將比較方式改為函數指針的方式，這樣使用者使用時可以自己寫比較的類型函數（不僅包含內置類型，struct 定義的也可以，但前提是連續的）

如果使用者對整型排序，則自己寫的compare為（只供參考，方法不唯一）：

int cmp(const void* e1, const void* e2)
{// (int*)e1 表示將泛型指針轉為整型指針// *((int*)e1) 表示對整型指針解引用從而得到整型的數 // 兩整型的數相減，為正則e1大，為負則e2大，為0則相等return *((int*)e1) - *((int*)e2);
}

對交換的方式更改：

這里只需將交換方式改為一個字節一個字節的方式交換即可。


則swap應改為：

void swap(char* a, char* b, size_t width)
{// a 和 b 表示兩個數開始的地址// a + i 表示 a 元素第 i 塊字節的地址，同理于b// *(a + i) 表示 a 元素第 i 塊字節的內容，同理于b// 通過一個字節一個字節的交換，確保內容不會丟失for (int i = 0; i < width; ++i){char temp = *(a + i);*(a + i) = *(b + i);*(b + i) = temp;}
}

結果驗證：

內置類型：

完整代碼：

#include <stdio.h>
#include <stdbool.h>void swap(char* a, char* b, size_t width)
{for (int i = 0; i < width; ++i){char temp = *(a + i);*(a + i) = *(b + i);*(b + i) = temp;}
}//			要排序的數組	   數組大小	   每個元素寬度		比較的函數指針
int bubbleSort(void* base, size_t sz, size_t width, int (*compare)(const void* e1, const void* e2))
{// 1.n個數中，每次交換前需要比較兩個數字，則比較次數為n - 1for (int i = 0; i < sz - 1; ++i){bool flag = true;						// 3.檢查是否有序// 2.在 “1.” 的基礎之上，i每循環一次，必定有一個數排好到后面，則 “- i" 來優化for (int j = 0; j < sz - 1 - i; ++j){if (compare((char*)base + j * width, (char*)base + j * width + width) > 0){flag = false;					// 3.表示無序swap((char*)base + j * width, (char*)base + j * width + width, width);}}if (flag == true)						// 3.有序直接退出循環{break;}}
}int cmp(const void* e1, const void* e2)			// 對整形
{return *((int*)e1) - *((int*)e2);
}int cmp1(const void* e1, const void* e2)		// 對字符
{return *((char*)e1) - *((char*)e2);
}int cmp2(const void* e1, const void* e2)		// 對浮點
{double num1 = *(double*)e1;double num2 = *(double*)e2;// double 返回與 int 沖突會影響，只需更改一下返回邏輯return num1 > num2 ? 1 : -1;
}int main()
{int arr[10] = { 3, 9, 2, 7, 8, 5, 6, 1, 10, 4 };int sz = 10;bubbleSort(arr, sz, sizeof(int), cmp);for (int i = 0; i < sz; ++i){printf("%d ", arr[i]);}printf("\n");char arr1[10] = { 3, 9, 2, 7, 8, 5, 6, 1, 10, 4 };double arr2[10] = { 3.1, 9.4, 2.9, 7.8, 8.8, 5.1, 6.2, 1.0, 10.1, 4.4 };bubbleSort(arr1, sz, sizeof(char), cmp1);bubbleSort(arr2, sz, sizeof(double), cmp2);for (int i = 0; i < sz; ++i){printf("%d ", arr1[i]);}printf("\n");for (int i = 0; i < sz; ++i){printf("%.2lf ", arr2[i]);}printf("\n");return 0;
}

自定義類型：

完整代碼：

#include <stdio.h>
#include <stdbool.h>
#include <string.h>void swap(char* a, char* b, size_t width)
{for (int i = 0; i < width; ++i){char temp = *(a + i);*(a + i) = *(b + i);*(b + i) = temp;}
}//			要排序的數組	   數組大小	   每個元素寬度		比較的函數指針
int bubbleSort(void* base, size_t sz, size_t width, int (*compare)(const void* e1, const void* e2))
{// 1.n個數中，每次交換前需要比較兩個數字，則比較次數為n - 1for (int i = 0; i < sz - 1; ++i){bool flag = true;						// 3.檢查是否有序// 2.在 “1.” 的基礎之上，i每循環一次，必定有一個數排好到后面，則 “- i" 來優化for (int j = 0; j < sz - 1 - i; ++j){if (compare((char*)base + j * width, (char*)base + j * width + width) > 0){flag = false;					// 3.表示無序swap((char*)base + j * width, (char*)base + j * width + width, width);}}if (flag == true)						// 3.有序直接退出循環{break;}}
}typedef struct Student
{char name[20];int age;char id[10];
} Student;int cmpAge(const void* e1, const void* e2)
{return ((Student*)e1)->age - ((Student*)e2)->age;
}int cmpId(const void* e1, const void* e2)
{return strcmp(((Student*)e1)->id, ((Student*)e2)->id);
}int main()
{Student arr[5] = {{.name = "張三", .age = 20, .id = "1" },{.name = "李四", .age = 21, .id = "2" },{.name = "王二", .age = 18, .id = "3" },{.name = "麻子", .age = 30, .id = "4" } };int sz = 4;bubbleSort(arr, sz, sizeof(Student), cmpAge);printf("以年齡排序：\n");for (int i = 0; i < sz; ++i){printf("%s ", arr[i].name);printf("%d ", arr[i].age);printf("%s\n", arr[i].id);}printf("\n");bubbleSort(arr, sz, sizeof(Student), cmpId);printf("以ID排序：\n");for (int i = 0; i < sz; ++i){printf("%s ", arr[i].name);printf("%d ", arr[i].age);printf("%s\n", arr[i].id);}printf("\n");return 0;
}

注意：

上述代碼對不連續的數據無效，如鏈表的每個元素是以指針連接存儲的，compare函數 和 swap函數 需要更改來解決。