数据结构从入门到精通——冒泡排序

鲜于言悠

发布于 2024-03-24 13:04:01

890

发布于 2024-03-24 13:04:01

冒泡排序

前言

冒泡排序是一种简单的排序算法，通过重复遍历待排序数列，比较相邻元素的大小并交换位置，使得每一轮遍历后最大（或最小）的元素都会“冒泡”到数列的一端，直到整个数列有序。这种算法的时间复杂度较高，但在处理小规模数据或近乎有序的数据时表现良好，除此之外，与其他排序算法相比，冒泡排序更适用于教学而不适应于实际生活

一、冒泡排序的基本思想

冒泡排序的基本思想是通过相邻元素之间的比较和交换，使得每一趟排序过程中，最大（或最小）的元素能够“冒泡”到序列的一端，从而达到排序的目的。

具体来说，冒泡排序的算法过程可以分为以下几个步骤：

从序列的第一个元素开始，比较相邻的两个元素，如果它们的顺序错误（即前一个元素大于后一个元素），则交换这两个元素的位置。
接着，从序列的第二个元素开始，重复上述步骤，直到序列的最后一个元素。这样，第一趟排序结束后，最大的元素就会被放到序列的最后面。
接下来，对序列的前n-1个元素进行同样的操作，直到整个序列都有序为止。在每一趟排序过程中，都会有一个最大（或最小）的元素被放到序列的末尾。

冒泡排序的时间复杂度为O(n^2)，其中n为序列的长度。虽然它的效率不如一些更高级的排序算法，但由于其实现简单，易于理解，因此在一些实际应用中仍然被广泛使用。

例如，在一些小型数据集的排序中，冒泡排序可以作为一种简单有效的解决方案。此外，在一些需要稳定排序的场合中，冒泡排序也是一种不错的选择，因为它在交换相邻元素时不会改变相等元素的相对顺序。但是像上述这些情况生活中出现的概率很小，没有人会为了冒泡排序而专门设置一串代码。

总之，冒泡排序虽然不是最优的排序算法，但它的基本思想简单易懂，具有教学意义，不适用于实际生活。

二、冒泡排序的特性总结

冒泡排序是一种非常容易理解的排序
时间复杂度：O(N^2)
空间复杂度：O(1)
稳定性：稳定

冒泡排序，作为一种基础的排序算法，虽然在实际应用中由于其效率问题较少被直接使用，但在理解排序算法的基本原理和特性上，它起到了至关重要的作用。以下是对冒泡排序特性的总结：

稳定性：冒泡排序是一种稳定的排序算法。这意味着在排序过程中，对于相等的元素，它们的相对顺序不会发生改变。这对于某些需要保持原有数据结构中元素间关系的场景来说是非常重要的。
简单易懂：冒泡排序的实现逻辑相对直观，容易理解。它通过相邻元素之间的比较和交换来逐步将最大值或最小值“冒泡”到序列的一端。
效率问题：尽管冒泡排序在理解上较为简单，但其效率并不高。它的时间复杂度在最坏情况下为O(n^2)，其中n为待排序序列的长度。这意味着对于大型数据集，冒泡排序可能不是最优的选择。
优化空间：尽管基本冒泡排序效率不高，但可以通过一些优化手段来改进其性能。例如，可以设置一个标志位来跟踪在一次完整的遍历过程中是否发生了交换，如果没有发生交换，则说明序列已经有序，可以提前结束排序。
适应性：冒泡排序适用于小规模数据集或者部分有序的序列。对于部分有序的序列，冒泡排序的效率会相对较高，因为其可以在较少的遍历次数内完成排序。

综上所述，冒泡排序虽然在实际应用中可能不是最优的选择，但它在教学、理解排序算法原理以及处理小规模数据集或特定场景（如稳定性要求高的场景）下仍然具有重要意义。通过深入理解冒泡排序的特性，我们可以更好地掌握排序算法的基本原理和优化方法，为处理更复杂的数据结构和算法问题打下坚实的基础。

三、冒泡排序的动画演示

冒泡排序

冒泡排序的动画演示展示了冒泡排序算法的工作过程。在演示中，可以看到一系列数字按照顺序逐个比较和交换位置，直到所有数字按照升序或降序排列。通过动画，可以清晰地看到每个步骤中数字的变化，从而理解冒泡排序算法的原理和步骤。这种演示方式有助于学习者更好地掌握冒泡排序算法，并理解其在实际应用中的工作原理。

四、冒泡排序的具体代码

test.c

#include<stdio.h>
#include<stdlib.h>
#include<time.h>

void BubbleSort(int* a, int n);
void PrintArray(int* a, int n);
void Swap(int* p1, int* p2)
{
	int tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}
void TestBubbleSort()
{
	//int a[] = { 5, 13, 9, 16, 12, 4, 7, 1, 28, 25, 3, 9, 6, 2, 4, 7, 1, 8 };
	int a[] = { 5, 3, 9, 6, 2, 4, 7, 1, 8 };
	PrintArray(a, sizeof(a) / sizeof(int));

	BubbleSort(a, sizeof(a) / sizeof(int));

	PrintArray(a, sizeof(a) / sizeof(int));
}


void PrintArray(int* a, int n)
{
	for (int i = 0; i < n; i++)
	{
		printf("%d ", a[i]);
	}
	printf("\n");
}
void BubbleSort(int* a, int n)
{
	for (int i = 0; i < n - 1; i++)
	{
		int exchange = 0;
		for (int j = 0; j < n - i - 1; j++)
		{
			if (a[j + 1] <= a[j])
			{
				Swap(&a[j + 1], &a[j]);
				exchange = 1;
			}
		}
		if (exchange == 0)break;
	}
}
void TestOP()
{
	srand(time(0));
	const int N = 10000;
	int* a1 = (int*)malloc(sizeof(int) * N);

	for (int i = 0; i < N; ++i)
	{
		a1[i] = rand();
	}
	int begin1 = clock();
	BubbleSort(a1, N);
	int end1 = clock();
	printf("BubbleSort:%d\n", end1 - begin1);

	free(a1);
}

int main()
{
	TestBubbleSort();
	TestOP();

	return 0;
}

这段代码实现了冒泡排序算法。冒泡排序的基本思想是通过相邻元素的比较和交换来将大的元素逐步“冒泡”到最后。

代码中的函数BubbleSort接受两个参数，一个是待排序数组a，另一个是数组的长度n。

首先，外层的循环i表示排序的轮数，每一轮会把当前未排序部分的最大元素冒泡到最后。循环的终止条件是i < n - 1，因为最后一个元素无需再进行比较。

内层的循环j用来进行相邻元素的比较和交换。每一轮的比较从数组的第一个元素开始，依次比较相邻的两个元素。如果后一个元素小于等于前一个元素，就交换它们的位置。

在每一轮的内层循环结束后，通过exchange变量来判断是否有元素发生了交换。如果没有发生交换，说明数组已经是有序的，就可以提前结束排序。

最终，当外层的循环结束后，整个数组就按照从小到大的顺序排列好了。