排序篇

一：故事背景

最近在准备5月底的软件工程师的考试，这个考试最困难的就是算法部分了。这是排序算法的第二篇文章，本篇文章将会分享四种算法，分别是冒泡排序、快速排序、归并排序、基数排序。本文将于上篇文章一样，详细的介绍各种排序，给出对应的图和代码实现，比较不同排序算法。希望大家通过此文章，了解不同排序算法。

二：冒泡排序

2.1 概念

通过相邻元素（i与i-1）之间的比较和交换，将排序码较小的元素逐渐从底层移向顶层。整个过程像水底的气泡逐渐向上冒，由此得名冒泡排序。

2.2 画图表示

通过观察动图可以发现，与我们上面描述的概念相符，相邻的数据一直在比较，并且逐渐的在排成由小到大。

2.3 代码实现

以下为java代码实现冒泡排序

public class BubbleSort {
    // 定义一个静态方法，用于实现冒泡排序
    public static 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]) {
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
    }
    public static void main(String[] args) {
        int[] arr = { 3, 44, 38, 5, 47, 15, 36}; // 定义一个数组
        bubbleSort(arr); // 调用 bubbleSort 方法进行冒泡排序
        System.out.println("Sorted array:"); // 打印排序后的数组
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
    }
}

2.4 总结提升

冒泡排序的时间复杂度为 O(n²)

在冒泡排序中，只需要使用一个临时变量来交换两个元素的值，所以空间复杂度是常量级别的，即O(1)。无论输入的数据规模大小如何，所需的额外空间都是固定的，与输入规模无关。

冒泡排序是一种原地排序算法，可以对原始数组进行排序，不需要使用额外的空间。

三：快速排序

3.1 概念

通过一趟排序将要排序的数据分成独立的两个部分，其中一部分的所有数据比另外一部分的数据的所有数据都要小，然后按照此方法对这两部分分别进行快速排序，整个排序过程递归进行，从而达到整个数据编程有序序列。

3.2 画图表示

3.3 代码实现

public class QuickSort {
    public static void quickSort(int[] nums, int left, int right) {
        if (left >= right) {
            return;
        }
        int pivotIndex = partition(nums, left, right);
        quickSort(nums, left, pivotIndex - 1);
        quickSort(nums, pivotIndex + 1, right);
    }
    private static int partition(int[] nums, int left, int right) {
        int pivot = nums[left];
        int i = left + 1;
        int j = right;
        while (i <= j) {
            while (i <= j && nums[i] < pivot) {
                i++;
            }
            while (i <= j && nums[j] >= pivot) {
                j--;
            }
            if (i < j) {
                swap(nums, i, j);
            }
        }
        swap(nums, left, j);
        return j;
    }
    private static void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
    public static void main(String[] args) {
        int[] nums = {5, 1, 7, 3, 9, 2};
        quickSort(nums, 0, nums.length - 1);
        System.out.println(Arrays.toString(nums));
    }
}

3.4 总结提升

快速排序的核心是一直选出一个应该放到指令位置的数据，在我们这里体现的就是选择的基准数据。快排也属于一种交换排序，相对于冒泡排序而言，其效率更高。快排的时间复杂度为O(nlogn) ~ O(n^2)

快速排序的空间复杂度是 O(logn)。这是因为快速排序算法需要递归地调用自己，每次递归需要使用一个栈空间来保存参数、返回地址和局部变量等信息。在平均情况下，快速排序算法的递归深度是 O(logn)，因此它的空间复杂度也是 O(logn)。

在最坏情况下，快速排序算法的递归深度是 O(n)，因此它的空间复杂度也是 O(n)。在最坏情况下，快速排序算法的空间复杂度比较高，但是通常情况下快速排序算法的空间复杂度较低，适用于处理大规模数据的排序。

四：归并排序

4.1 概念

归并排序的过程分为三步：

分解：将n个元素分成各含n/2个元素的子序列

求解：使用归并排序对两个子序列递归的进行排序

合并：将两个已经排好的子序列进行合并得到排序结果

4.2 画图表示

4.3 代码实现

