起泡排序算法
Bubble Sort is a simple algorithm which is used to sort a given set of n elements provided in form of an array with n number of elements. Bubble Sort compares all the element one by one and sort them based on their values.
冒泡排序是一个简单的算法，其用于一组给定的排序n在与阵列的形式提供要素n元素的个数。 Bubble Sort会一一比较所有元素，然后根据它们的值对它们进行排序。
If the given array has to be sorted in ascending order, then bubble sort will start by comparing the first element of the array with the second element, if the first element is greater than the second element, it will swap both the elements, and then move on to compare the second and the third element, and so on.
如果给定数组必须按升序排序，则冒泡排序将通过将数组的第一个元素与第二个元素进行比较来开始，如果第一个元素大于第二个元素，它将交换两个元素，然后继续比较第二个和第三个元素，依此类推。
If we have total n elements, then we need to repeat this process for n-1 times.
如果总共有n元素，则需要重复此过程n-1次。
It is known as bubble sort, because with every complete iteration the largest element in the given array, bubbles up towards the last place or the highest index, just like a water bubble rises up to the water surface.
之所以称为气泡排序 ，是因为在每次完整迭代中，给定数组中的最大元素都会将气泡向上气泡到最后一个位置或指向最高索引，就像气泡上升到水面一样。
Sorting takes place by stepping through all the elements one-by-one and comparing it with the adjacent element and swapping them if required.
排序是通过一步一步地遍历所有元素并将其与相邻元素进行比较，并在需要时进行交换来进行的。
实现冒泡排序算法 (Implementing Bubble Sort Algorithm)
Following are the steps involved in bubble sort(for sorting a given array in ascending order):
以下是气泡排序所涉及的步骤(用于按给定的数组升序排序)：
Starting with the first element(index = 0), compare the current element with the next element of the array.
从第一个元素(索引= 0)开始，将当前元素与数组的下一个元素进行比较。
If the current element is greater than the next element of the array, swap them.
如果当前元素大于数组的下一个元素，请交换它们。
If the current element is less than the next element, move to the next element. Repeat Step 1.
如果当前元素小于下一个元素，则移至下一个元素。 重复步骤1 。
Let's consider an array with values {5, 1, 6, 2, 4, 3}
让我们考虑一个值为{5, 1, 6, 2, 4, 3} 5，1，6，2，4，4，3 {5, 1, 6, 2, 4, 3}的数组
Below, we have a pictorial representation of how bubble sort will sort the given array.
下面，我们用图形表示了气泡排序如何对给定数组进行排序。
So as we can see in the representation above, after the first iteration, 6 is placed at the last index, which is the correct position for it.
因此，如上图所示，在第一次迭代之后，将6放置在最后一个索引处，这是它的正确位置。
Similarly after the second iteration, 5 will be at the second last index, and so on.
类似地，在第二次迭代之后， 5将位于倒数第二个索引，依此类推。
Time to write the code for bubble sort:
是时候编写气泡排序代码了：
// below we have a simple C program for bubble sort
#include <stdio.h>
void bubbleSort(int arr[], int n)
{
int i, j, temp;
for(i = 0; i < n; i++)
{
for(j = 0; j < n-i-1; j++)
{
if( arr[j] > arr[j+1])
{
// swap the elements
temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
// print the sorted array
printf("Sorted Array: ");
for(i = 0; i < n; i++)
{
printf("%d ", arr[i]);
}
}
int main()
{
int arr[100], i, n, step, temp;
// ask user for number of elements to be sorted
printf("Enter the number of elements to be sorted: ");
scanf("%d", &n);
// input elements if the array
for(i = 0; i < n; i++)
{
printf("Enter element no. %d: ", i+1);
scanf("%d", &arr[i]);
}
// call the function bubbleSort
bubbleSort(arr, n);
return 0;
}Although the above logic will sort an unsorted array, still the above algorithm is not efficient because as per the above logic, the outer for loop will keep on executing for 6 iterations even if the array gets sorted after the second iteration.
尽管以上逻辑将对未排序的数组进行排序，但上述算法仍然无效，因为按照上述逻辑，即使数组在第二次迭代后进行了排序，外部for循环仍将继续执行6次迭代。
So, we can clearly optimize our algorithm.
因此，我们可以清楚地优化算法。
优化的冒泡排序算法 (Optimized Bubble Sort Algorithm)
To optimize our bubble sort algorithm, we can introduce a flag to monitor whether elements are getting swapped inside the inner for loop.
为了优化气泡排序算法，我们可以引入一个flag来监视元素是否在内部for循环内被交换。
Hence, in the inner for loop, we check whether swapping of elements is taking place or not, everytime.
因此，在内部for循环中，我们每次都会检查是否发生元素交换。
If for a particular iteration, no swapping took place, it means the array has been sorted and we can jump out of the for loop, instead of executing all the iterations.
如果对于特定的迭代没有发生交换，则意味着该数组已排序，我们可以跳出for循环，而不是执行所有迭代。
Let's consider an array with values {11, 17, 18, 26, 23}
让我们考虑一个值{11, 17, 18, 26, 23}的数组
Below, we have a pictorial representation of how the optimized bubble sort will sort the given array.
下面，我们以图形方式表示优化的气泡排序将如何对给定数组进行排序。
As we can see, in the first iteration, swapping took place, hence we updated our flag value to 1, as a result, the execution enters the for loop again. But in the second iteration, no swapping will occur, hence the value of flag will remain 0, and execution will break out of loop.
如我们所见，在第一次迭代中，发生了交换，因此我们将flag值更新为1 ，结果是执行再次进入for循环。 但是在第二次迭代中，不会发生交换，因此flag的值将保持为0 ，并且执行将跳出循环。
// below we have a simple C program for bubble sort
#include <stdio.h>
void bubbleSort(int arr[], int n)
{
int i, j, temp, flag=0;
for(i = 0; i < n; i++)
{
for(j = 0; j < n-i-1; j++)
{
// introducing a flag to monitor swapping
if( arr[j] > arr[j+1])
{
// swap the elements
temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
// if swapping happens update flag to 1
flag = 1;
}
}
// if value of flag is zero after all the iterations of inner loop
// then break out
if(flag==0)
{
break;
}
}
// print the sorted array
printf("Sorted Array: ");
for(i = 0; i < n; i++)
{
printf("%d ", arr[i]);
}
}
int main()
{
int arr[100], i, n, step, temp;
// ask user for number of elements to be sorted
printf("Enter the number of elements to be sorted: ");
scanf("%d", &n);
// input elements if the array
for(i = 0; i < n; i++)
{
printf("Enter element no. %d: ", i+1);
scanf("%d", &arr[i]);
}
// call the function bubbleSort
bubbleSort(arr, n);
return 0;
}In the above code, in the function bubbleSort, if for a single complete cycle of j iteration(inner for loop), no swapping takes place, then flag will remain 0 and then we will break out of the for loops, because the array has already been sorted.
在上面的代码中，在bubbleSort函数中，如果对于j迭代的一个完整周期(内部for循环)没有交换发生，则flag将保持为0 ，然后我们将退出for循环，因为数组具有已经排序。
气泡排序的复杂度分析 (Complexity Analysis of Bubble Sort)
In Bubble Sort, n-1 comparisons will be done in the 1st pass, n-2 in 2nd pass, n-3 in 3rd pass and so on. So the total number of comparisons will be,
在冒泡排序中， n-1比较将在第一遍中进行， n-2在第二遍中进行， n-3在第三遍中进行，依此类推。 这样比较的总数将是
(n-1) + (n-2) + (n-3) + ..... + 3 + 2 + 1 Sum = n(n-1)/2 i.e O(n2)
(n-1)+(n-2)+(n-3)+ ..... + 3 + 2 +1总和= n(n-1)/ 2，即O(n 2 )
Hence the time complexity of Bubble Sort is O(n2).
因此，冒泡排序的时间复杂度为O(n 2 ) 。
The main advantage of Bubble Sort is the simplicity of the algorithm.
冒泡排序的主要优点是算法简单。
The space complexity for Bubble Sort is O(1), because only a single additional memory space is required i.e. for temp variable.
Bubble Sort的空间复杂度为O(1) ，因为仅需要一个额外的存储空间，即temp变量。
Also, the best case time complexity will be O(n), it is when the list is already sorted.
同样， 最佳情况下的时间复杂度将是O(n) ，即列表已经排序的时间。
Following are the Time and Space complexity for the Bubble Sort algorithm.
以下是冒泡排序算法的时间和空间复杂度。
Worst Case Time Complexity [ Big-O ]: O(n2)
最坏情况下的时间复杂度[Big-O]： O(n 2 )
Best Case Time Complexity [Big-omega]: O(n)
最佳情况下的时间复杂度[大Ω]： O(n)
Average Time Complexity [Big-theta]: O(n2)
平均时间复杂度[Big-theta]： O(n 2 )
Space Complexity: O(1)
空间复杂度： O(1)
翻译自: https://www.studytonight.com/data-structures/bubble-sort
起泡排序算法