冒泡排序

Coddy C++ 数组课程的第 13 课，共 26 课。

另一种数组排序方法叫做冒泡排序。它的思路是比较每一对相邻数字，如果右边的数字小于左边的数字，就交换它们，直到到达末尾。

1. 声明一个名为 counter 的变量，并将其初始化为 1。counter 用来记录已经排好序的元素数量。

2. 创建一个 while 循环，条件是 counter 小于 n 时继续迭代。

int counter=1;
while(counter<n){
     
}

3. 在 while 循环中创建一个 for 循环，让它从 0 迭代到 n-counter 次。因为 counter 个元素已经排好序，我们不需要再次检查它们。

int counter=1;
while(counter<n){
     for(int i=0;i<n-counter;i++){
     
     }
}

4. 然后比较第 i 个元素和它后面的元素，也就是第 (i+1) 个元素。如果 arr[i]>arr[i+1]，就交换它们。

我们可以看到，在外层 while 循环的第一次迭代中，最大的元素被推到了最后一个位置，因此下一次迭代时我们会忽略这部分，并将 counter 加 1。

int counter=1;
while(counter<n){
  for(int i=0;i<n-counter;i++){
    if(arr[i]>arr[i+1]){
      int temp=arr[i];
      arr[i]=arr[i+1];
      arr[i+1]=temp;
    }
  }
  counter++;
}

时间复杂度分析

我们运行 while 循环 n 次，每次 while 循环中，for 循环会运行近 n 次，因此时间复杂度为 O(n²)。

查看算法实际运行的逐步过程。

冒泡排序可视化工具

挑战

使用冒泡排序算法对给定的数组进行排序，并打印索引为奇数的所有元素。元素之间用一个空格分隔。

亲手试试

#include<iostream>
using namespace std;


int main(){
  
int n;
cin>>n;
int arr[n];
for(int i=0;i<n;i++){
  cin>>arr[i];
}

//Code Here




return 0;

}