数据结构&算法 冒泡排序
-
冒泡排序
冒泡排序是一种简单的排序算法。该排序算法是基于比较的算法,其中比较每对相邻元素,如果元素不按顺序交换。该算法不适用于大型数据集,因为其平均和最坏情况下的复杂度为Ο(n2),其中n是项数。 -
冒泡排序如何工作?
我们以未排序的数组为例。冒泡排序需要O(n2)时间,因此我们将其保持简短而精确。冒泡排序从头两个元素开始,然后比较它们以检查哪个更大。在这种情况下,值33大于14,因此它已经在排序的位置。接下来,我们将33与27进行比较。我们发现27小于33,并且必须交换这两个值。新数组应如下所示:接下来,我们将33和35进行比较。我们发现两者都已处于已排序的位置。然后,我们移至下两个值35和10。那么我们知道10比35小。因此,它们没有被排序。我们交换这些值。我们发现已经到达数组的末尾。一次迭代后,数组应如下所示:确切地说,我们现在显示每次迭代后数组的外观。在第二次迭代后,它应该看起来像这样-请注意,每次迭代后,至少有一个值在末尾移动。而且,当不需要交换时,冒泡排序会得知数组已完全排序。现在我们应该研究冒泡排序的一些实际方面。 -
算法
我们假设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
-
伪码
我们在算法中观察到,冒泡排序会比较每对数组元素,除非整个数组完全按照升序排序。这可能会引起一些复杂性问题,例如如果数组不再需要交换(因为所有元素都已经升序),该怎么办。为了解决此问题,我们使用了一个标志变量swapped,该变量将帮助我们查看是否发生了任何交换。如果没有发生交换,即该数组不需要排序更多的处理,它将退出循环。BubbleSort算法的伪代码可以编写如下-procedure bubbleSort( list : array of items ) loop = list.count; for i = 0 to loop-1 do: swapped = false for j = 0 to loop-1 do: /* compare the adjacent elements */ if list[j] > list[j+1] then /* swap them */ swap( list[j], list[j+1] ) swapped = true end if end for /*if no number was swapped that means array is sorted now, break the loop.*/ if(not swapped) then break end if end for end procedure return list
-
实现
我们在原始算法及其临时的伪代码中未解决的另一个问题是,每次迭代后,最高值都将落在数组的末尾。因此,下一次迭代不需要包括已经排序的元素。为此,在我们的实现中,我们限制内部循环以避免已排序的值。以下是C语言的实现
尝试一下#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(); }