十大排序（一）：冒泡排序
目录
一、简介
冒泡排序是一种简单的排序算法，它重复地比较相邻的两个元素，如果顺序错误就交换它们，直到没有元素需要交换为止。这个过程类似于气泡在水中上升的过程，因此被称为冒泡排序。
实现过程
下面是冒泡排序的实现过程：
- 从待排序的数组中的第一个元素开始，依次比较相邻的两个元素。
- 如果前一个元素大于后一个元素，则交换它们的位置。
- 继续比较下一对相邻元素，直到比较到数组的最后一个元素。
- 重复以上步骤，每次比较的元素个数减少一位，直到最后一个元素。
- 重复以上步骤，直到所有元素都按照从小到大的顺序排列。
时间复杂度
冒泡排序的时间复杂度是O(n^2)，其中n是待排序数组的长度。由于每次排序都会比较相邻的两个元素，因此需要进行n-1次比较。而每次比较都有可能进行元素交换，最坏情况下需要进行n-1次交换。因此，总的比较和交换次数都是(n-1)+(n-2)+(n-3)+...+1 = n*(n-1)/2（等差数列求和公式），即O(n^2)。
二、代码实现
思想随易，实现不易，接下来是冒泡排序的代码实现（以C语言为例）。
函数声明
void BubbleSort(int* a, int n);//接收一个数组，作为参数Swap函数
冒泡排序是一种交换排序，每次比较两个数，如果符合条件（大泡泡在前，小泡泡在后），则会发生位置的交换。我们先实现一个能完成两个数交换的函数Swap。
Swap
功能：能实现两个数的交换
void Swap(int* pa, int* pb)
{
int tmp = *pa;
*pa = *pb;
*pb = tmp;
}单趟
我们先来完成一趟冒泡排序过程的代码：
假设有10个数，下标为0~9，在第一趟冒泡排序的过程中，要比较的下标为（0,1），（1,2），（2,3），... （8,9）。我们用for循环产生每对下标的前一个（或后一个）（以前一个为例），记为i，那么i的最大下标为n-2(n为数组元素个数）。因此，控制循环结束的条件为i<n-1（或i<=n-2）。
void BubbleSort(int* a, int n)
{
//单趟（第一趟）排序的过程
for (int i = 0; i < n - 1; i++)
{
//前一个泡泡大，则换到后一个位置
if (a[i] > a[i + 1])
{
Swap(&a[i], &a[i + 1]);
}
}
}多趟
但是，以上的一趟排序只是把最大的数换到了最后，只解决了一个数的排序。因此，我们需要进行多趟的排序。假设有10（n）个数，我们只需要进行9（n-1）趟的排序，9个数到了他们正确的位置，那么余下的一个数也找到了他的位置。把趟数用j作为标记，把循环次数控制为n-1。
void BubbleSort(int* a, int n)
{
//j为趟数
for (int j = 0; j < n - 1; j++)
{
//单趟排序(第一趟)的过程
for (int i = 0; i < n - 1; i++)
{
//前一个泡泡大，则换到后一个位置
if (a[i] > a[i + 1])
{
Swap(&a[i], &a[i + 1]);
}
}
}
}0~n-2,循环次数为n-1。
那么，我们把第一趟的单趟冒泡排序走完后，完成了一个数的排序，把最大的数，放在了n-1，数组中最后一个下标的位置。接下来，第二趟的排序，我们要完成的是n-1个数的排序，最后一个位置的坐标为n-2，最后完成比较的那一对坐标为（n-3, n-2），所以i最大为n-3。单趟排序的代码需做些修改,使第j趟的排序，与i能够对应上。
void BubbleSort(int* a, int n)
{
for (int j = 0; j < n - 1; j++)
{
//单趟排序(第j趟)的过程
for (int i = 0; i < n - 1 - j; i++)
{
if (a[i] > a[i + 1])
{
Swap(&a[i], &a[i + 1]);
}
}
}
}我们把i控制为 i < n-1-j：
第一趟：j = 0，i < n-1-0，即 i < n - 1, i最大为n-2。
第二趟：j = 1，i < n-1-1，即 i < n - 2, i最大为n-3。
。。。
符合条件！
测试
以上，就完成了冒泡排序的代码。
做些小小的测试：
执行完BubbleSort后，数组变为了有序，成功！
优化
最后给出一个优化版本：
//冒泡
void BubbleSort(int* a, int n)
{
for (int j = 0; j < n - 1; j++)
{
//假设数组已经有序
int flag = 1;
//单趟排序(第j趟)的过程
for (int i = 0; i < n - 1 - j; i++)
{
if (a[i] > a[i + 1])
{
Swap(&a[i], &a[i + 1]);
flag = 0;//数据发生了交换，假设错误
}
}
//这趟排序无任何数据发生交换，数组已然有序
if (flag == 1)
{
break;
}
}
}冒泡排序如果在进行某趟排序后，就已经有序了，我们再进行一趟排序后，发现无任何数据发生交换，就不然其进行下一趟的排序，直接跳出循环。
以上为冒泡排序内容介绍，感谢各位读者三连支持！
原文地址：https://blog.csdn.net/2302_81053095/article/details/142315634
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！