算法(二)冒泡排序

冒泡排序主要是相邻的两个数两两进行比较，拿从小到大说明，进行冒泡排序后会将大的数沉到底部，将小得数浮到顶部。所以冒泡说法由此得名。

实现步骤

以从小到大为例，排序数组大小为n。

1. 第N = 0趟排序开始都从a[0]开始与其下面的相邻的数进行比较，如果大于相邻的数则交换他们的位置。
2. 继续与下一个相邻的数进行比较，大于相邻的就交换，最后进行比较n-1次后，第N = 0趟排序结束，最大的数就在数组的a[n-1]处。
3. 重复前面的步骤，直到 N = n-1,排序结束。

根据思想实现就不难了

实现

public static void bubbleSort(int[] arr) {
        int temp;
        for (int n = 0; n < arr.length - 1; n++)//需要n-1次
            for (int j = 0; j < arr.length - n - 1; j++) {
                if (arr[j] > arr[j + 1]) {//交换
                    temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
    }

实现完之后我们是否心中有点疑问，因为他要逐个比较，如果数组后面的一些数是有序的呢，是否可以减少排序的次数呢？结果是肯定的，例如，我们数组后面的30个数是已经排好序的，那么我们在排序的时候就可以直接忽略后面的数，只考虑他们前面的，所以我们在排序的时候可以设计个标识flag,当从第j开始都没有进行数据的交换，即有序。那么我们就可以把原来的数据切段只对j前面的数继续比较，相对于形成新的排序数组。这样就对原来的排序进行了一些优化。

优化

根据上面的思想，我们可以这样修改代码。

public static void bubbleSort2(int[] arr) {
        int temp;
        int flag = arr.length - 1;
        while (flag > 0) {
            int n = flag;
            flag = 0;
            for (int j = 0; j < n; j++) {
                if (arr[j] > arr[j + 1]) {
                    temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                    flag = j;
                }
            }
        }
    }

总结

根据前面的思想我们会知道该排序为稳定排序，最好的时间复杂度为O(n)即排序数组开始就是有序的且与要排序的顺序相同，因此只要进行一趟比较排序，遍历一次数组。最坏的情况自然是数组开始时与要排序的顺序相反，所以时间复杂度为O(n^2)

转载请指明出处 idisfkj博客：https://idisfkj.github.io