交换类排序法（Java实现）

交换类排序算法总结

---

冒泡排序

---

冒泡排序是众多排序算法中最简单的一个，也是在学校最先学的一个排序算法。

冒泡排序的基本思路：从前两个元素开始依次比较相邻的两个元素，如果第一个比第二大则交换两个元素的位置，直到n-1次完成排序（n是数组的长度）。

可以使用一个int型变量记录一次循环的元素交换次数，如果为0则完成排序可以直接return

时间复杂度O（N2）

代码实现：

/**
 * @author MaxYang
 * @date 2021/7/21 1:50 下午
 */
public class BubbleSort {
    public static void sort(int[] nums) {
        for (int i = 0; i < nums.length - 1; i++) {
            for (int j = 0; j < nums.length - 1 - i; j++) {
                if (nums[j] > nums[j + 1]) {
                    int temp = nums[j];
                    nums[j] = nums[j + 1];
                    nums[j + 1] = temp;
                }
            }
        }
    }

    public static void main(String[] args) {
        //创建数组
        int nums[] = {1, 5, 8, 2, 3, 7, 9, 4, 6};
        //调用排序方法
        sort(nums);
        //输出排序后的数组
        for (int i = 0; i < nums.length; i++) {
            System.out.print(nums[i]);
        }
    }
}

---

快速排序

---

快速排序是基于二分的思想，对冒泡排序的一种改进。

快速排序的基本思路：假设现在对“6 1 2 7 9 3 4 5 10 8”这个10个数进行排序。首先在这组数字里随便找一个数作为基准数。接下来的实现将会一第一个数6作为基准数，然后将这组数字中比基准数6大的放在6的右边，比基准数6小的放在6的左边。

排序算法

大致排序方法为分别从初始序列“6 1 2 7 9 3 4 5 10 8”两端开始“嗅探”，先从右往左找一个小于6的数，再从左往右找一个大于6的数字，然后交换这两个数字的位置。这里可以设置两个变量i和j，分别指向序列的最左边(i=0)和最右边(j=9)。

因为此时设置的基准数是最左边的数，所以必须让j先开始移动（否则交换完成时不能保证所有左边的值小于基准数），j一步一步向左挪动（j–），直到指向一个小于6的数时停下来。接下来i开始一步一步向右边移动（i++），直到找到一个大于6的数停下来。最后j停留在了数字5，i停留在了数字7。

现在i和j所指向的元素交换位置，交换后的序列如上图所示。

至此第一次交换结束。接下来j继续开始向左移动（记住依然是必须j先开始移动），遇到4（比6小）时停下来。然后i开始向右移动，到9时停下来（比6大）。此时再次将i和j指向的元素进行交换，交换后的序列如下：

至此第二次交换结束，开始第三次“嗅探”。j继续向左移动，发现3（比6小）后停了下来。i继续向又移动，这时在3的位置与j相遇。说明本次“嗅探”结束。将基数6和3进行交换，交换后的序列如下：

第一轮“嗅探”结束后，此时以基数6为分界点，6左边的数都小于等于6，6右边的数都大于等于6。以6为分界点拆分出了两个序列。左边序列是“3 1 2 5 4”，右边序列是“9 7 10 8”。接下来可以用上面同样的方式来处理这两个序列。

以6左边的序列为例：左边的序列是“3 1 2 5 4”。请将这个序列以3为基准数进行调整，使得3左边的数都小于等于3，3右边的数都大于等于3。按照上述方法排序得到的顺序应该是：

2 1 3 5 4

然后再对3左边的序列“2 1”和右边的序列“5 4”用同样的方法进行排序。对序列“2 1”以2为基准数进行调整，处理完毕之后的序列为“1 2”，此时序列“1”只有一个数不再需要进行任何处理。序列“5 4”结果同样的处理后最后可以得到如下序列：

1 2 3 4 5 6 9 7 10 8

对于6右边的“9 7 10 8”也模拟刚才的过程，直到不可拆分出新的子序列为止。最终得到如下序列：

1 2 3 4 5 6 7 8 9 10

到此为止排序完全结束。

快速排序之所以比较快是因为对比冒泡排序每次交换是跳跃式的，总交换次数少了很多。

在最坏的情况下时间复杂度和冒泡排序相同：O（N2），平均时间复杂度O（NlogN）

代码实现：

/**
 * @author MaxYang
 * @date 2021/7/21 11:58 下午
 */
public class QuickSort {
    public static void quickSort(int[] arr, int low, int high) {
        int i, j, temp, t;
        if (low > high) {
            return;
        }
        i = low;
        j = high;
        //temp：基准数
        temp = arr[low];

        while (i < j) {
            //先从右边以此向左移动
            while (temp <= arr[j] && i < j) {
                j--;
            }
            //再从左边依次向右移动
            while (temp >= arr[i] && i < j) {
                i++;
            }
            //满足条件元素互换位置
            if (i < j) {
                t = arr[j];
                arr[j] = arr[i];
                arr[i] = t;
            }

        }
        //将基准为与i和j相等位置的数字交换
        arr[low] = arr[i];
        arr[i] = temp;
        //递归排序左半数组
        quickSort(arr, low, j - 1);
        //递归排序右半数组
        quickSort(arr, j + 1, high);
    }

    public static void main(String[] args) {
        //创建数组
        int[] arr = {10, 7, 2, 4, 7, 62, 3, 4, 2, 1, 8, 9, 19};
        //调用快速排序
        quickSort(arr, 0, arr.length - 1);
        //输出排序后的数组
        for (int i = 0; i < arr.length; i++) {
            System.out.println(arr[i]);
        }
    }
}