设计与分析-冒泡排序

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

冒泡排序算法

冒泡排序是一种基本排序算法，其工作原理是在必要时重复交换相邻元素。当不需要交换时，文件被排序。

我们假设list是一个包含n 个元素的数组。我们进一步假设交换函数交换给定数组元素的值。

步骤 1 - 检查输入数组中的第一个元素是否大于数组中的下一个元素。

步骤 2 - 如果更大，则交换两个元素；否则将指针在数组中向前移动。

步骤 3 - 重复步骤 2，直到到达数组末尾。

步骤 4 - 检查元素是否已排序；如果不是，则从数组的最后一个元素到第一个元素重复相同的过程（步骤 1 到步骤 3）。

步骤 5 - 最终输出是排序后的数组。

Algorithm: Sequential-Bubble-Sort (A)
fori ← 1 to length [A] do
for j ← length [A] down-to i +1 do
   if A[A] < A[j-1] then
      Exchange A[j] ⟷ A[j-1]

伪代码

我们在算法中观察到，冒泡排序会比较每对数组元素，除非整个数组完全按升序排序。这可能会导致一些复杂性问题，例如如果数组不再需要交换，因为所有元素都已经升序了，该怎么办。

为了缓解这个问题，我们使用一个标志变量swapped，这将帮助我们查看是否发生了任何交换。如果没有发生交换，即数组不需要更多处理来排序，它将跳出循环。

冒泡排序算法的伪代码可以写成如下 -

voidbubbleSort(int numbers[], intarray_size){
   inti, j, temp;
   for (i = (array_size - 1); i>= 0; i--)
   for (j = 1; j <= i; j++)
   if (numbers[j-1] > numbers[j]){
      temp = numbers[j-1];
      numbers[j-1] = numbers[j];
      numbers[j] = temp;
   }
}

分析

这里，比较的次数是

       1 + 2 + 3 + ... + (n - 1) = n(n - 1)/2 = O(n2)

显然，该图显示了冒泡排序的n ^2性质。

在该算法中，比较的次数与数据集无关，即所提供的输入元素是按排序顺序、倒序还是随机的。

内存要求

从上面的算法可以看出，冒泡排序不需要额外的内存。

例子

我们以未排序的数组为例。冒泡排序需要 Ο(n2) 时间，因此我们保持简短且精确。

冒泡排序从前两个元素开始，比较它们以检查哪个元素更大。

在本例中，值 33 大于 14，因此它已经位于已排序的位置中。接下来，我们将 33 与 27 进行比较。

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

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

然后我们转向接下来的两个值：35 和 10。

我们知道 10 比 35 小。因此它们没有排序。我们交换这些值。我们发现已经到达了数组的末尾。一次迭代后，数组应如下所示 -

准确地说，我们现在展示的是每次迭代后数组应该是什么样子。第二次迭代后，它应该看起来像这样 -

请注意，每次迭代后，至少有一个值会在最后移动。

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

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

例子

我们在原始算法及其临时伪代码中没有解决的另一个问题是，每次迭代后，最高值都会落在数组的末尾。因此，下一次迭代不需要包含已经排序的元素。为此，在我们的实现中，我们限制内部循环以避免已经排序的值。

#include <stdio.h>
void bubbleSort(int array[], int size){
   for(int i = 0; i<size; i++) {
      int swaps = 0; //flag to detect any swap is there or not
      for(int j = 0; j<size-i-1; j++) {
         if(array[j] > array[j+1]) { //when the current item is bigger than next
            int temp;
            temp = array[j];
            array[j] = array[j+1];
            array[j+1] = temp;
            swaps = 1; //set swap flag
         }
      }
      if(!swaps)
         break; // No swap in this pass, so array is sorted
   }
}
int main(){
   int n;
   n = 5;
   int arr[5] = {67, 44, 82, 17, 20}; //initialize an array 
   printf("Array before Sorting: ");
   for(int i = 0; i<n; i++)
      printf("%d ",arr[i]);
   printf("\n");
   bubbleSort(arr, n);
   printf("Array after Sorting: ");
   for(int i = 0; i<n; i++)
      printf("%d ", arr[i]);
   printf("\n");
}

Array before Sorting: 67 44 82 17 20 
Array after Sorting: 17 20 44 67 82 

#include<iostream>
using namespace std;
void bubbleSort(int *array, int size){
   for(int i = 0; i<size; i++) {
      int swaps = 0; //flag to detect any swap is there or not
      for(int j = 0; j<size-i-1; j++) {
         if(array[j] > array[j+1]) { //when the current item is bigger than next
            int temp;
            temp = array[j];
            array[j] = array[j+1];
            array[j+1] = temp;
            swaps = 1; //set swap flag
         }
      }
      if(!swaps)
         break; // No swap in this pass, so array is sorted
   }
}
int main(){
   int n;
   n = 5;
   int arr[5] = {67, 44, 82, 17, 20}; //initialize an array
   cout << "Array before Sorting: ";
   for(int i = 0; i<n; i++)
      cout << arr[i] << " ";
   cout << endl;
   bubbleSort(arr, n);
   cout << "Array after Sorting: ";
   for(int i = 0; i<n; i++)
      cout << arr[i] << " ";
   cout << endl;
}

Array before Sorting: 67 44 82 17 20 
Array after Sorting: 17 20 44 67 82

import java.io.*;
import java.util.*;
public class BubbleSort {
   public static void main(String args[]) {
      int n = 5;
      int[] arr = {67, 44, 82, 17, 20}; //initialize an array
      System.out.print("Array before Sorting: ");
      for(int i = 0; i<n; i++)
         System.out.print(arr[i] + " ");
      System.out.println();
      for(int i = 0; i<n; i++) {
         int swaps = 0; //flag to detect any swap is there or not
         for(int j = 0; j<n-i-1; j++) {
            if(arr[j] > arr[j+1]) { //when the current item is bigger than next
               int temp;
               temp = arr[j];
               arr[j] = arr[j+1];
               arr[j+1] = temp;
               swaps = 1; //set swap flag
            }
         }
         if(swaps == 0)
            break;
      }
      System.out.print("Array After Sorting: ");
      for(int i = 0; i<n; i++)
         System.out.print(arr[i] + " ");
      System.out.println();
   }
}

Array before Sorting: 67 44 82 17 20 
Array After Sorting: 17 20 44 67 82

def bubble_sort(array, size):
   for i in range(size):
      swaps = 0;
      for j in range(0, size-i-1):
         if(arr[j] > arr[j+1]):
            temp = arr[j];
            arr[j] = arr[j+1];
            arr[j+1] = temp;
            swaps = 1;
      if(swaps == 0):
         break;

arr = [67, 44, 82, 17, 20]
n = len(arr)
print("Array before Sorting: ")
print(arr)
bubble_sort(arr, n);
print("Array after Sorting: ")
print(arr)

Array before Sorting: 
[67, 44, 82, 17, 20]
Array after Sorting: 
[17, 20, 44, 67, 82]