北京企业网站推广哪家公司好网站建设 小程序开发
目录
一、简介
实现过程
时间复杂度
二、代码实现
函数声明
Swap函数
单趟
多趟
测试
优化
一、简介
冒泡排序是一种简单的排序算法，它重复地比较相邻的两个元素，如果顺序错误就交换它们，直到没有元素需要交换为止。这个过程类似于气泡在水中上升的过程，因此被称为冒泡排序。
实现过程
下面是冒泡排序的实现过程：
- 从待排序的数组中的第一个元素开始，依次比较相邻的两个元素。
- 如果前一个元素大于后一个元素，则交换它们的位置。
- 继续比较下一对相邻元素，直到比较到数组的最后一个元素。
- 重复以上步骤，每次比较的元素个数减少一位，直到最后一个元素。
- 重复以上步骤，直到所有元素都按照从小到大的顺序排列。
时间复杂度
冒泡排序的时间复杂度是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;}}
}冒泡排序如果在进行某趟排序后，就已经有序了，我们再进行一趟排序后，发现无任何数据发生交换，就不然其进行下一趟的排序，直接跳出循环。
以上为冒泡排序内容介绍，感谢各位读者三连支持！