冒泡排序

冻土区土壤的冒泡现象

简介

冒泡排序动态展示

冒泡排序是一种简单的朴素的排序算法，像自然界中很多冒泡现象一样，在气泡上升的过程中，会逐渐变大，所以气泡从下到上会呈现出从小到大基本有序的场景。

冒泡排序每一轮会找出一个集合中的最大值，然后将该最大值放于集合的尾部。

当最大值的位置确定之后，下一轮会找出集合中剩余数据的次大值，然后放在上一轮最大值前面的位置。

以此类推，直到所有的值从从大到小都放在了正确的位置。

流程

• 假如一个数据量为n的数据集，需要从小到大进行排序，冒泡排序需要循环n轮。
  • 每一轮循环找出剩余元素中的最大值，然后放在未排序集合的最后位置，例如第一轮找出全局的最大值，放在第n-1位，那么最后一位是已经排好序的，下一轮找出剩余n-1个元素的最大值，之后放在第n-2的位置。以此类推。
  • 每一轮找最大值的过程，也是一轮循环，从前到后，将当前的最大值和当前值比较，如果当前值比最大值大，则将当前值和最大值交互，这一轮循环的过程中，最大值始终位于已经比较过的集合的最后位置。

实现

#include <iostream>
using namespace std;
  
const int maxSize = 20;
  
// 冒泡排序:从小到大排序
template <class T>
void BubbleSort(T arr[], int n) {
  int i, j, flag;
  T temp;
   
  for(i = 0; i < n-1; i++) { // 进行n-1次
    flag = 0; // 交换标志，0表示无交换，1表示有交换
    for(j = 0; j < (n-i-1); j++) { // 数组下标最大为n-1
      if(arr[j] > arr[j+1]) { // 逆序就交换
        flag = 1; // 有交换
        temp = arr[j];
        arr[j] = arr[j+1];
        arr[j+1] = temp;
      }
    }
    if(flag == 0) // 无交换,说明已经全部排好序，提前结束
      break;
  } // for
} // BubbleSort
  
int main(int argc, const char * argv[]) {
  int i, n, arr[maxSize];
   
  cout << "请输入要排序的数的个数：";
  cin >> n;
  cout << "请输入要排序的数：";
  for(i = 0; i < n; i++)
    cin >> arr[i];
  cout << "排序前：" << endl;
  for(i = 0; i < n; i++)
    cout << arr[i] << " ";
  cout << endl;
  BubbleSort(arr, n);
  cout << "排序后：" << endl;
  for(i = 0; i < n; i++)
    cout << arr[i] << " ";
  cout << endl;
  return 0;
}