1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
| /**
* 原地归并排序实现
* 减少额外内存使用
*/
public class InPlaceMergeSort {
/**
* 原地归并排序主函数
*/
public static void inPlaceMergeSort(int[] arr) {
if (arr.length <= 1) return;
mergeSortHelper(arr, 0, arr.length - 1);
}
private static void mergeSortHelper(int[] arr, int left, int right) {
if (left >= right) return;
int mid = left + (right - left) / 2;
mergeSortHelper(arr, left, mid);
mergeSortHelper(arr, mid + 1, right);
inPlaceMerge(arr, left, mid, right);
}
/**
* 原地合并两个有序子数组
* 使用循环位移的方法
*/
private static void inPlaceMerge(int[] arr, int left, int mid, int right) {
int start2 = mid + 1;
// 如果已经有序，直接返回
if (arr[mid] <= arr[start2]) {
return;
}
while (left <= mid && start2 <= right) {
if (arr[left] <= arr[start2]) {
left++;
} else {
int value = arr[start2];
int index = start2;
// 将元素向右移动
while (index != left) {
arr[index] = arr[index - 1];
index--;
}
arr[left] = value;
// 更新所有指针
left++;
mid++;
start2++;
}
}
}
/**
* 使用块交换优化的原地归并
*/
public static void inPlaceMergeSortOptimized(int[] arr) {
if (arr.length <= 1) return;
mergeSortOptimizedHelper(arr, 0, arr.length - 1);
}
private static void mergeSortOptimizedHelper(int[] arr, int left, int right) {
if (left >= right) return;
int mid = left + (right - left) / 2;
mergeSortOptimizedHelper(arr, left, mid);
mergeSortOptimizedHelper(arr, mid + 1, right);
blockSwapMerge(arr, left, mid, right);
}
/**
* 使用块交换的原地归并
*/
private static void blockSwapMerge(int[] arr, int left, int mid, int right) {
int leftLen = mid - left + 1;
int rightLen = right - mid;
if (leftLen == 0 || rightLen == 0) return;
// 使用二分查找和块交换进行优化
if (leftLen <= rightLen) {
blockSwapMergeHelper(arr, left, mid + 1, leftLen, rightLen);
} else {
// 翻转两个子数组，然后递归处理
reverse(arr, left, mid);
reverse(arr, mid + 1, right);
reverse(arr, left, right);
blockSwapMergeHelper(arr, left, left + rightLen, rightLen, leftLen);
}
}
private static void blockSwapMergeHelper(int[] arr, int left1, int left2, int len1, int len2) {
if (len1 == 0 || len2 == 0) return;
if (len1 == 1 && len2 == 1) {
if (arr[left1] > arr[left2]) {
swap(arr, left1, left2);
}
return;
}
int mid1 = len1 / 2;
int pos = binarySearch(arr, left2, left2 + len2 - 1, arr[left1 + mid1]);
// 计算新的长度
int newLen2 = pos - left2;
int newLen1 = len2 - newLen2;
// 块交换
blockSwap(arr, left1 + mid1, left2, newLen2);
// 递归处理
blockSwapMergeHelper(arr, left1, left1 + mid1, mid1, newLen2);
blockSwapMergeHelper(arr, left1 + mid1 + newLen2, pos, len1 - mid1, newLen1);
}
private static int binarySearch(int[] arr, int left, int right, int target) {
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return left;
}
private static void blockSwap(int[] arr, int start1, int start2, int len) {
for (int i = 0; i < len; i++) {
swap(arr, start1 + i, start2 + i);
}
}
private static void reverse(int[] arr, int start, int end) {
while (start < end) {
swap(arr, start++, end--);
}
}
private static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
|