用Java实现冒泡排序

排序算法的数量相当多，其中许多算法都非常具体，是为了解决一小部分问题并处理特定类型的数据而开发的。但在所有这些多样性中，最简单的算法当之无愧的是冒泡排序，它可以用任何编程语言实现。尽管它很简单，但它是许多相当复杂的算法的基础。另一个同样重要的优点是它的简单性，因此可以立即记住并实施它，而无需您面前有任何其他文献。在 Java 中实现冒泡排序 - 1

介绍

整个现代互联网由数据库中收集的大量不同类型的数据结构组成。它们存储各种信息，从用户的个人数据到高度智能自动化系统的语义核心。不用说，数据排序在如此海量的结构化信息中发挥着极其重要的作用。排序可能是在数据库中搜索任何信息之前的强制性步骤，排序算法的知识在编程中起着非常重要的作用。

通过机器眼和人眼分类

假设您需要对 5 列不同高度的升序进行排序。这些列可以表示任何类型的信息（股票价格、通信通道带宽等），您可以呈现此任务的一些您自己的版本以使其更加清晰。好吧，举个例子，我们将按照身高对复仇者联盟进行排序：

与计算机程序不同，排序对您来说并不困难，因为您可以看到全局，并且可以立即找出需要将哪个英雄移动到哪里才能成功完成按高度排序。您可能已经猜到，要按升序对这个数据结构进行排序，只需交换绿巨人和钢铁侠的位置即可：

完毕！

这样就可以成功完成排序了。然而，计算机与你不同，~~它有些愚蠢~~，它不能将整个数据结构视为一个整体。它的控制程序一次只能比较两个值。为了解决这个问题，她必须将两个数字放入内存中并对它们执行比较操作，然后转向另一对数字，依此类推，直到分析完所有数据。因此，任何排序算法都可以非常简化为三个步骤的形式：

比较两个元素；
交换或复制其中之一；
转到下一个元素；

不同的算法可以以不同的方式执行这些操作，但我们将继续考虑冒泡排序的工作原理。

冒泡排序算法

冒泡排序被认为是最简单的，但在描述这个算法之前，让我们想象一下，如果你可以像一台机器一样，在一段时间内只比较两个英雄，你将如何按身高对复仇者进行排序。最有可能的是，您会按照以下方式（最优化）进行操作：

您移动到数组的零元素（黑寡妇）；
将零元素（黑寡妇）与第一个元素（绿巨人）进行比较；
如果位置 0 的元素更高，则交换它们；
否则，如果位置 0 处的元素较小，则将它们保留在原来的位置；
移动到右侧的位置并重复比较（将绿巨人与船长进行比较）

当你用这样的算法一次性遍历完整个列表后，排序并不能完全完成。但另一方面，列表中最大的元素将被移动到最右边的位置。这种情况总会发生，因为一旦你找到最大的元素，你就会不断地改变位置，直到把它移到最后。也就是说，一旦程序在数组中“找到”绿巨人，它就会将他进一步移动到列表的最后：

这就是为什么该算法被称为冒泡排序，因为其操作的结果是，列表中最大的元素将位于数组的最顶部，而所有较小的元素将向左移动一位：

要完成排序，您需要返回到数组的开头并再次重复上述五个步骤，再次从左到右移动，根据需要比较和移动元素。但这一次你需要在数组末尾前一个元素停止算法，因为我们已经知道最大的元素（Hulk）绝对在最右边的位置：

所以程序必须有两个循环。为了更清楚起见，在我们继续查看程序代码之前，您可以通过此链接查看冒泡排序如何工作的可视化：可视化冒泡排序的工作原理

Java冒泡排序的实现

为了演示 Java 中排序的工作原理，下面是程序代码：

创建一个包含 5 个元素的数组；
将复仇者联盟上传到其中；
显示数组的内容；
实现冒泡排序；
重新显示排序后的数组。

您可以查看下面的代码，甚至可以将其下载到您最喜欢的~~IntelliJ~~ IDE 中。下面将对其进行分析：

class ArrayBubble{
    private long[] a;   // array reference
    private int elems;  //number of elements in the array

    public ArrayBubble(int max){    //class constructor
        a = new long[max];          //create an array with size max
        elems = 0;                  //when created, the array contains 0 elements
    }

