Java算法之TimSort

2024/10/24 17:22:40 来源：https://blog.csdn.net/weixin_38959316/article/details/141683724 浏览: 次关键词：Java算法之TimSort

TimSort简介

TimSort是一种高效的排序算法，由Tim Peters于2002年设计，主要特点是结合了归并排序（Merge Sort）和插入排序（Insertion Sort）的优点。这种算法在很多编程语言的默认排序函数中得到应用，如Python的sort()和Java的Arrays.sort()。

算法原理

TimSort的工作原理如下：

分解：将待排序数组分解为小的有序序列，每个序列长度为minrun。
插入排序：对每个minrun大小的小数组使用插入排序，因为小数组的插入排序非常高效。
归并排序：递归地将有序序列合并成更大的有序序列，直到整个数组有序。

代码实现

以下是使用Java实现TimSort的示例代码：

public class TimSort {private static final int MIN_RUN_SIZE = 32; // 定义最小运行大小// 插入排序辅助函数private static void insertionSort(int[] arr, int left, int right) {for (int i = left + 1; i <= right; i++) {if (arr[i] < arr[i - 1]) {int temp = arr[i];int j = i - 1;while (j >= left && arr[j] > temp) {arr[j + 1] = arr[j];j--;}arr[j + 1] = temp;}}}// 归并两个有序序列private static void merge(int[] arr, int l, int m, int r) {int n1 = m - l + 1;int n2 = r - m;// 创建临时数组int[] L = new int[n1];int[] R = new int[n2];// 复制数据到临时数组System.arraycopy(arr, l, L, 0, n1);System.arraycopy(arr, m + 1, R, 0, n2);// 合并临时数组回到原数组arr[l..r]int i = 0, j = 0, k = l;while (i < n1 && j < n2) {if (L[i] <= R[j]) {arr[k++] = L[i++];} else {arr[k++] = R[j++];}}// 复制左数组中的剩余元素while (i < n1) {arr[k++] = L[i++];}// 复制右数组中的剩余元素while (j < n2) {arr[k++] = R[j++];}}// 计算minrunprivate static int calculateMinRun(int n) {return (n | (n >> 1)) + 1;}// TimSort主函数public static void timSort(int[] arr) {int n = arr.length;int minRun = calculateMinRun(n);// 对每个minRun大小的序列进行插入排序for (int i = 0; i < n; i += minRun) {insertionSort(arr, i, Math.min(i + minRun - 1, n - 1));}// 逐步合并for (int size = minRun; size < n; size *= 2) {for (int left = 0; left < n; left += size * 2) {int mid = left + size - 1;int right = Math.min(left + size * 2 - 1, n - 1);merge(arr, left, mid, right);}}}public static void main(String[] args) {int[] arr = {-2, 3, 0, 9, 6, 5, 4, 67, 2, 8, 1};timSort(arr);System.out.println("排序后的数组: ");for (int value : arr) {System.out.print(value + " ");}}
}