1.冒泡排序概念
冒泡排序（Bubble Sort）是一种简单的排序算法，它重复地交换相邻的元素，将较大的元素“冒泡”到数组的末尾。
2.冒泡排序图解
给定一个乱序数组7,1,9,5,2,6,4降序排列
首先要比较相邻两个元素的大小，然后如果满足前一个数大于后一个数则交换
第一趟
7>1，交换得1,7,9,5,2,6,4
第二次1,7,9,5,2,6,4
第三次1,7,5,9,2,6,4
.......
最后直到变为1,7,5,2,6,4,9
第二趟
直到1,5,2,6,4,7,9
以此类推
直到六趟后整个数组变为
1,2,4,5,6,7,9
至此数组有序且降序
根据以上，我们不难发现，一个长度为n的数组，最多经过n-1趟后，数组有序
每一趟最多排序n-1-i(趟数)次
3.代码示例
#include <stdio.h> void bubblesort(int* arr, size_t n) { for (int i = 0; i < n; i++) { for (int j = 0; j < n - i - 1; j++) { if (arr[j] > arr[j + 1]) { int tmp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = tmp; } } } } void printarr(int* arr, size_t n) { for (int i = 0; i < n; i++) { printf("%d ", arr[i]); } } int main() { int arr[] = { 7,1,9,5,2,6,4 }; int sz = sizeof(arr) / sizeof(arr[0]); bubblesort(arr, sz); printarr(arr, sz); }
运行结果
4.冒泡排序代码改进
当我给到一个数组9,0,1,2,3,4,5时我们可以发现其实循环只用走一趟，数组就能有序，大大减少运行时间，所以我们可以先让循环走一次把9放到最后，然后再走一次判断此时数组是否有序
代码示例
#include <stdio.h> void bubblesort(int* arr, size_t n) { int flag = 1; for (int i = 0; i < n; i++) { for (int j = 0; j < n - i - 1; j++) { if (arr[j] > arr[j + 1]) { int tmp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = tmp; flag = 0; } } if (flag == 1) break; } } void printarr(int* arr, size_t n) { for (int i = 0; i < n; i++) { printf("%d ", arr[i]); } } int main() { int arr[] = { 9,0,1,2,3,4,5 }; int sz = sizeof(arr) / sizeof(arr[0]); bubblesort(arr, sz); printarr(arr, sz); }
运行结果
