原创不易,转载请注明出处。欢迎点赞收藏~
冒泡排序是一种简单的排序算法,其原理是重复地比较相邻的两个元素,并将顺序不正确的元素进行交换,使得每次遍历都能将一个最大(或最小)的元素放到末尾。通过多次遍历,最终实现整个序列的排序。
具体的冒泡排序算法步骤如下:
- 比较相邻的两个元素。如果第一个大于第二个,则交换它们的位置。
- 对每一对相邻元素重复步骤1,从开始到结尾。这样一次遍历之后,最大的元素会被放在序列的末尾。
- 针对所有的元素重复步骤1和步骤2,除了已经排好序的末尾元素。
- 重复步骤3,直到整个序列有序为止。
冒泡排序的时间复杂度为O(n^2),其中n为待排序序列的长度。这是因为在最坏情况下,需要进行n-1轮比较,每轮比较需要遍历剩余未排序元素。所以总共需要比较的次数为(n-1)+(n-2)+...+1=n*(n-1)/2,因此时间复杂度为O(n^2)。
冒泡排序的空间复杂度为O(1),即只需要常数级别的额外空间来存储临时交换变量,不随待排序序列的大小而变化。
冒泡排序是一种稳定的排序算法,即相等元素的相对次序在排序后保持不变。但由于其时间复杂度较高,在实际应用中较少使用,更多地作为教学和理解排序算法的基础。
C/C++语言示例如下:
#include <stdio.h>// 冒泡排序函数
void bubble_sort(int arr[], int n)
{for (int i = 0; i < n - 1; i++){for (int j = 0; j < n - i - 1; j++){if (arr[j] > arr[j + 1]){// 交换相邻元素的位置int temp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = temp;}}}
}int main()
{int arr[] = {64, 34, 25, 12, 22, 11, 90};int n = sizeof(arr) / sizeof(arr[0]);printf("排序前的数组:\n");for (int i = 0; i < n; i++){printf("%d ", arr[i]);}bubble_sort(arr, n);printf("\n排序后的数组: \n");for (int i = 0; i < n; i++){printf("%d ", arr[i]);}putchar('\n');return 0;
}
运行结果如下: