排序篇
一：故事背景
最近在准备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) ) | 稳定 |
七：总结提升
此篇文章为大家介绍了冒泡排序、快速排序、归并排序、基数排序、并且给出了这几种排序对应的图和代码。希望通过此篇博客，大家对排序算法有一个更加深刻的了解。学习算法，学会看时间复杂度和空间复杂度，在以后的开发中优化代码。
![现有一个接口DataOperation定义了排序方法sort(int[])和查找方法search(int[],int)，已知类QuickSort的quickSort(int[])方法实现了快速排序算法](https://ucc.alicdn.com/b3c447iaqrtq2_20240813_8507e56fc1e0475c88702b767789ed11.png?x-oss-process=image/resize,h_160,m_lfit)