关于程序员:每日一算冒泡排序

冒泡排序 是最简略的排序算法，如果相邻元素的程序谬误，则通过反复替换它们来工作。该算法不适用于大数据集，因为它的均匀和最坏状况工夫复杂度都很高。

原理

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

第一步：

• 冒泡排序从最后面的两个元素开始，比拟它们以查看哪个更大。
• (6 3 0 5) –> (3 6 0 5 )，这里，算法比拟前两个元素，并从 6 > 3 开始替换。
• (3 6 0 5 ) –> (3 0 6 5 ), 从 6 > 0 开始替换
• (3 0 6 5 ) –> (3 0 5 6 ), Swap since 6 > 5

第二步：

• 当初，在第二次迭代期间，它应该如下所示：
• (3 0 5 6 ) –> (0 3 5 6 ), Swap since 3 > 0
• (0 3 5 6 ) –> (0 3 5 6 ), 不变为 5 > 3

第三步：

• 当初，数组曾经排序了，然而咱们的算法不晓得它是否实现了。

• 该算法须要一个

  残缺的传递, 而不进行任何替换能力晓得它已排序。

• (0 3 5 6 ) –> (0 3 5 6 ), 没有变动 3 > 0

数组当初已排序，不会再产生传递。

算法实战

请依照以下步骤解决问题：

• 运行嵌套的 for 循环以应用两个变量 i 和j遍历输出数组，使得 0 ≤ i < n-1 和 0 ≤ j < ni-1
• 如果 arr[j] 大于 arr[j+1] 则替换这些相邻元素，否则持续
• 打印排序后的数组

上面是上述办法的实现：

• Java 版本

import java.util.*;

class BubbleSort {void bubbleSort(int arr[])
    {
        int n = arr.length;
        for (int i = 0; i < n - 1; i++)
            for (int j = 0; j < n - i - 1; j++)
                if (arr[j] > arr[j + 1]) {// swap arr[j+1] and arr[j]
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
    }


    void printArray(int arr[])
    {
        int n = arr.length;
        for (int i = 0; i < n; ++i)
            System.out.print(arr[i] + " ");
        System.out.println();}

    
    public static void main(String args[])
    {BubbleSort ob = new BubbleSort();
        int arr[] = { 5, 1, 4, 2, 8};
        ob.bubbleSort(arr);
        System.out.println("Sorted array");
        ob.printArray(arr);
    }
}

输入

排序数组：1 2 4 5 8

工夫复杂度： O(N 2)
辅助空间： O(1)

冒泡排序的优化实现：

即便数组已排序，上述函数也始终运行 O(N 2) 工夫。如果外部循环没有引起任何替换，能够通过进行算法来优化它。

上面是上述办法的实现：

• Java 版本实现

import java.io.*;

class GFG
{
    // 冒泡排序的优化版本
    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 (swapped == false)
                break;
        }
    }

    
    static void printArray(int arr[], int size)
    {
        int i;
        for (i = 0; i < size; i++)
            System.out.print(arr[i] + " ");
        System.out.println();}


    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);
    }
}

输入

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

工夫复杂度： O(N 2)
辅助空间： O(1)

冒泡排序的最坏状况剖析：

冒泡排序的最坏 状况 产生在数组元素按降序排列时。
在最坏的状况下，对给定数组进行排序所需的迭代或遍历总数为 (n-1)。 其中“n”是数组中存在的元素数量。

在第 1 遍： 比拟次数 = (n-1)

       替换次数 = (n-1)

在第 2 遍： 比拟次数 = (n-2)

       替换次数 = (n-2)

在第 3 遍： 比拟次数 = (n-3)

      替换次数 = (n-3)
           **。**
           **.**
           **.**

在第 n-1 次： 比拟次数 = 1

        替换次数 = 1

