算法介绍——冒泡排序

冒泡排序

冒泡排序的基本思想是：每次比较两个相邻的元素，如果它们的顺序错误就把它们交换过来。

举例说明

假如我们需要将 12 35 99 18 76 这 5 个数进行从大到小的排序。我们可以这么做：

• 首先比较第 1 位和第 2 位的大小，现在第 1 位是 12，第 2 位是 35。发现 12 比 35 要小，因为我们希望小的排在后面，因此需要交换这两个数的位置。交换之后这 5 个数的顺序是 35 12 99 18 76。
• 按照这个方法，继续比较第 2 位和第 3 位的大小，第 2 位是 12，第 3 位是 99。12 比 99 要小，因此需要交换这两个数的位置。交换之后这 5 个数的顺序是 35 99 12 18 76。
• 继续比较第 3 位和第 4 位的大小，如果第 3 位比第 4 位小，则交换两个数的位置。交换之后这 5 个数的顺序是 35 99 18 12 76。
• 最后，比较第 4 位和第 5 位。4 次比较之后 5 个数的顺序是 35 99 18 76 12。

这个过程如下图所示：

每次都是比较相邻的两个数，如果后面的数比前面的数大，则交换这两个数的位置。一直比较下去直到两个数比较完毕，最小的数就在最后一个了。就如同是一个气泡，一步一步往后 “翻滚”，直到最后一位。所以这个排序的方法有一个很好听的名字 “冒泡排序”。

说到这里其实我们的排序只将 5 个数中最小的一个归位了。每将一个数归位我们将其称为 “一趟”。下面我们将继续重复刚才的过程，将剩下的 4 个数一一归位。

• 现在开始 “第二趟”，目标是将第 2 小的数归位。首先还是先比较第 1 位和第 2 位，如果第 1 位比第 2 位小，则交换位置。交换之后这 5 个数的顺序是 99 35 18 76 12。接下来比较第 2 位和第 3 位、第 3 位和第 4 位。注意此时已经不需要再比较第 4 位和第 5 位，因为在第一趟结束后已经可以确定第 5 位就是最小的。
• “第三趟” 也是一样的。第三趟之后这 5 个数的顺序是 99 76 35 18 12。
• 接下来还要走 “第四趟”。有的小伙伴可能会问，这不是已经排好了吗？还要继续吗？当然，这里纯属巧合，如果换其他数可能就不是这样了。“第四趟” 只需要比较第 1 位和第 2 位的大小，因为第 1 位是 99，第 2 位是76，所以不需要交换。这 5 个数的顺序不变，仍然是 99 76 35 18 12。
• 到此排序完美结束了，5 个数已经有 4 个数归位，那最后一个数也只能放在第 1 位了。

整个排序过程如下图所示：

我们来总结一下：如果有 n 个数进行排序，只需将 n-1 个数归位，即需要要进行 n-1 趟操作。而 “每一趟” 都需要从第 1 位开始进行相邻两个数的比较，将较小的一个数放在后面，比较完毕后向后挪一位继续比较后面两个相邻数的大小，重复此步骤，直到最后一个尚未归位的数。

C代码实现

#include <stdio.h>
#include <assert.h>

#define DEBUG 1

static int bsort(int *a, unsigned int size)
{
	int i, j, k, t;

	assert(a);

	for(i=1; i<size; i++) {
#if DEBUG
		for(k=0; k<5; k++) {
			printf("%d ", a[k]);
		}
		printf("\n");
#endif
		/* 冒泡排序的核心部分 */
		for(j=0; j<size-i; j++) {
			if(a[j] < a[j+1]) {
				t = a[j];
				a[j] = a[j+1];
				a[j+1] = t;
			}
		}
	}
	return 0;
}

int main(void)
{
	int a[5] = {12, 35, 99, 18, 76};  /* 简单起见，直接对数组进行初始化 */
	int i;

	bsort(a, 5);  /* 调用冒泡排序接口函数 */

	for(i=0; i<5; i++) {
		printf("%d ", a[i]);
	}
	printf("\n");
    
	return 0;
}

编译并执行代码，如下：

复杂度分析

冒泡排序的核心部分是双重嵌套循环。假设有 n 个待排序数，则循环执行了 $\rm{(n-1)(\frac{n}{2}+1)}$，不难看出冒泡排序的时间复杂度是 $\rm{O(N2)}$。

这是一个非常高的时间复杂度。冒泡排序早在 1956 年就有人开始研究，之后有很多人都尝试过对冒泡排序进行改进，但结果却令人失望。如 Donald E. Knuth（中文名为高德纳，1974年图灵奖获得者）所说：“冒泡排序除了它迷人的名字和导致了某些有趣的理论问题这一事实之外，似乎没有什么值得推荐的。”

转载：https://blog.csdn.net/luckydarcy/article/details/102484894