临沂seo网站推广,网络优化网络维护网络建站,站长之家站长工具综合查询,个人网页设计思维导图0. 简介 冒泡排序#xff08;Bubble Sort#xff09;是一种简单的排序算法。它重复地遍历要排序的数列#xff0c;一次比较两个元素#xff0c;如果他们的顺序错误就把他们交换过来。遍历数列的工作是重复地进行直到没有再需要交换#xff0c;也就是说该数列已经排…0. 简介 冒泡排序Bubble Sort是一种简单的排序算法。它重复地遍历要排序的数列一次比较两个元素如果他们的顺序错误就把他们交换过来。遍历数列的工作是重复地进行直到没有再需要交换也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。 1. 冒泡排序实现
冒泡排序的基本思想
比较相邻的元素。如果第一个比第二个大就交换他们两个。对每一对相邻元素做同样的工作从开始第一对到结尾的最后一对。这步做完后最后的元素会是最大的数。针对所有的元素重复以上的步骤除了最后一个。持续每次对越来越少的元素重复上面的步骤直到没有任何一对数字需要比较。
冒泡排序过程演示 2. 冒泡排序时间复杂度和空间复杂度分析
冒泡排序的时间复杂度和空间复杂度如下 时间复杂度 最坏情况逆序比较和交换次数均为 n*(n-1)/2所以时间复杂度是 O(n^2)。最好情况已排序只需要进行 n-1 次比较所以时间复杂度是 O(n)。平均情况时间复杂度是 O(n^2)。 空间复杂度 冒泡排序是原地排序只需要一个额外空间用于临时交换元素所以空间复杂度是 O(1)。
冒泡排序的平均和最坏情况时间复杂度都是 O(n^2)空间复杂度是 O(1)。 3. 冒泡排序C语言代码
C代码
#include stdio.h void bubbleSort(int arr[], int n) { int i, j, temp; for (i 0; i n-1; i) { // 外层循环控制排序趟数 for (j 0; j n-i-1; j) { // 内层循环控制每一趟排序多少次 if (arr[j] arr[j1]) { // 如果前一个元素大于后一个元素交换它们的位置 temp arr[j]; arr[j] arr[j1]; arr[j1] temp; } } }
} int main() { int arr[] {64, 34, 25, 12, 22, 11, 90}; // 待排序的数组 int n sizeof(arr)/sizeof(arr[0]); // 数组的长度 bubbleSort(arr, n); // 对数组进行冒泡排序 printf(Sorted array: \n); for (int i0; i n; i) { // 输出排序后的数组 printf(%d , arr[i]); } printf(\n); return 0;
}
代码解释
bubbleSort 函数接收一个整数数组和它的长度作为参数。外层循环负责保证排序的趟数。例如有7个数字就需要排序6趟。内层循环负责每一趟中的具体比较和交换操作。每一次内层循环都会确保当前未排序部分的最大值移到正确的位置。当内层循环结束后最大的数已经被放到了正确的位置所以外层循环的每次迭代都会减少内层循环的次数。 4. 运行结果
代码运行结果
