当使用大型数据库时，有必要添加功能以搜索值或者从一系列项目中找到最高或者最低值。
冒泡排序算法是一种简化算法。

气泡排序算法是一种排序技术，可帮助以简单有效的方式对元素进行排序。
使用冒泡排序，可以按升序/降序对元素进行排序。

冒泡排序会在相邻元素之间进行比较，如果元素未按定义的顺序(升序或者降序)进行交换，则将它们交换。

冒泡排序算法

• 从第一个元素开始，即position = 0，然后将其与该特定数组的下一个元素进行比较。

• 如果要比较的元素大于下一个元素，则需要交换这些元素。

• 如果要比较的元素小于下一个元素，请移至下一个位置以检查另一个元素。

• 重复步骤1-3，直到所有元素都以升序或者降序排序。

逻辑：

bubble_sort(input_array)
for x <- 1 to index_of_last_element-1
  if left_element > right_element
    swap left_element and right_element
end bubble_sort

冒泡排序算法的工作

让我们借助示例了解冒泡排序算法的工作原理。

我们的任务是按升序对元素进行排序。

因此，我们将从第一个元素(即位置0的元素)开始，并将其与第二个(相邻)元素进行比较。
如果第一个元素大于后一个元素，则将它们交换。

此外，重复相同的过程，直到访问或者遍历数组的所有元素为止。

注意：在冒泡排序中，如果数组包含N个元素，则它将执行N次迭代。

考虑元素10、7、20，-1。

迭代1：

冒泡排序算法迭代1

当i = 0时，将第一个元素(10)与第二个元素(7)比较。
由于10> 7，将交换它们并更新阵列。

使过程前进，即i ＝ 1，将第二元素(10)与第三元素(20)进行比较。
由于10不大于20，它们将保留其在数组中的位置。

当i = 2时，将20与-1比较。
由于20> -1，它们被交换。

迭代2：

冒泡排序算法迭代2

在第二次迭代中，将7与10进行比较。
由于7不大于10，因此它们保留其位置。

此外，将10与-1比较。
当10> -1时，它们被交换并更新阵列。

然后，将10与20交换。
由于10不大于20，它们将保留在数组中的位置。

迭代3：

冒泡排序算法迭代3

在第三次迭代中，将7与-1比较。
由于7> -1，它们将被交换并更新阵列。

然后，将7与10进行比较。
由于7不大于20，因此它们保持其位置。

此外，将10与20进行比较。
由于10不大于20，它们将保留其在数组中的位置。

现在大家都可以看到，数组已经排序。
但是，如上所述，对于每n个元素，冒泡排序都会执行n次迭代。

因此，在此示例中，对于4个元素，它将执行4次迭代。

迭代4：

冒泡排序算法迭代4

输入：10、7、20，-1

输出：-1，7，10，20

在C中实现冒泡排序

#include <stdio.h>
void bubble(int arr[], int size) {
  int temp=0;
  for (int i = 0; i < size; i++) {   
      for (int j = 0; j < size - i - 1; j++) { //elements excluding the sorted ones
          if (arr[j] > arr[j + 1]) {  
              temp = arr[j];
              arr[j] = arr[j + 1];
              arr[j + 1] = temp;
          }
      }
  }
}
int main() {
int arr[100], size;

printf("Enter the count of elements of the array:\n");
scanf("%d", &size); 

printf("Enter the elements:\n");
for (int i = 0; i < size; i++)
  scanf("%d", &arr[i]);

bubble(arr, size);

printf("The sorted array:\n");
for (int i = 0; i < size; i++)
   printf("%d\n", arr[i]);

return 0;
}

输出：

Enter the count of elements of the array:
4
Enter the elements:
10
7
20
-1
The sorted array:
-1
7
10
20

优化算法

如上所示，即使在第三次迭代后获得排序后的数组，气泡排序仍会重复n次。
这些结果提供了较差的代码效率。

因此，为了提高效率并优化代码，我们在"内部循环"上设置一个"变量"元素，以检查在特定的迭代过程中元素是否被交换。

因此，如果在特定的迭代中没有发生元素交换，我们可以简单地移出" for循环"，而不必为所有迭代执行。

让我们考虑以上示例。

输入：10、7、20，-1

我们将设置一个变量元素，比方说检查内部循环。

如上所述，在第四次迭代中没有元素被交换。
因此，inspect的值= 0，我们将退出循环。

优化气泡排序算法的C语言实现

例：

#include <stdio.h>
void bubble(int arr[], int size) {
  int inspect,temp=0;
  for (int i = 0; i < size; i++) {   
      for (int j = 0; j < size - i - 1; j++) {
//variable to monitor the swapping of elements in the inner loop
      inspect = 0;
          
          if (arr[j] > arr[j + 1]) {  
              temp = arr[j];
              arr[j] = arr[j + 1];
              arr[j + 1] = temp;
       //set inspect = 1, if they function witness swap of elements
             inspect = 1; 
 }
      }
//if the value of inspect continues to stay zero after all of the 
//iterations of the inner loop, then move out of the loop
      if(!inspect)
      {
          break;
      }
  }
}
int main() {
int arr[100], size;

printf("Enter the count of elements of the array:\n");
scanf("%d", &size); 

printf("Enter the elements:\n");
for (int i = 0; i < size; i++)
  scanf("%d", &arr[i]);

bubble(arr, size);

printf("The sorted array:\n");
for (int i = 0; i < size; i++)
   printf("%d\n", arr[i]);

return 0;
}

输出：

Enter the count of elements of the array:
4
Enter the elements:
10
7
20
-1
The sorted array:
-1
7
10
20

气泡排序的复杂度分析

最佳情况下时间复杂度：O(n ^ 2)

空间复杂度：O(1)