Démonstration animée du tri à bulles

冒泡排序 是最简单的排序算法，如果相邻元素的顺序错误，它的工作原理是重复交换相邻元素。该算法不适合大型数据集，因为其平均和最坏情况时间复杂度相当高。

冒泡排序算法

在这个算法中，

从左侧遍历，比较相邻元素，较高的放在右侧。

这样，最大的元素首先被移动到最右端。

然后继续这个过程，找到第二大的并放置它，依此类推，直到数据排序完毕。

冒泡排序是如何工作的？

让我们借助下图来了解冒泡排序的工作原理：

输入： arr[] = {6, 3, 0, 5}

第一关：

最大的元素被放置在正确的位置，即数组的末尾。

冒泡排序算法：将最大的元素放在正确的位置

第二遍：

将第二大元素放在正确的位置

冒泡排序算法：将第二大元素放在正确的位置

第三遍：

将其余两个元素放置在正确的位置。

冒泡排序算法：将剩余元素放置在正确的位置

总数通过次数： n-1
总数比较次数： n*(n-1)/2

冒泡排序的实现

下面是冒泡排序的实现。如果内部循环没有引起任何交换，可以通过停止算法来优化它。

C++

              
                
                    // Optimized implementation of Bubble sort
#include <bits/stdc++.h>
using namespace std;
 
// An optimized version of Bubble Sort
void bubbleSort(int arr[], int n)
{
    int
                          i, j;
    bool swapped;
    for (i = 0; i < n - 1; i++) {
                        
        swapped = false;
        for (j = 0; j < n - i - 1; j++) {
                        
            if (arr[j] > arr[j + 1]) {
                swap(arr[j], arr[j + 1]);
                swapped = true;
            }
        }
 
        // If no two elements were swapped
        // by inner loop, then break
        if (swapped == false)
            break;
    }
}
 
// Function to print an array
void printArray(int arr[], int size)
{
    int
                          i;
    for (i = 0; i < size; i++)
        cout << " " << arr[i];
}
 
// Driver program to test above functions
int main()
{
    int
                          arr[] = { 64, 34, 25, 12, 22, 11, 90 };
    int
                          N = sizeof(arr) / sizeof(arr[0]);
    bubbleSort(arr, N);
    cout << "Sorted array: \n";
    printArray(arr, N);
    return 0;
}
// This code is contributed by shivanisinghss2110

                  

              
            

C

              
                
                    // Optimized implementation of Bubble sort
#include <stdbool.h>
#include <stdio.h>
                        
 
void swap(int* xp, int* yp)
{
    int
                          temp = *xp;
    *xp = *yp;
    *yp = temp;
}
 
// An optimized version of Bubble Sort
void bubbleSort(int arr[], int n)
{
    int
                          i, j;
    bool swapped;
    for (i = 0; i < n - 1; i++) {
                        
        swapped = false;
        for (j = 0; j < n - i - 1; j++) {
                        
            if (arr[j] > arr[j + 1]) {
                swap(&arr[j], &arr[j + 1]);
                swapped = true;
            }
        }
 
        // If no two elements were swapped by inner loop,
        // then break
        if (swapped == false)
            break;
    }
}
 
// Function to print an array
void printArray(int arr[], int size)
{
    int
                          i;
    for (i = 0; i < size; i++)
        printf("%d ", arr[i]);
}
 
// Driver program to test above functions
int main()
{
    int
                          arr[] = { 64, 34, 25, 12, 22, 11, 90 };
    int
                          n = sizeof(arr) / sizeof(arr[0]);
    bubbleSort(arr, n);
    printf("Sorted array: \n");
    printArray(arr, n);
    return 0;
}

                  

              
            

Java

              
                
                    // Optimized java implementation of Bubble sort
 
import java.io.*;
 
class GFG {
     
