数据结构&算法冒泡排序

冒泡排序

冒泡排序是一种简单的排序算法。该排序算法是基于比较的算法，其中比较每对相邻元素，如果元素不按顺序交换。该算法不适用于大型数据集，因为其平均和最坏情况下的复杂度为Ο(n²)，其中n是项数。

冒泡排序如何工作？

我们以未排序的数组为例。冒泡排序需要O(n²)时间，因此我们将其保持简短而精确。

冒泡排序从头两个元素开始，然后比较它们以检查哪个更大。

在这种情况下，值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();
}

尝试一下

数据结构&算法 冒泡排序

冒泡排序

冒泡排序如何工作？

算法

伪码

实现

数据结构&算法冒泡排序