冒泡排序

冒泡排序 首页 / 结构和算法入门教程 / 冒泡排序

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

冒泡排序

我们以未排序的数组为便,冒泡排序需要〇(n 2 )时间,因此我们将其简短而精确。

Bubble Sort

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

Bubble Sort

在这种情况下,值33大于14,因此它已经在排序的位置。接下来,我们将33与27进行比较。

Bubble Sort

我们发现27小于33,并且必须交换这两个值。

Bubble Sort

新数组应如下所示:

Bubble Sort

接下来,我们将33和35进行比较。我们发现两者都已处于已排序的位置。

Bubble Sort

然后,我们移至下两个值35和10。

Bubble Sort

那么我们知道10比35小。因此,它们没有被排序。

Bubble Sort

我们交换这些值,我们发现已经到达数组的末尾,一次迭代后,数组应如下所示:

Bubble Sort

确切地说,我们现在显示每次迭代后数组的外观,在第二次迭代后,它应该看起来像这样-

Bubble Sort

请注意,每次迭代后,至少有一个值在末尾移动。

Bubble Sort

而且,当不需要交换时,冒泡排序会得知数组已完全排序。

链接:https://www.learnfk.comhttps://www.learnfk.com/data-structures-algorithms/bubble-sort-algorithm.html

来源:LearnFk无涯教程网

Bubble Sort

现在我们应该研究气泡排序的一些实际方面。

算法

我们假设 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

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();
}
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 ]

祝学习愉快!(内容编辑有误?请选中要编辑内容 -> 右键 -> 修改 -> 提交!)

技术教程推荐

MySQL实战45讲 -〔林晓斌〕

Elasticsearch核心技术与实战 -〔阮一鸣〕

深入浅出云计算 -〔何恺铎〕

分布式数据库30讲 -〔王磊〕

陈天 · Rust 编程第一课 -〔陈天〕

林外 · 专利写作第一课 -〔林外〕

商业思维案例笔记 -〔曹雄峰〕

高并发系统实战课 -〔徐长龙〕

云原生架构与GitOps实战 -〔王炜〕

好记忆不如烂笔头。留下您的足迹吧 :)