一、什么是冒泡排序
冒泡排序是一种排序思想，目的是让一组无序的数据，通过比较规则和相邻元素两两比较，最终形成有序的数据。冒泡排序的对象可以是整型数据、字符型数据、结构体（需制定通过结构体哪个成员进行比较的规则）。
以下代码中，通过排序整型数据来演示。
二、三个版本代码解析
方法一：
void BubbleSort(int* arr, int sz)
{
for (int i = 0; i < sz - 1; i++)
{
for (int j = 0; j < sz - 1 - i; j++)
{
if (arr[j] > arr[j + 1])
{
int tmp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = tmp;
}
}
}
}
void printArr(int* arr, int sz)
{
for (int i = 0; i < sz; i++)
{
printf("%d ", *(arr + i));
}
printf("\n");
}
int main()
{
int arr[] = { 9,7,5,3,1,2,4,6,8,10 };
int sz = sizeof(arr) / sizeof(arr[0]);
printf("排序前:\n");
printArr(arr, sz);
BubbleSort(arr, sz);
printf("排序后：\n");
printArr(arr, sz);
return 0;
}
以上代码包含三个函数：BubbleSort()、printArr()以及main函数，主要讲解这里的实现冒牌排序的函数。函数由两层for循环形成，外层for循环控制比较的次数，假设有10个无序的数据，那么最多只要比较9次就可以让元素形成有序，所以这里i < sz(数据个数)-1。内层for循环是控制每一轮比较边界的，即每一轮比较的元素最大和最小下标在哪里，每一次初始值j = 0，而通过每一轮的比较都可以让一个数归于属于它的位置上，所以j的右边界是sz-1-i（每一轮都有后i个元素不参与比较）。
方法二：
void BubbleSort(int* arr, int sz)
{
for (int end = sz; end > 0; end--)
{
for (int i = 1; i < end; i++)
{
if (arr[i - 1] > arr[i])
{
int tmp = arr[i - 1];
arr[i - 1] = arr[i];
arr[i] = tmp;
}
}
}
}
void printArr(int* arr, int sz)
{
for (int i = 0; i < sz; i++)
{
printf("%d ", *(arr + i));
}
printf("\n");
}
int main()
{
int arr[] = { 9,7,5,3,1,2,4,6,8,10 };
int sz = sizeof(arr) / sizeof(arr[0]);
printf("排序前：\n");
printArr(arr, sz);
BubbleSort(arr, sz);
printf("排序后：\n");
printArr(arr, sz);
return 0;
}
以上冒泡排序的实现思想其实和方法一是一样的，外层循环都是在控制内层循环的右边界，把每一轮冒泡排序中的最大数通过比较移动到最右面的位置上。
方法三：
void BubbleSort(int* arr, int sz)
{
for (int i = 0; i < sz - 1; i++)
{
for (int j = sz - 1; j > 0; j--)
{
if (arr[j - 1] > arr[j])
{
int tmp = arr[j - 1];
arr[j - 1] = arr[j];
arr[j] = tmp;
}
}
}
}
void printArr(int* arr, int sz)
{
for (int i = 0; i < sz; i++)
{
printf("%d ", *(arr + i));
}
printf("\n");
}
int main()
{
int arr[] = { 9,7,5,3,1,2,4,6,8,10 };
int sz = sizeof(arr) / sizeof(arr[0]);
printf("排序前：\n");
printArr(arr, sz);
BubbleSort(arr, sz);
printf("排序后：\n");
printArr(arr, sz);
return 0;
}
这一种写法，依旧是sz-1轮的比较，是将每一轮中最小的数通过两两比较归于当前轮数中的最低位上。
三、时间复杂度的对比
| 版本 | 最好情况 | 平均情况 | 最坏情况 |
|---|---|---|---|
| 方法一 | O(n^2) | O(n^2) | O(n^2) |
| 方法二 | O(n^2) | O(n^2) | O(n^2) |
| 方法三 | O(n) | O(n^2) | O(n^2) |
四、空间复杂度的对比
都只开辟了常数个临时变量，所以空间复杂度都是O（1）。
转载自 CSDN-专业IT技术社区
原文链接：https://blog.csdn.net/weixin_44218929/article/details/169557686
