数据结构&算法 冒泡排序



  • 冒泡排序

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

    我们以未排序的数组为例。冒泡排序需要O(n2)时间,因此我们将其保持简短而精确。
    bubblesort
    冒泡排序从头两个元素开始,然后比较它们以检查哪个更大。
    bubblesort
    在这种情况下,值33大于14,因此它已经在排序的位置。接下来,我们将33与27进行比较。
    bubblesort
    我们发现27小于33,并且必须交换这两个值。
    bubblesort
    新数组应如下所示:
    bubblesort
    接下来,我们将33和35进行比较。我们发现两者都已处于已排序的位置。
    bubblesort
    然后,我们移至下两个值35和10。
    bubblesort
    那么我们知道10比35小。因此,它们没有被排序。
    bubblesort
    我们交换这些值。我们发现已经到达数组的末尾。一次迭代后,数组应如下所示:
    bubblesort
    确切地说,我们现在显示每次迭代后数组的外观。在第二次迭代后,它应该看起来像这样-
    bubblesort
    请注意,每次迭代后,至少有一个值在末尾移动。
    bubblesort
    而且,当不需要交换时,冒泡排序会得知数组已完全排序。
    bubblesort
    现在我们应该研究冒泡排序的一些实际方面。
  • 算法

    我们假设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();
    }