    public void into(long value){   // method for inserting an element into an array
        a[elems] = value;           //insert value into array a
        elems++;                    //array size increases
    }

    public void printer(){          // method for outputting an array to the console
        for (int i = 0; i < elems; i++){    //for each element in the array
            System.out.print(a[i] + " ");   // output to console
            System.out.println("");         //a new line
        }
        System.out.println("----End array output----");
    }

    private void toSwap(int first, int second){ //method swaps a pair of array numbers
        long dummy = a[first];      // put the first element into a temporary variable
        a[first] = a[second];       // put the second element in place of the first
        a[second] = dummy;          //instead of the second element, write the first from temporary memory
    }

    public void bubbleSorter(){     //МЕТОД ПУЗЫРЬКОВОЙ СОРТИРОВКИ
        for (int out = elems - 1; out >= 1; out--){  //Outer loop
            for (int in = 0; in < out; in++){       //Inner loop
                if(a[in] > a[in + 1])               //If the order of the elements is wrong
                    toSwap(in, in + 1);             // call the swapping method
            }
        }
    }
}

public class Main {
    public static void main(String[] args) {
        ArrayBubble array = new ArrayBubble(5); //Create array array with 5 elements

        array.into(163);       //fill the array
        array.into(300);
        array.into(184);
        array.into(191);
        array.into(174);

        array.printer();            //display elements before sorting
        array.bubbleSorter();       //ИСПОЛЬЗУЕМ ПУЗЫРЬКОВУЮ СОРТИРОВКУ
        array.printer();            // print the sorted list again
    }
}

尽管代码中有详细的注释，我们还是提供了程序中提供的一些方法的描述。程序中执行主要工作的关键方法都写在 ArrayBubble 类中。该类包含一个构造函数和几个方法：

into– 将元素插入数组的方法；
printer– 逐行显示数组内容；
toSwap– 如有必要，重新排列元素。为此，使用临时变量dummy，将第一个数字的值写入其中，并在第一个数字的位置写入第二个数字的值。然后临时变量的内容被写入第二个数字。这是交换两个元素的标准技术；

最后是主要方法：

bubbleSorter– 它的主要工作是对数组中存储的数据进行排序，我们将再次单独介绍：

public void bubbleSorter(){     //МЕТОД ПУЗЫРЬКОВОЙ СОРТИРОВКИ
    for (int out = elems - 1; out >= 1; out--){  //Outer loop
        for (int in = 0; in < out; in++){       //Inner loop
            if(a[in] > a[in + 1])               //If the order of the elements is wrong
                toSwap(in, in + 1);             // call the swapping method
        }
    }
}

这里你应该注意两个计数器：externalout和internal in。 外部计数器out从数组末尾开始枚举值，并在每次新遍历时逐渐减一。out每次新传递时，变量都会进一步向左移动，以免影响已排序到数组右侧的值。内部计数器in从数组的开头开始枚举值，并在每次新传递时逐渐加一。增加in一直发生，直到达到out（当前通道中最后一个分析的元素）。内循环in比较两个相邻单元格in和in+1。如果in比中存储的数字更大in+1，则调用该方法toSwap，该方法交换这两个数字的位置。

结论

冒泡排序算法是最慢的算法之一。如果数组由 N 个元素组成，则第一遍将执行 N-1 次比较，第二遍将执行 N-2 次比较，然后是 N-3 次比较，依此类推。也就是说，总遍历次数为： (N-1) + (N-2) + (N-3) + … + 1 = N x (N-1)/2 因此，在排序时，算法执行大约 0.5x(N ^2) 次比较。当 N = 5 时，比较次数约为 10 次，当 N = 10 时，比较次数将增加到 45 次。因此，随着元素数量的增加，排序的复杂度显着增加：

算法的速度不仅受到传递次数的影响，还受到需要进行的排列的数量的影响。对于随机数据，排列次数平均值为 (N^2) / 4，大约是遍数的一半。然而，在最坏的情况下，排列的数量也可以是 N^2 / 2 - 如果数据最初以相反的顺序排序，就会出现这种情况。尽管这是一种相当慢的排序算法，但了解和理解它的工作原理非常重要，并且如前所述，它是更复杂算法的基础。天哪！

TO VIEW ALL COMMENTS OR TO MAKE A COMMENT,
GO TO FULL VERSION