public class MergeSort {
    public static void sort(int[] arr) {
        int n = arr.length;
        if (n < 2) {
            return;
        }
        int mid = n / 2;
        int[] leftArr = new int[mid];
        int[] rightArr = new int[n - mid];
        System.arraycopy(arr, 0, leftArr, 0, mid);
        System.arraycopy(arr, mid, rightArr, 0, n - mid);
        sort(leftArr);
        sort(rightArr);
        merge(leftArr, rightArr, arr);
    }
    private static void merge(int[] leftArr, int[] rightArr, int[] resultArr) {
        int i = 0, j = 0, k = 0;
        while (i < leftArr.length && j < rightArr.length) {
            if (leftArr[i] <= rightArr[j]) {
                resultArr[k++] = leftArr[i++];
            } else {
                resultArr[k++] = rightArr[j++];
            }
        }
        while (i < leftArr.length) {
            resultArr[k++] = leftArr[i++];
        }
        while (j < rightArr.length) {
            resultArr[k++] = rightArr[j++];
        }
    }
}

4.4 总结提升

归并排序的时间复杂度为O(nlogn)，空间复杂度为O(n)。

归并排序的时间复杂度可以分为两部分来考虑。首先是将数组拆分成较小的子数组，这个过程需要O(logn)的时间复杂度，因为它涉及到了对数级别的递归。然后是将子数组合并成一个有序的数组，这个过程需要O(n)的时间复杂度，因为它需要遍历整个数组并对每个元素进行比较。因此，归并排序的总时间复杂度为O(nlogn)。

归并排序的空间复杂度为O(n)，因为在合并子数组时，需要创建一个大小为n的辅助数组来存储排序后的元素。在归并排序的过程中，由于每次都需要将数组分成两半，因此需要创建递归调用栈，栈的深度为logn。因此，归并排序的总空间复杂度为O(n)。

五：基数排序

5.1 概念

基数排序（radix sort）属于“分配式排序”（distribution sort），又称“桶子法”（bucket sort）或bin sort。顾名思义，它是透过键值的部份资讯，将要排序的元素分配至某些“桶”中，藉以达到排序的作用。

基数排序属于一种按位排序，从个位逐渐向上进行比较。

5.2 画图表示

5.3 代码实现

public class RadixSort {
    // 获取数组中最大值
    public static int getMax(int[] arr) {
        int max = arr[0];
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] > max) {
                max = arr[i];
            }
        }
        return max;
    }
    // 基数排序
    public static void radixSort(int[] arr) {
        int max = getMax(arr);
        for (int exp = 1; max / exp > 0; exp *= 10) {
            countSort(arr, exp);
        }
    }
    // 计数排序
    public static void countSort(int[] arr, int exp) {
        int[] output = new int[arr.length];
        int[] count = new int[10];
        // 统计每个数字出现的次数
        for (int i = 0; i < arr.length; i++) {
            count[(arr[i] / exp) % 10]++;
        }
        // 计算每个数字的位置
        for (int i = 1; i < 10; i++) {
            count[i] += count[i - 1];
        }
        // 将数字按照计算出的位置放入 output 数组中
        for (int i = arr.length - 1; i >= 0; i--) {
            output[count[(arr[i] / exp) % 10] - 1] = arr[i];
            count[(arr[i] / exp) % 10]--;
        }
        // 将 output 数组中的结果复制回 arr 数组中
        for (int i = 0; i < arr.length; i++) {
            arr[i] = output[i];
        }
    }
    // 测试代码
    public static void main(String[] args) {
        int[] arr = { 170, 45, 75, 90, 802, 24, 2, 66 };
        radixSort(arr);
        System.out.println(Arrays.toString(arr));
    }
}

5.4 总结提升

基数排序法是属于稳定性的排序，其时间复杂度为O (nlog®m)，其中r为所采取的基数，而m为堆数，在某些时候，基数排序法的效率高于其它的稳定性排序法

六：表格比较

算法名 \ 比较项	时间复杂度	空间复杂度	稳定性
冒泡排序	O(n²)	O(1)	稳定
快速排序	O(nlogn) ~ O(n^2)	O(nlogn) ~ O(n)	不稳定

归并排序	O(nlogn)	O(n)	稳定
基数排序	O (nlog®m)	O(n+k) )	稳定

七：总结提升

此篇文章为大家介绍了冒泡排序、快速排序、归并排序、基数排序、并且给出了这几种排序对应的图和代码。希望通过此篇博客，大家对排序算法有一个更加深刻的了解。学习算法，学会看时间复杂度和空间复杂度，在以后的开发中优化代码。

软考算法-排序篇-下

排序篇