一、快速排序
描述：快速排序（Quick Sort）是一种高效的分治排序算法，其工作原理如下：
基本思想
- 通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小
- 分别对这两部分记录继续进行排序，以达到整个序列有序
- 采用分治法策略，递归地对子数组进行排序
工作原理
- 选择基准元素：从数组中选择一个元素作为基准（pivot），通常选择最后一个元素
- 分区操作：重新排列数组，使得比基准小的元素放在基准左边，比基准大的元素放在基准右边
- 递归排序：对基准左右两个子数组递归地进行快速排序
- 基准定位：每次分区操作后，基准元素会放到其最终的正确位置上
- 终止条件：当子数组长度小于等于1时，递归终止
public static void main(String[] args) {
int [] a = {5,3,2,4,1};
quickSort(a, 0, a.length - 1);
System.out.println(Arrays.toString(a));
}
// 快速排序
public static void quickSort(int[] arr, int low, int high) {
if (low < high) { // 递归终止条件：子数组长度大于1
int pi = partition(arr, low, high); // 获取分区点
quickSort(arr, low, pi - 1); // 递归排序左半部分
quickSort(arr, pi + 1, high); // 递归排序右半部分
}
}
public static int partition(int[] arr, int low, int high) {
int pivot = arr[high]; // 选择最后一个元素作为基准
int i = (low - 1); // 小于基准的元素的索引
for (int j = low; j < high; j++) { // 遍历从low到high-1的元素
if (arr[j] <= pivot) { // 如果当前元素小于等于基准
i++; // 扩展小于基准的区域
int temp = arr[i]; // 交换元素
arr[i] = arr[j];
arr[j] = temp;
}
}
int temp = arr[i + 1]; // 将基准放到正确位置
arr[i + 1] = arr[high];
arr[high] = temp;
return i + 1; // 返回基准的索引
}
特点
- 时间复杂度：
- 最好情况：O(n log n) - 每次分区都能平均分割
- 平均情况：O(n log n)
- 最坏情况：O(n²) - 每次选到最大或最小元素作为基准
- 空间复杂度：O(log n) - 递归调用栈空间
- 稳定性：不稳定排序算法
- 适用场景：大规模数据集，对性能要求较高的场景
二、归并排序
描述：归并排序（Merge Sort）是一种基于分治思想的排序算法，其工作原理如下：
基本思想
- 将数组不断二分，直到每个子数组只有一个元素
- 然后将这些子数组两两合并，合并过程中保持有序
- 最终得到一个完全有序的数组
工作原理
- 分解：将数组从中间分成两个子数组，递归地对两个子数组进行分解
- 解决：当子数组长度为1时，认为其已排序
- 合并：将两个已排序的子数组合并成一个有序数组
- 递归：重复上述过程，直到整个数组有序
public static void main(String[] args) {
int [] a = {5,3,2,4,1};
mergeSort(a, 0, a.length - 1);
System.out.println(Arrays.toString(a));
}
// 归并排序
public static void mergeSort(int[] arr, int left, int right) {
// 当 left < right 时继续分解数组
if (left < right) {
// 计算中间位置，将数组分为两部分
int mid = (left + right) / 2;
// 递归排序左半部分
mergeSort(arr, left, mid);
// 递归排序右半部分
mergeSort(arr, mid + 1, right);
// 合并已排序的两部分
merge(arr, left, mid, right);
}
}
// 合并两个已排序的子数组
public static void merge(int[] arr, int left, int mid, int right) {
// 计算左右子数组的长度
int n1 = mid - left + 1; // 左子数组长度
int n2 = right - mid; // 右子数组长度
// 创建临时数组存储左右子数组
int[] leftArr = new int[n1];
int[] rightArr = new int[n2];
// 将原数组元素复制到临时数组中
for (int i = 0; i < n1; i++)
leftArr[i] = arr[left + i]; // 复制左子数组
for (int j = 0; j < n2; j++)
rightArr[j] = arr[mid + 1 + j]; // 复制右子数组
// 初始化左右子数组的索引以及合并后数组的索引
int i = 0, j = 0, k = left;
// 比较两个子数组的元素，将较小的元素放入原数组
while (i < n1 && j < n2) {
if (leftArr[i] <= rightArr[j]) {
arr[k] = leftArr[i]; // 左子数组元素较小，放入原数组
i++; // 左子数组索引后移
} else {
arr[k] = rightArr[j]; // 右子数组元素较小，放入原数组
j++; // 右子数组索引后移
}
k++; // 原数组索引后移
}
// 将左子数组剩余元素复制到原数组
while (i < n1) {
arr[k] = leftArr[i];
i++;
k++;
}
// 将右子数组剩余元素复制到原数组
while (j < n2) {
arr[k] = rightArr[j];
j++;
k++;
}
}
特点
- 时间复杂度：
- 最好情况：O(n log n)
- 平均情况：O(n log n)
- 最坏情况：O(n log n)
- 空间复杂度：O(n) - 需要额外的数组空间用于合并
- 稳定性：稳定排序算法
- 适用场景：大规模数据排序，对时间复杂度有稳定要求的场景
三、堆排序
描述：堆排序（Heap Sort）是一种基于二叉堆数据结构的比较排序算法。它利用堆这种数据结构所设计的一种排序算法，是选择排序的优化版本。
基本思想
- 将待排序数组构建成一个最大堆（或最小堆）
- 此时数组的第一个元素就是最大（或最小）值
- 将堆顶元素与末尾元素交换，然后重新调整剩余元素为堆
- 重复此过程，直到所有元素排序完成
工作原理
- 构建初始堆：将无序数组调整为最大堆结构
- 交换堆顶与末尾元素：将堆顶最大值与末尾元素交换，使最大值"沉底"
- 重新调整堆：对剩余未排序元素重新构建最大堆
- 重复过程：重复步骤2-3，直到所有元素排序完成
// 堆排序
public static void heapSort(int[] arr) {
int n = arr.length;
// 构建最大堆：从最后一个非叶子节点开始，自下而上调整
for (int i = n / 2 - 1; i >= 0; i--) {
heapify(arr, n, i);
}
// 逐个从堆顶取出元素
for (int i = n - 1; i > 0; i--) {
// 将当前最大元素（堆顶）移到数组末尾
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
// 重新调整剩余元素为最大堆
heapify(arr, i, 0);
}
}
// 调整堆结构，使其满足最大堆性质
public static void heapify(int[] arr, int n, int i) {
int largest = i; // 假设当前节点为最大值
int left = 2 * i + 1; // 左子节点索引
int right = 2 * i + 2; // 右子节点索引
// 如果左子节点存在且大于当前最大值
if (left < n && arr[left] > arr[largest]) {
largest = left;
}
// 如果右子节点存在且大于当前最大值
if (right < n && arr[right] > arr[largest]) {
largest = right;
}
// 如果最大值不是当前节点，则交换并继续调整
if (largest != i) {
int swap = arr[i];
arr[i] = arr[largest];
arr[largest] = swap;
// 递归调整受影响的子树
heapify(arr, n, largest);
}
}
特点
- 时间复杂度：
- 最好情况：O(n log n)
- 平均情况：O(n log n)
- 最坏情况：O(n log n)
- 空间复杂度：O(1) - 原地排序算法
- 稳定性：不稳定排序算法（相同元素的相对位置可能改变）
- 适用场景：对空间复杂度有要求，且数据量较大的排序场景
四、希尔排序
描述：希尔排序（Shell Sort）是插入排序的一种更高效的改进版本，也称为递减增量排序算法。它通过将原始数组按照一定的间隔（gap）分成若干子序列，对这些子序列分别进行插入排序，然后逐步缩小间隔，最终当间隔为1时，进行一次完整的插入排序。
基本思想
- 设置一个间隔序列，通常初始间隔为数组长度的一半
- 按照间隔将数组分组，对每组进行插入排序
- 逐步缩小间隔，重复上述过程
- 当间隔为1时，进行最后一次插入排序，完成排序
工作原理
- 选择间隔：选择一个间隔序列，通常从数组长度的一半开始
- 分组排序：按照当前间隔将数组分组，对每组执行插入排序
- 缩小间隔：将间隔减小（通常除以2），重复分组排序过程
- 最终排序：当间隔为1时，进行一次完整的插入排序
public static void main(String[] args) {
int [] a = {5,3,2,4,1};
shellSort(a);
System.out.println(Arrays.toString(a));
}
// 希尔排序
public static void shellSort(int[] arr) {
int n = arr.length;
// 初始间隔为数组长度的一半，逐步缩小间隔
for (int gap = n / 2; gap > 0; gap /= 2) {
// 对每个间隔内的元素进行插入排序
for (int i = gap; i < n; i++) {
int key = arr[i]; // 当前要插入的元素
int j = i;
// 在间隔为gap的子序列中进行插入排序
while (j >= gap && arr[j - gap] > key) {
arr[j] = arr[j - gap]; // 将大于key的元素向后移动gap个位置
j -= gap;
}
arr[j] = key; // 插入当前元素到正确位置
}
}
}
特点
- 时间复杂度：
- 最好情况：O(n log n) - 数组已经基本有序
- 平均情况：O(n^1.3) - 根据间隔序列的选择而变化
- 最坏情况：O(n²) - 使用不当的间隔序列
- 空间复杂度：O(1) - 原地排序算法
- 稳定性：不稳定排序算法（相同元素的相对位置可能改变）
- 适用场景：中等规模数据排序，比插入排序更高效，实现相对简单
五、 ArrayList 排序
ArrayList本身是一种动态数组数据结构，它本身并不直接提供排序功能。在Java中，对ArrayList进行排序通常使用以下方式：
ArrayList排序方式
使用Collections.sort()方法
- 对于ArrayList，通常使用
Collections.sort()方法进行排序 - 该方法内部使用的是优化的归并排序（Timsort算法）
- 对于ArrayList，通常使用
使用Arrays.sort()方法
- 如果将ArrayList转换为数组，可以使用
Arrays.sort()方法 - 对于基本类型数组，使用双轴快速排序（Dual-Pivot Quicksort）
- 对于对象数组，使用Timsort算法
- 如果将ArrayList转换为数组，可以使用
ArrayList排序的具体实现
// 示例：ArrayList排序用法
ArrayList<Integer> list = new ArrayList<>();
list.add(5);
list.add(3);
list.add(2);
list.add(8);
list.add(1);
list.sort(Comparator.naturalOrder()); //升序
list.sort(Collections.reverseOrder()); //倒叙
// 使用Collections.sort()排序
Collections.sort(list); // 内部使用Timsort算法 //升序
Collections.sort(list, Collections.reverseOrder()); //倒叙
Timsort算法特点
- 混合排序算法：结合了归并排序和插入排序的优点
- 稳定排序：相等元素的相对位置不会改变
- 自适应性：对于部分有序的数据效率很高
- 时间复杂度：
- 最好情况：O(n) - 数据已经有序
- 平均情况：O(n log n)
- 最坏情况：O(n log n)
- 空间复杂度：O(n)
Collections.sort()方法的实现逻辑如下：
- 将ArrayList转换为数组
- 调用
Arrays.sort()方法对数组进行排序 - 将排序后的数组元素重新放回ArrayList
default void sort(Comparator<? super E> c) {
Object[] a = this.toArray();
Arrays.sort(a, (Comparator) c);
ListIterator<E> i = this.listIterator();
for (Object e : a) {
i.next();
i.set((E) e);
}
}
对于对象类型（如Integer、String等），Arrays.sort()使用Timsort算法，这是一种高度优化的归并排序变体。因此，可以说ArrayList在Java中排序时主要使用的是Timsort算法，它是一种稳定、高效的排序算法，实际应用中常见的部分有序数据。