    // An optimized version of Bubble Sort
    static
                          void bubbleSort(int arr[], int n)
    {
        int i, j, temp;
        boolean swapped;
        for (i = 0; i < n - 1; i++) {
            swapped = false;
            for (j = 0; j < n - i - 1; j++) {
                if (arr[j] > arr[j + 1]) {
                     
                        
                    // Swap arr[j] and arr[j+1]
                    temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                    swapped = true;
                        
                }
            }
 
            // If no two elements were
            // swapped by inner loop, then break
            if (swapped == false)
                break;
        }
    }
 
    // Function to print an array
    static
                          void printArray(int arr[], int size)
    {
        int i;
        for (i = 0; i < size; i++)
            System.out.print(arr[i] + " ");
        System.out.println();
    }
 
    // Driver program
    public
                          static void main(String args[])
    {
        int arr[] = { 64, 34, 25, 12, 22, 11, 90 };
        int n = arr.length;
        bubbleSort(arr, n);
        System.out.println("Sorted array: ");
        printArray(arr, n);
    }
}
 
// This code is contributed
// by Nikita Tiwari.

                  

              
            

Python3

              
                
                    # Optimized Python program for implementation of Bubble Sort
 
 
def bubbleSort(arr):
    n = len(arr)
                        
     
    # Traverse through all array elements
    for
                          i in range(n):
        swapped = False
 
        # Last i elements are already in place
        for j in
                          range(0, n-i-1):
 
            # Traverse the array from 0 to n-i-1
            # Swap if the element found is greater
            # than the next element
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
                swapped = True
                        
        if (swapped == False):
            break
 
 
# Driver code to test above
if __name__ ==
                          "__main__":
    arr = [64, 34, 25, 12, 22, 11, 90]
 
    bubbleSort(arr)
 
    print("Sorted array:")
    for
                          i in range(len(arr)):
        print("%d"
                          % arr[i], end=" ")
 
# This code is modified by Suraj krushna Yadav

                  

              
            

C＃

              
                
                    // Optimized C# implementation of Bubble sort
using System;
 
class GFG {
    // An optimized version of Bubble Sort
    static
                          void bubbleSort(int[] arr, int n)
    {
        int i, j, temp;
        bool swapped;
        for (i = 0; i < n - 1; i++) {
            swapped = false;
            for (j = 0; j < n - i - 1; j++) {
                if (arr[j] > arr[j + 1]) {
                     
                        
                    // Swap arr[j] and arr[j+1]
                    temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                    swapped = true;
                        
                }
            }
 
            // If no two elements were
            // swapped by inner loop, then break
            if (swapped == false)
                break;
        }
    }
 
    // Function to print an array
    static
                          void printArray(int[] arr, int size)
    {
        int i;
        for (i = 0; i < size; i++)
            Console.Write(arr[i] + " ");
        Console.WriteLine();
    }
 
    // Driver method
    public
                          static void Main()
    {
        int[] arr = { 64, 34, 25, 12, 22, 11, 90 };
        int n = arr.Length;
        bubbleSort(arr, n);
        Console.WriteLine("Sorted array:");
        printArray(arr, n);
    }
}
// This code is contributed by Sam007

                  

              
            

JavaScript

              
                
                    // Optimized javaScript implementation
// of Bubble sort
// An optimized version of Bubble Sort
function bubbleSort(arr, n)
{
    var
                          i, j, temp;
    var
                          swapped;
    for
                          (i = 0; i < n - 1; i++) 
    {
        swapped = false;
        for (j = 0; j < n - i - 1; j++) 
        {
            if (arr[j] > arr[j + 1]) 
            {
                // Swap arr[j] and arr[j+1]
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                swapped = true;
                        
            }
        }
 
        // IF no two elements were 
        // swapped by inner loop, then break
        if (swapped == false)
        break;
    }
}
 
// Function to print an array 
function printArray(arr, size)
{
  var i;
  for (i = 0; i < size; i++)
      console.log(arr[i] + " ");
}
 
