排序算法-交换排序

1. 冒泡排序Bubble Sort

1.1 Bubble Sort介绍

冒泡排序（Bubble Sort）的基本思想是：通过对待排序的序列进行从左往右（即从下标较小的元素开始），依次比较相邻元素的值，若逆序则将其顺序交换。重复执行此过程直至没有需要交换的元素，也即说明改序列完成了排序，冒泡排序会使得值较大的元素逐渐从前移向后部。

一个简单的优化思路：由于在排序过程中，各元素不断接近自己的位置，如果一轮比较过后整个序列没有进行过交换，即说明该序列原本就是有序的。因此设置一个flag用于判断在该轮排序中是否进行过元素交换，从而减少重复不必要的比较。

1.2 示例说明Bubble Sort步骤

举一个例子来具体说明冒泡排序法的过程。给出一个无序数列：3，6，4，2，11，10，5使用冒泡排序将其排列成一个从小到大的有序数列。

对原始序列3，6，4，2，11，10，5进行第一轮排序：

1. 3与6进行比较，3<6因此不交换位置，得到序列3，6，4，2，11，10，5
2. 6与4进行比较，6>4，6与4交换位置，得到序列3，4，6，2，11，10，5
3. 6与2进行比较，6>2，6再次与2交换位置，得到序列3，4，2，6，11，10，5
4. 6与11进行比较，6<11不交换，得到序列3，4，2，6，11，10，5
5. 11与10进行比较，11>10交换位置，得到序列3，4，2，6，10，11，5
6. 最后将11与5比较，11>5故交换，得到第一趟排序的结果3，4，2，6，10，5，11
7. 重新开始重复上述步骤，完成后面几轮排序。需要注意的是，每一趟排序过后，最后一个数（即最大的数）即被确认不再进行比较交换。

冒泡排序规则总结：

• 一共需要进行nums.length - 1轮排序；
• 每一轮排序中，都会确认该轮的未排序序列的最后一个数，因此每一轮排序的次数在逐渐减少（nums.length - i - 1）；
• 优化的思路为，若发现在某一趟排序中并未发生交换，就可以认为序列已经有序，从而提前结束冒泡排序。
• 时间复杂度：最坏情况O(\(n^2\))，平均时间复杂度O(\(n^2\))。

1.3 代码实现

package com.algorithm;

import java.util.Arrays;

/**
 * @author SnkrGao
 * @create 2023-04-12 16:55
 */
public class BubbleSort {
    public static void main(String[] args) {
        int[] nums = {3,6,4,2,11,10,5};
        System.out.println("排序前的数组为：");
        System.out.println(Arrays.toString(nums));
        System.out.println("---------------------------------");

        bubbleSort(nums);

        System.out.println("---------------------------------");
        System.out.println("排序后的数组为：");
        System.out.println(Arrays.toString(nums));
    }

    public static void bubbleSort(int[] nums) { // 时间复杂度O(n^2)

        int temp = 0;
        boolean flag = false; // 用于标识在某轮排序中是否有元素交换过

        for (int i = 0; i < nums.length - 1; i++) { // 一共进行length - 1轮排序
            for (int j = 0; j < nums.length - i - 1; j++) { 
                // 每轮排序都是是对长度为length - i - 1的序列进行排序
                if (nums[j] > nums[j + 1]) {
                    flag = true;
                    temp = nums[j];
                    nums[j] = nums[j + 1];
                    nums[j + 1] = temp;
                }
            }
            if (flag) {
                flag = false; // 重置flag用于下一轮次的判断
            } else {
                break;
            }
            System.out.println("第" + (i + 1) + "轮排序结果为：");
            System.out.println(Arrays.toString(nums));
        }
    }
}

1.4 结果

2. 快速排序Quick Sort

2.1 Quick Sort介绍

Quick Sort算法是对Bubble Sort的一种改进，在当前所有内部排序算法中，Quick Sort被认为是最好的排序算法之一。

Quick Sort的基本思想是：通过一趟排序将待排序的序列分割为左右两个子序列，其中左边的子序列中的所有数据都比右边子序列中的数据小，然后继续依照此方法对左右两个子序列进行快速排序（递归），直至整个序列有序。

2.2 图解说明Quick Sort（挖坑法）步骤

举一个例子来具体说明快速排序（挖坑法）的过程。给出一个无序数列：6，1，2，7，9，3，4，5，10，8使用冒泡排序将其排列成一个从小到大的有序数列。

对原始序列6，1，2，7，9，3，4，5，10，8进行第一轮快排，将序列分割为左右两个子序列：

1. 首先选定基准元素pivot，一般选择序列最左边的第一个元素作为pivot（也可以随机选择）。设置两个指针left和right分别指向序列的最左端和最右端。此时序列最左端pivot的位置（也即nums[left]）为“坑”。

   eg.以上图为例，pivot = nums[left] = 6，left = 0，right = 9

