十大排序之：冒泡排序

目录

一、简介

实现过程 

时间复杂度

二、代码实现

函数声明

Swap函数 

单趟

多趟

测试 

优化 

---

一、简介

冒泡排序是一种简单的排序算法，它重复地比较相邻的两个元素，如果顺序错误就交换它们，直到没有元素需要交换为止。这个过程类似于气泡在水中上升的过程，因此被称为冒泡排序。

 

实现过程 

下面是冒泡排序的实现过程：

1. 从待排序的数组中的第一个元素开始，依次比较相邻的两个元素。
2. 如果前一个元素大于后一个元素，则交换它们的位置。
3. 继续比较下一对相邻元素，直到比较到数组的最后一个元素。
4. 重复以上步骤，每次比较的元素个数减少一位，直到最后一个元素。
5. 重复以上步骤，直到所有元素都按照从小到大的顺序排列。

时间复杂度

 冒泡排序的时间复杂度是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;}}
}

冒泡排序如果在进行某趟排序后，就已经有序了，我们再进行一趟排序后，发现无任何数据发生交换，就不然其进行下一趟的排序，直接跳出循环。 

 

以上为冒泡排序内容介绍，感谢各位读者三连支持！