实现冒泡排序的 C++ 程序

冒泡排序是基于比较的排序算法。在该算法中，相邻元素被比较并交换以形成正确的序列。该算法比其他算法简单，但也有一些缺点。该算法不适用于大量数据集。解决排序任务需要很多时间。

冒泡排序技术的复杂性

• 时间复杂度：O(n)对于最好的情况，O(n ² ) 对于平均和最坏的情况

• 空间复杂度：O(1)

Input − A list of unsorted data: 56 98 78 12 30 51
Output − 排序后的数组： 12 30 51 56 78 98

算法

bubbleSort(array, size)

输入：一个数据数组，以及数组中的总数

输出：排序后的数组

Begin
   for i := 0 to size-1 do
      flag := 0;
      for j:= 0 to size –i – 1 do
         if array[j] > array[j+1] then
            swap array[j] with array[j+1]
            flag := 1
      done
      if flag ≠ 1 then
         break the loop.
   done
End

示例代码

#include<iostream>
using namespace std;
void swapping(int &a, int &b) {      //交换 a 和 b 的内容
   int temp;
   temp = a;
   a = b;
   b = temp;
}
void display(int *array, int size) {
   for(int i = 0; i<size; i++)
      cout << array[i] << " ";
   cout << endl;
}
void bubbleSort(int *array, int size) {
   for(int i = 0; i<size; i++) {
      int swaps = 0;         //检测任何交换的标志是否存在
      for(int j = 0; j<size-i-1; j++) {
         if(array[j] > array[j+1]) {       //当前项大于下一项时
            swapping(array[j], array[j+1]);
            swaps = 1;    //设置交换标志
         }
      }
      if(!swaps)
         break;       // 此传递中没有交换，因此数组已排序
   }
}
int main() {
   int n;
   cout << "输入元素数量： ";
   cin >> n;
   int arr[n];     //创建具有给定元素数量的数组
   cout << "输入元素：" << endl;
   for(int i = 0; i<n; i++) {
      cin >> arr[i];
   }
   cout << "排序前的数组： ";
   display(arr, n);
   bubbleSort(arr, n);
   cout << "排序后的数组： ";
   display(arr, n);
}

输入元素数量： 6
输入元素：
56 98 78 12 30 51
排序前的数组： 56 98 78 12 30 51
排序后的数组： 12 30 51 56 78 98