tim排序java实现
时间: 2023-09-13 12:08:08 浏览: 42
以下是Java实现的tim排序示例代码:
```
public class TimSort {
private static final int MIN_MERGE = 32;
private int[] arr;
private int n;
private int[] buffer;
public void sort(int[] arr) {
this.arr = arr;
this.n = arr.length;
this.buffer = new int[n];
int minRun = minRunLength(MIN_MERGE);
for (int i = 0; i < n; i += minRun) {
int end = Math.min(i + minRun, n);
insertionSort(i, end);
}
for (int size = minRun; size < n; size <<= 1) {
for (int left = 0; left < n; left += 2 * size) {
int mid = left + size;
int right = Math.min(left + 2 * size, n);
merge(left, mid, right);
}
}
}
private void insertionSort(int start, int end) {
for (int i = start + 1; i < end; i++) {
int j = i;
while (j > start && arr[j] < arr[j - 1]) {
swap(j, j - 1);
j--;
}
}
}
private void merge(int left, int mid, int right) {
int i = left;
int j = mid;
int k = left;
while (i < mid && j < right) {
if (arr[i] < arr[j]) {
buffer[k++] = arr[i++];
} else {
buffer[k++] = arr[j++];
}
}
while (i < mid) {
buffer[k++] = arr[i++];
}
while (j < right) {
buffer[k++] = arr[j++];
}
for (k = left; k < right; k++) {
arr[k] = buffer[k];
}
}
private void swap(int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
private int minRunLength(int minMerge) {
int r = 0;
while (n >= minMerge) {
r |= (n & 1);
n >>= 1;
}
return n + r;
}
}
```
使用示例:
```
int[] arr = {5, 2, 4, 6, 1, 3};
TimSort timSort = new TimSort();
timSort.sort(arr);
System.out.println(Arrays.toString(arr));
```
输出结果:
```
[1, 2, 3, 4, 5, 6]
```
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)