排序是计算机中常见且重要的操作，用于使数据按照某种规则或标准进行有序化，便于后续的搜索、查找和处理。
为什么排序算法很重要？
由于排序通常有助于降低问题的算法复杂性，因此它在计算机科学中具有重要用途。百度搜索显示，当今计算世界中有 40 多种不同的排序算法。疯狂吧？那你知道几个呢！
现实世界中实现这一点的一些最佳示例是。
- 冒泡排序用于电视节目中，根据观众观看时间对频道进行排序！
- 数据库使用外部合并排序对太大而无法完全加载到内存中的数据集进行排序！
- 体育比分通过快速排序算法实时快速组织！
数据结构中的排序类型
- 基于比较的排序：在基于比较的排序技术中，定义比较器来比较数据样本的元素或项目。该比较器定义元素的顺序。例子有：冒泡排序、归并排序。
- 基于计数的排序：这些类型的排序算法中的元素之间不涉及比较，而是在执行过程中进行计算假设。例如：计数排序、基数排序。
- 就地与非就地排序（In-Place vs Not-in-Place Sorting）：数据结构中的就地排序技术会修改原始数组中数组元素的顺序。另一方面，非就地排序技术使用辅助数据结构对原始数组进行排序。就地排序技术的示例有：冒泡排序、选择排序。非就地排序算法的一些示例包括：合并排序、快速排序。
下面详细介绍一下，8 种排序算法。
PS：GIF图较大，耐心等待打开，值得反复去看！
1、冒泡排序
冒泡排序的基本思想是，如果相邻元素的顺序不符合要求，则重复交换相邻元素。是的，就是这么简单。
如果给定的数组元素必须按升序排序，则冒泡排序将首先比较数组的第一个元素与第二个元素，如果结果大于第二个元素，则立即交换它们，然后继续比较第二个和第三个元素，依此类推。
通过一个简单的例子理解冒泡排序算法。
让我们尝试通过一个例子来理解冒泡排序背后的直观方法：
冒泡排序算法解释
Java 中的实现
import java.util.Arrays;
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 arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
public static void main(String[] args) {
int[] arr = {5, 3, 4, 2, 1};
bubbleSort(arr);
System.out.println("Sorted array: ");
for (int num : arr) {
System.out.print(num + " ");
}
System.out.println();
}
}冒泡排序的实现
时间复杂度：
- 最坏情况： O(n^2)
- 平均情况：O(n*logn)
- 最好的情况：O(n*logn)
空间复杂度： O(1)。
2、选择排序
选择排序是一种排序算法，其中给定数组分为两个子数组：已排序的左部分和未排序的右部分。
最初，已排序部分为空，未排序部分是整个列表。在每次迭代中，我们从未排序列表中获取最小元素并将其推送到已排序列表的末尾，从而构建已排序的数组。
通过示例了解选择排序算法。
让我们尝试用一个简单的例子来理解选择排序背后的直观想法：
选择排序算法解释
Java 中的实现
import java.util.Arrays;
public class SelectionSort {
public static void selectionSort(int[] arr) {
int n = arr.length;
for (int i = 0; i < n - 1; i++) {
int minIndex = i;
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
int temp = arr[minIndex];
arr[minIndex] = arr[i];
arr[i] = temp;
}
}
public static void main(String[] args) {
int[] arr = {25, 22, 27, 15, 19};
selectionSort(arr);
System.out.println("Sorted array:");
for (int num : arr) {
System.out.print(num + " ");
}
System.out.println();
}
}选择排序的实现
时间复杂度：
- 最坏情况： O(n*n)
- 平均情况： O(n*logn)
- 最好情况： O(n*logn)
空间复杂度： O(1)。
3、插入排序
插入排序是一种将给定数组分为已排序部分和未排序部分的排序算法。在每次迭代中，要插入的元素必须在已排序的子序列中找到其最佳位置，然后插入，同时将剩余元素向右移动。
通过示例了解插入排序算法。
下面是一个例子，可以帮助更好地理解插入排序：
插入排序算法解释
现在已经了解了插入排序的实际工作原理，接下来看一下 Java的 实现。
import java.util.Arrays;
public class InsertionSort {
public static void insertionSort(int[] arr) {
int n = arr.length;
for (int i = 1; i = 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j = j - 1;
}
arr[j + 1] = key;
}
}
public static void main(String[] args) {
int[] arr = {25, 22, 27, 15, 19};
insertionSort(arr);
System.out.println(Arrays.toString(arr));
}
}插入排序的实现
时间复杂度：
- 最坏情况： O(n*n)
- 平均情况： O(n*logn)
- 最好情况： O(n*logn)
空间复杂度： O(1)。
4、快速排序
快速排序是一种分而治之的算法。快速排序背后的直观概念是，它从给定的元素数组中选择一个元素作为主元，然后围绕主元元素对数组进行分区。随后，它递归地调用自身并随后对两个子数组进行分区。
通过可视化了解快速排序算法。
快速排序算法涉及的逻辑步骤如下：
- 枢轴选择：选择一个元素作为枢轴（这里，我们选择最后一个元素作为枢轴）。
- 分区：数组的分区方式使得所有小于主元的元素都位于左子数组中，而所有严格大于主元的元素都存储在右子数组中。
- 递归调用快速排序：对上面创建的两个子数组再次调用快速排序函数，并重复步骤。
下面的实现中包含了注释，以帮助更好地理解快速排序算法。
import java.util.Arrays;
public class QuickSort {
public static int partition(int[] arr, int low, int high) {
int pivot = arr[high];
int i = low - 1;
for (int j = low; j