2. 从right指针开始，将right所指元素与pivot进行比较，若nums[right] ≥ pivot，说明right所指元素本身就应处于pivot右侧的序列，因此将right左移right--；上述步骤也即是在找右侧第一个比pivot小的元素，当搜索到nums[right] < pivot时，将当前nums[right]填入“坑”中（即赋值令nums[left] = nums[right]），表示比pivot小的元素应处于左侧子序列。此时nums[right]所在的位置成为新的“坑”。

   eg.以上图为例，当left = 7时，找到右侧第一个小于pivot的元素，此时将nums[7]赋值给nums[0]，nums[7]的位置为新的“坑”

3. 接下来切换到left指针进行比较，将left所指元素与pivot进行比较，若num[left] ≤ pivot，说明left所指元素本身就应处于pivot左侧的序列，因此将left右移left++；上述步骤也即是在找左侧第一个比pivot大的元素，当搜索到nums[left] > pivot时，将当前nums[left]填入“坑”中（即赋值令nums[right] = nums[left]），表示比pivot大的元素应处于右侧子序列。此时nums[left]所在的位置又称为新的“坑”。

   eg.以上图为例，当left = 3时，找到左侧第一个大于pivot的元素，此时将nums[3]赋值给nums[7]，nums[3]的位置即为新的“坑”

4. 重复上述的2~3步骤，直至left与right指针相遇（left == right），此时将pivot的值赋值给相遇的位置（即最后的”坑”填入pivot，nums[left] == nums[right] = pivot），此时pivot左侧的序列元素均小于pivot，右侧的序列元素均大于pivot，第一轮快排结束。

   eg.当left == right时，两指针在下标为5处重合，此时赋值令nums[5] = pivot

5. 后续只需要给出递归终止条件：left ≥ right时结束递归，并对左子序列和右子序列递归执行上述排序（或称partition分区）过程即可。

2.3 代码实现

package com.algorithm;

import java.util.Arrays;

/**
 * @author SnkrGao
 * @create 2023-04-13 12:46
 */
public class QuickSort {
    public static void main(String[] args) {
        int[] nums = {6,1,2,7,9,3,4,5,10,8};
        System.out.println("排序前的数组为：");
        System.out.println(Arrays.toString(nums));

        quickSort(nums, 0, nums.length - 1);

        System.out.println("排序后的数组为：");
        System.out.println(Arrays.toString(nums));

    }

    public static void quickSort(int[] nums, int left, int right) {
        if (left >= right) { // 递归终止条件
            return;
        }
        int partitiobIndex = partition(nums, left, right);
        // 调用partition方法得到分割点位置，然后分别对左右子序列开始递归，完成快排
        quickSort(nums, left, partitiobIndex - 1);
        quickSort(nums, partitiobIndex + 1, right);
    }

    /**
     * 快排将待排序的序列分为左子序列和右子序列
     * @param nums 待排序的数组
     * @param left 左指针
     * @param right 右指针
     * @return 返回分割为左右两个序列的pivot的位置，即该位置左侧元素均小于该位置右侧的元素
     *         ！！！注意返回的是左右指针重合的位置，也即最后一个“坑”，不是返回pivot的值
     */
    public static int partition(int[] nums, int left, int right) {
        int pivot = nums[left]; // 指定序列最左侧第一个元素为基准值

        while (left < right) {
            // 从right指针开始，从右往左找到第一个小于pivot的元素的位置
            while (left < right && nums[right] >= pivot) {
                right--;
            }
            // 找到后将该值填入“坑”中，该位置称为新的“坑”
            nums[left] = nums[right];
            // 接着从left指针从左往右找到第一个大于pivot的元素的位置
            while (left < right && nums[left] <= pivot) {
                left++;
            }
            // 找到后将该值填入上一个“坑”，这个位置又成为新的“坑”
            nums[right] = nums[left];
        }

        // 当左右指针相遇时，跳出while循环，并将该相遇位置作为“坑”，填入pivot
        // 得到以pivot作为分割点划分出的左右两个子序列
        nums[left] = pivot;

        // 返回分割点的位置
        return left;
    }
}

2.4 Quick Sort时间复杂度分析

可以看出Quick Sort的时间复杂度与partition的划分过程有很大关系，主要取决于partition过程划分的是否平衡。

• 最好情况时间复杂度：O(\(nlongn\))

  最优情况下，partition每一次都划分均匀，恰好将序列分为长度相等的两个子序列；

• 最坏情况时间复杂度：O(\(n^2\))

  最坏情况下退回到冒泡排序；

• 平均时间复杂度：O(\(nlongn\))