当初，计算排序数组所需的比拟总数
= (n-1) + (n-2) + (n-3) +。. . 2 + 1
= (n-1)(n-1+1)/2 {用 N 个自然数求和公式}*
= n (n-1)/2

对于最坏的状况：

替换总数 = 比拟总数 比拟
总数（最坏状况）= n(n-1)/2
替换总数（最坏状况）= n(n-1)/2

最坏和均匀状况工夫复杂度： O(N 2)。最坏的状况产生在数组被反向排序时。
最佳状况工夫复杂度： O(N)。最好的状况产生在数组曾经排序时。
辅助空间： O(1)

冒泡排序的递归实现：

这个想法是将最大的元素放在它的地位上，并对所有其余元素持续做同样的事件。

算法：

1. 从一组未排序的数字开始
2. 定义一个名为“bubbleSort”的函数，它将数组和数组的长度作为参数
3. 在函数中，创立一个名为“sorted”的变量，并将其设置为 true
4. 创立一个 for 循环，遍历从索引 0 开始到数组长度- 1 完结的数组
5. 在 for 循环中，将以后元素与数组中的下一个元素进行比拟
6. 如果以后元素大于下一个元素，替换它们的地位并将“sorted”设置为 false
7. for 循环后，查看“sorted”是否为假
8. 如果“sorted”为假，以雷同的数组和长度作为参数再次调用“bubbleSort”函数
9. 如果“sorted”为真，则数组当初已排序，函数将返回排序后的数组
10. 应用初始未排序数组及其长度作为参数调用“bubbleSort”函数以开始排序过程。

上面是上述办法的实现：

• Java 版本

import java.util.*;
class GFG
{public static void main(String[] args) {int[] ar={5,4,8,2,9,7,3};
        bubbleSort(ar,ar.length);
        
        System.out.print("Sorted array :");
        for(int ele:ar)
        {System.out.print(ele+" ");
        }
        System.out.println();}
    public static void bubbleSort(int[] a,int n)
    {
        boolean sorted=true;
    // 咱们假如该数组曾经排序。for(int i=0;i<n-1;i++)
        {if(a[i]>a[i+1])
            {int t=a[i];
                a[i]=a[i+1];
                a[i+1]=t;
                
                sorted=false;
            // 当初数组没有排序。}
        // 如果没有替换，那么咱们能够说数组曾经排序。}
        if(sorted==false)
        {
            // 递归调用直到它被排序。bubbleSort(a,n);
        }
    }
}

输入

排序数组：2 3 4 5 7 8 9

工夫复杂度：O (N 2)

辅助空间：O(1)

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

当元素曾经排序时，冒泡排序须要最短时间（n 的程序）。因而最好当时查看数组是否曾经排序，以防止 O(N 2) 工夫复杂度。

排序是否在冒泡排序中产生？

是的，冒泡排序在不应用任何次要数据结构的状况下执行相邻对的替换。因而冒泡排序算法是一种就地算法。

冒泡排序算法稳固吗？

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

冒泡排序算法用在哪里？

因为其简略性，冒泡排序通常用于介绍排序算法的概念。
在计算机图形学中，它因其可能检测简直已排序的数组中的渺小谬误（如仅替换两个元素）并仅以线性
复杂度 (2n) 修复它而广受欢迎。

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

长处：

• 冒泡排序易于了解和实现。
• 它不须要任何额定的内存空间。
• 它对不同类型的数据具备适应性。
• 它是一种稳固的排序算法，意味着具备雷同键值的元素在排序后的输入中放弃它们的绝对程序。

毛病

• 冒泡排序的工夫复杂度为 O(n^2)，这使得它对于大型数据集十分慢。
• 它对于大型数据集效率不高，因为它须要屡次遍历数据。
• 冒泡排序是一种基于比拟的排序算法，这意味着它须要一个比拟运算符来确定输出数据集中元素的绝对程序。尽管这不肯定是毛病，但在某些状况下它会限度算法的效率。

本文由 mdnice 多平台公布