// Driver program
var arr = [ 64, 34, 25, 12, 22, 11, 90 ];
var n = arr.length;
bubbleSort(arr, n);
console.log("Sorted array: ");
printArray(arr, n);
 
// This code is contributed shivanisinghss2110

                  

              
            

PHP

              
                
                    <?php 
// PHP Optimized implementation
// of Bubble sort
 
// An optimized version of Bubble Sort
function bubbleSort(&$arr)
{
    $n
                          = sizeof($arr);
 
    // Traverse through all array elements
    for($i = 0; $i < $n; $i++)
    {
        $swapped = False;
 
        // Last i elements are already
        // in place
        for ($j
                          = 0; $j < $n - $i - 1; $j++)
                        
        {
             
                        
            // Traverse the array from 0 to
            // n-i-1. Swap if the element 
            // found is greater than the
            // next element
            if ($arr[$j] > $arr[$j+1])
            {
                $t = $arr[$j];
                $arr[$j] = $arr[$j+1];
                $arr[$j+1] = $t;
                $swapped = True;
            }
        }
 
        // If no two elements were swapped
        // by inner loop, then break
        if ($swapped
                          == False)
            break;
    }
}
         
// Driver code
$arr = array(64, 34, 25, 12, 22, 11, 90); 
$len = sizeof($arr);
bubbleSort($arr);
 
echo "Sorted array: \n";
 
for($i = 0; $i < $len; $i++)
    echo
                          $arr[$i]." ";
     
// This code is contributed by ChitraNayal.
?>

                  

              
            

输出

排序数组：
11 12 22 25 34 64 90

冒泡排序的复杂度分析：

时间复杂度： O(N ² )
辅助空间： O(1)

冒泡排序的优点：

冒泡排序很容易理解和实现。
它不需要任何额外的内存空间。
它是一种稳定的排序算法，这意味着具有相同键值的元素在排序输出中保持其相对顺序。

冒泡排序的缺点：

冒泡排序的时间复杂度为 O(N ² )，这使得它对于大型数据集非常慢。
冒泡排序是一种基于比较的排序算法，这意味着它需要比较运算符来确定输入数据集中元素的相对顺序。在某些情况下它会限制算法的效率。

与冒泡排序相关的一些常见问题：

冒泡排序的边界情况是什么？

当元素已排序时，冒泡排序所需的时间最少（n 阶）。因此，最好事先检查数组是否已经排序，以避免 O(N ² ) 时间复杂度。

冒泡排序中排序是否就地进行？

是的，冒泡排序在不使用任何主要数据结构的情况下执行相邻对的交换。因此，冒泡排序算法是一种就地算法。

冒泡排序算法稳定吗？

是的，冒泡排序算法是稳定的。

冒泡排序算法用在哪里？

由于其简单性，冒泡排序经常被用来引入排序算法的概念。在计算机图形学中，它因其能够检测几乎排序的数组中的微小错误（例如仅两个元素的交换）并仅用线性复杂度（2n）来修复它而广受欢迎。

示例：它用于多边形填充算法，其中边界线按特定扫描线（平行于 x 轴的线）处的 x 坐标排序，并且随着 y 的增加，它们的顺序仅发生变化（两个元素交换）在两条线的交点处（来源：维基百科）

相关文章：

递归冒泡排序
排序的编码练习
冒泡排序测验
冒泡排序的复杂度分析

冒泡排序算法

冒泡排序是如何工作的？

冒泡排序的实现

C++

C

Java

Python3

C＃

JavaScript

PHP

冒泡排序的复杂度分析 ：

冒泡排序的优点：

冒泡排序的缺点：

与冒泡排序相关的一些常见问题：

冒泡排序的边界情况是什么？

冒泡排序中排序是否就地进行？

冒泡排序算法稳定吗？

冒泡排序算法用在哪里？

冒泡排序的复杂度分析：