起泡排序算法

When working with large databases, it is necessary to add the functionality to search for values or find the highest or lowest values from a range of items. The Bubble Sort Algorithm is an algorithm that facilitates just that.

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

Bubble Sort Algorithm is a sorting technique that assists with sorting the elements in a simple and efficient manner. Using bubble sort, elements can be sorted in ascending/descending order.

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

Bubble sort makes a comparison between the adjacent elements and swaps the elements if they are not in a defined order (either ascending or descending).

冒泡排序会在相邻元素之间进行比较，并在相邻元素未按定义顺序（升序或降序）时进行交换。

---

---

冒泡排序算法 (The Bubble Sort Algorithm)

1. Initiate with the first element i.e. position = 0, and compare it with the next element of that particular array.
   从第一个元素（即position = 0）开始，然后将其与该特定数组的下一个元素进行比较。
2. If the element to be compared is greater than the next element, then we need to swap the elements.
   如果要比较的元素大于下一个元素，则需要交换元素。
3. If the element to be compared is smaller than the next element, move to the next position to check for another element. 
   如果要比较的元素小于下一个元素，请移至下一个位置以检查另一个元素。
4. Repeat Step 1 – 3 until all the elements get sorted in an ascending or descending fashion.
   重复步骤1-3 ，直到所有元素都以升序或降序排序。

Logic:

逻辑：

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

---

---

冒泡排序算法的工作 (Working of Bubble Sort Algorithm)

Let’s understand how the Bubble Sort algorithm works with the help of an example.

让我们借助示例了解Bubble Sort算法的工作方式。

Our task is to sort the elements in ascending order.

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

So, we will start from the first element i.e. element at position 0 and compare it with the second (adjacent) element. If the first element is greater than the latter element, they are swapped.

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

Further, the same process is repeated until all the elements of the array are visited or traversed.

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

Note: In Bubble sort, if the array contains N elements, then it would perform N iterations.

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

Consider the elements 10, 7, 20, -1.

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

Iteration 1:

迭代1：

When i=0, the first element(10) is compared with the second element(7). Since 10 > 7, they are swapped and the array is updated.

当i = 0时，将第一个元素（10）与第二个元素（7）比较。 从10> 7开始，将交换它们并更新数组。

Taking the process ahead i.e. i=1, the second element(10) is compared with the third element(20). Since 10 is not greater than 20, they retain their positions in the array.

将过程提前，即i = 1，将第二个元素（10）与第三个元素（20）进行比较。 由于10不大于20，它们将保留在数组中的位置。

When i=2, 20 is compared with -1. Since 20 > -1,they are swapped.

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

Iteration 2:

迭代2：

In the second iteration, 7 is compared with 10. Since 7 is not greater than 10, they retain their positions.

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

Further, 10 is compared with -1. As 10 > -1, they are swapped and the array is updated.

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

Then, 10 is swapped with 20. Since 10 is not greater than 20, they retain their positions in the array.

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

Iteration 3:

迭代3：

In the third iteration, 7 is compared with -1. Since 7 > -1, they are swapped and the array is updated.

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

Then, 7 is compared with 10. As 7 is not greater than 20, they retain their positions.

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

Further, 10 is compared with 20. Since 10 is not greater than 20, they retain their positions in the array.

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

Now as you all can witness, the array has been sorted. But, as mentioned above, for every n elements, bubble sort performs n iterations.

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

Therefore, in this example, for 4 elements it will perform 4 iterations.

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

Iteration 4:

迭代4：

Input: 10, 7, 20, -1

输入：10、7、20，-1

Output: -1, 7, 10, 20

输出：-1，7，10，20

---

---

C语言中冒泡排序的实现 (Implementation of Bubble Sort in C)

#include 
    
     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;}
    

Output:

输出：

Enter the count of elements of the array:4Enter the elements:10720-1The sorted array:-171020

---

---

优化算法 (Optimized Algorithm)

As seen above, even after getting the sorted array at third iteration, bubble sort continues to iterate n times. These results provide poor efficiency of code.

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

Thus to improve the efficiency and optimize the code, let’s set a variable element on the inner loop to check whether the elements get swapped or not during a particular iteration process.

因此，为了提高效率和优化代码，让我们在inner loop上设置一个variable元素，以检查在特定的迭代过程中这些元素是否被交换。

Thus, if at a particular iteration no swapping of elements occur, we can simply move out of the for loop instead of having to execute for all the iterations.

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

Let’s consider the above example.

让我们考虑以上示例。

Input: 10, 7, 20, -1

输入：10、7、20，-1

We will set a variable element, let’s say inspect to the inner loop.

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

As witnessed above, no elements get swapped in the fourth iteration. Thus, the value of inspect = 0 and we will break out from the loop.

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

---

---

优化气泡排序算法的C语言实现 (Implementation of Optimized Bubble Sort Algorithm in C)

Example:

例：

#include 
    
     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;}
    

Output:

输出：

Enter the count of elements of the array:4Enter the elements:10720-1The sorted array:-171020

---

---

气泡排序的复杂度分析 (Complexity Analysis of Bubble Sort)

Best Case Time Complexity: O(n^2)

最佳情况时间复杂度 ：O（n ^ 2）

Space Complexity: O(1)

空间复杂度： O（1）

---

---

结论 (Conclusion)

Thus, in this article, we have had a look at bubble sort and its working. Furthermore, we optimized the algorithm and learned its implementation in the .

因此，在本文中，我们研究了气泡排序及其工作原理。 此外，我们优化了算法，并学习了用实现的算法。

翻译自:

起泡排序算法