冒泡排序是一种简单的排序算法,该排序算法是基于比较的算法,其中比较每对相邻元素,如果元素不按顺序交换。该算法不适用于大型数据集,因为其平均和最坏情况下的复杂度为Ο(n 2 ),其中 n 是元素。
我们以未排序的数组为便,冒泡排序需要〇(n 2 )时间,因此我们将其简短而精确。
冒泡排序从头两个元素开始,然后比较它们以检查哪个更大。
在这种情况下,值33大于14,因此它已经在排序的位置。接下来,我们将33与27进行比较。
我们发现27小于33,并且必须交换这两个值。
新数组应如下所示:
接下来,我们将33和35进行比较。我们发现两者都已处于已排序的位置。
然后,我们移至下两个值35和10。
那么我们知道10比35小。因此,它们没有被排序。
我们交换这些值,我们发现已经到达数组的末尾,一次迭代后,数组应如下所示:
确切地说,我们现在显示每次迭代后数组的外观,在第二次迭代后,它应该看起来像这样-
请注意,每次迭代后,至少有一个值在末尾移动。
而且,当不需要交换时,冒泡排序会得知数组已完全排序。
链接:https://www.learnfk.comhttps://www.learnfk.com/data-structures-algorithms/bubble-sort-algorithm.html
来源:LearnFk无涯教程网
现在我们应该研究气泡排序的一些实际方面。
我们假设 list 是 n 个元素的数组。我们进一步假设 swap 函数交换给定数组元素的值。
begin BubbleSort(list) for all elements of list if list[i] > list[i+1] swap(list[i], list[i+1]) end if end for return list end BubbleSort
#include <stdio.h> #include <stdbool.h> #define MAX 10 int list[MAX] = {1,8,4,6,0,3,5,2,7,9}; void display() { int i; printf("["); // navigate through all items for(i = 0; i < MAX; i++) { printf("%d ",list[i]); } printf("]\n"); } void bubbleSort() { int temp; int i,j; bool swapped = false; // loop through all numbers for(i = 0; i < MAX-1; i++) { swapped = false; // loop through numbers falling ahead for(j = 0; j < MAX-1-i; j++) { printf(" Items compared: [ %d, %d ] ", list[j],list[j+1]); // check if next number is lesser than current no // swap the numbers. // (Bubble up the highest number) if(list[j] > list[j+1]) { temp = list[j]; list[j] = list[j+1]; list[j+1] = temp; swapped = true; printf(" => swapped [%d, %d]\n",list[j],list[j+1]); } else { printf(" => not swapped\n"); } } // if no number was swapped that means // array is sorted now, break the loop. if(!swapped) { break; } printf("Iteration %d#: ",(i+1)); display(); } } void main() { printf("Input Array: "); display(); printf("\n"); bubbleSort(); printf("\nOutput Array: "); display(); }
Input Array: [1 8 4 6 0 3 5 2 7 9 ] Items compared: [ 1, 8 ] => not swapped Items compared: [ 8, 4 ] => swapped [4, 8] Items compared: [ 8, 6 ] => swapped [6, 8] Items compared: [ 8, 0 ] => swapped [0, 8] Items compared: [ 8, 3 ] => swapped [3, 8] Items compared: [ 8, 5 ] => swapped [5, 8] Items compared: [ 8, 2 ] => swapped [2, 8] Items compared: [ 8, 7 ] => swapped [7, 8] Items compared: [ 8, 9 ] => not swapped Iteration 1#: [1 4 6 0 3 5 2 7 8 9 ] Items compared: [ 1, 4 ] => not swapped Items compared: [ 4, 6 ] => not swapped Items compared: [ 6, 0 ] => swapped [0, 6] Items compared: [ 6, 3 ] => swapped [3, 6] Items compared: [ 6, 5 ] => swapped [5, 6] Items compared: [ 6, 2 ] => swapped [2, 6] Items compared: [ 6, 7 ] => not swapped Items compared: [ 7, 8 ] => not swapped Iteration 2#: [1 4 0 3 5 2 6 7 8 9 ] Items compared: [ 1, 4 ] => not swapped Items compared: [ 4, 0 ] => swapped [0, 4] Items compared: [ 4, 3 ] => swapped [3, 4] Items compared: [ 4, 5 ] => not swapped Items compared: [ 5, 2 ] => swapped [2, 5] Items compared: [ 5, 6 ] => not swapped Items compared: [ 6, 7 ] => not swapped Iteration 3#: [1 0 3 4 2 5 6 7 8 9 ] Items compared: [ 1, 0 ] => swapped [0, 1] Items compared: [ 1, 3 ] => not swapped Items compared: [ 3, 4 ] => not swapped Items compared: [ 4, 2 ] => swapped [2, 4] Items compared: [ 4, 5 ] => not swapped Items compared: [ 5, 6 ] => not swapped Iteration 4#: [0 1 3 2 4 5 6 7 8 9 ] Items compared: [ 0, 1 ] => not swapped Items compared: [ 1, 3 ] => not swapped Items compared: [ 3, 2 ] => swapped [2, 3] Items compared: [ 3, 4 ] => not swapped Items compared: [ 4, 5 ] => not swapped Iteration 5#: [0 1 2 3 4 5 6 7 8 9 ] Items compared: [ 0, 1 ] => not swapped Items compared: [ 1, 2 ] => not swapped Items compared: [ 2, 3 ] => not swapped Items compared: [ 3, 4 ] => not swapped Output Array: [0 1 2 3 4 5 6 7 8 9 ]
祝学习愉快!(内容编辑有误?请选中要编辑内容 -> 右键 -> 修改 -> 提交!)