k部分归并排序
merge sort in k parts
我真的很感激能在这项作业上提供一些帮助。
任务是开发一种合并排序算法，将输入数组 "splits" 递归到 k 个数组中。我最初编写了两种方法来将合并排序分为两部分，即合并排序和合并。我试图概括这个算法
public class MergeSort {
public static int[] mergeSort(int[] a, int p, int r) {
// p is left bound
// r is right bound
if (p < r) {
int q = (int)Math.floor((p + r) / 2);
mergeSort(a, p, q);
mergeSort(a, q + 1, r);
return merge(a, p, q, r);
} else
return a;
}
// p ist linke grenze
// r ist rechte grenze
public static int[] merge(int[] a, int p, int q, int r) {
int n1 = q - p + 1; //length of first array
int n2 = r - q; //length of second array
int[] lt = new int[n1 + 1];
int[] rt = new int[n2 + 1];
for (int i = 0; i < n1; i++) {
lt[i] = a[p + i];
}
for (int j = 0; j < n2; j++) {
rt[j] = a[q + j + 1];
}
lt[n1] = 1000000000; //sentinels
rt[n2] = 1000000000;
int i = 0;
int j = 0;
for (int k = p; k <= r; k++) { //comparing the values of the arrays and merging
if (lt[i] <= rt[j]) {
a[k] = lt[i];
i++;
} else {
a[k] = rt[j];
j++;
}
}
return a;
}
public static int[] mergeSortK(int[] a, int k, int p, int r) {
// k number of steps; p is first index of array; r is last index of array;
if (p < r) {
int[] pos = new int[k + 1]; //array for saving the indices of the "splits"
for (int i = 0; i <= k; i++) {
pos[i] = (int) Math.floor(p + (r - p) / k * i); //saving the array indices
}
for (int i = 0; i < k; i++) {
mergeSortK(a, k, pos[i], pos[i + 1]); //sorting the arrays
}
for (int i = 0; i < k - 1; i++) {
merge(a, pos[i], pos[i + 1], pos[i + 2]); //merging the arrays pairwise
}
}
return a;
}
public static void main(String[] args) {
// task 2.1.a)
// Example Values:
int[] list = { 2, 1, 5, 6, 2, 12 };
int k = 4;
// use MergeSort
int[] newlist = mergeSortK(list, k, 0, list.length);
printList(newlist);
}
// Helper function to print the elements of a list
private static void printList(int[] list) {
for(int i = 0; i < list.length; i++) {
System.out.println(list[i]);
}
}
}
main 方法中给出的输入导致 {2, 1, 2, 5, 6, 12}
非常感谢任何帮助！对不起，如果我做错了，我是来学习的，我真的希望你们能帮助我！
您的代码中存在一些问题：
Math.floor()不需要截断整数除法的结果，不像Java脚本，Java对/和[=13=使用不同的语义] 参数和浮点参数。 (p + r) / 2 是积分商，但您可能想写 p + (r - p) / 2 以避免 p + r 上的潜在溢出。- 当您从
main() 传递 list.length 时，上面的索引被排除在外。这实际上是一个非常方便的约定，可以避免在计算切片大小时需要进行 +1 调整。删除那些错误的调整并依赖 included/excluded 约定。
- 不要使用标记：使用标记会阻止您正确排序包含大于或等于标记值
1000000000 的值的数组。这种做法是没有必要的，应该被禁止。只需将索引变量与切片长度进行比较，并在其中一个切片用完时复制剩余的元素。
- 您在
mergeSortK 中对切片边界的计算不正确：p + (r - p) / k * i 是用整数算法计算的，因此 (r - p) / k 在乘法之前四舍五入。如果 r - p 不是 k 的倍数，则最后一个切片结束索引将不等于 r。在除法之前乘法可以解决这个问题，但可能会溢出类型 int. 的范围
mergeSortK不进行k-way合并，而是进行一系列的部分合并，对k > 2.- 你的测试集有点小
这是更正后的版本：
public class MergeSort {
public static int[] mergeSort(int[] a, int p, int r) {
// p is left bound (included)
// r is right bound (excluded)
if (r - p >= 2) {
int q = p - (r - p) / 2;
mergeSort(a, p, q);
mergeSort(a, q, r);
return merge(a, p, q, r);
} else {
return a;
}
}
// p is left bound (included)
// q is start of right slice
// r is end of right slice (excluded)
public static int[] merge(int[] a, int p, int q, int r) {
int n1 = q - p; // length of first array
int n2 = r - q; // length of second array
int[] lt = new int[n1];
for (int i = 0; i < n1; i++) {
lt[i] = a[p + i];
}
int i = 0; // index into lt
int j = q; // index into a for right slice
int k = p; // index into a for merged list
while (i < n1 && j < r) { //comparing the values of the arrays and merging
if (lt[i] <= a[j]) {
a[k] = lt[i];
i++;
k++;
} else {
a[k] = a[j];
j++;
k++;
}
}
while (i < n1) { // copy remaining elements from right slice
a[k] = lt[i];
i++;
k++;
}
// remaining elements from right slice are already in place
return a;
}
public static int[] mergeSortK(int[] a, int k, int p, int r) {
// k amount of steps; p is first index of slice; r is last index of slice (excluded);
if (r - p >= 2) {
if (k > r - p)
k = r - p;
int[] pos = new int[k + 1]; //array for saving the indices of the "splits"
for (int i = 0; i <= k; i++) {
pos[i] = p + (r - p) * i / k; //saving the array indices
}
for (int i = 0; i < k; i++) {
mergeSortK(a, k, pos[i], pos[i + 1]); //sorting the arrays
}
while (k > 1) {
int i, n = 1;
for (i = 0; i < k - 1; i += 2) {
// merge slices 2 at a time: this will produce the expected output
// but is not a direct k-way merge.
merge(a, pos[i], pos[i + 1], pos[i + 2]);
pos[n++] = pos[i + 2];
}
if (i < k)
pos[n++] = pos[i + 1];
k = n - 1;
}
}
return a;
}
public static void main(String[] args) {
// task 2.1.a)
// Example Values:
int[] list = {
64, 36, 46, 31, 45, 52, 4, 48, 74, 59,
12, 16, 70, 67, 71, 26, 73, 34, 46, 84,
60, 16, 26, 68, 56, 57, 97, 6, 39, 74,
25, 69, 29, 69, 77, 26, 44, 53, 20, 6,
77, 31, 71, 91, 28, 6, 24, 75, 26, 33,
3, 20, 55, 94, 17, 81, 88, 32, 94, 32,
3, 90, 76, 69, 9, 96, 76, 53, 78, 14,
97, 32, 17, 15, 61, 63, 21, 0, 16, 14,
61, 4, 81, 86, 29, 29, 27, 57, 85, 5,
91, 54, 6, 68, 40, 88, 41, 9, 90, 51 };
int k = 4; // must be at least 2
// use MergeSort
int[] newlist = mergeSortK(list, k, 0, list.length);
printList(newlist);
}
// Helper function to print the elements of a list
private static void printList(int[] list) {
for (int i = 0; i < list.length; i++) {
System.out.println(list[i]);
}
}
}
我没有在 mergeSortK 末尾编写正确的 k 路合并阶段，上面的代码应该可以工作，但会在 ceil(log2(k)) 遍中合并 k 个切片。直接一次通过 k 路合并是棘手的，通常不值得。
我真的很感激能在这项作业上提供一些帮助。 任务是开发一种合并排序算法，将输入数组 "splits" 递归到 k 个数组中。我最初编写了两种方法来将合并排序分为两部分，即合并排序和合并。我试图概括这个算法
public class MergeSort {
public static int[] mergeSort(int[] a, int p, int r) {
// p is left bound
// r is right bound
if (p < r) {
int q = (int)Math.floor((p + r) / 2);
mergeSort(a, p, q);
mergeSort(a, q + 1, r);
return merge(a, p, q, r);
} else
return a;
}
// p ist linke grenze
// r ist rechte grenze
public static int[] merge(int[] a, int p, int q, int r) {
int n1 = q - p + 1; //length of first array
int n2 = r - q; //length of second array
int[] lt = new int[n1 + 1];
int[] rt = new int[n2 + 1];
for (int i = 0; i < n1; i++) {
lt[i] = a[p + i];
}
for (int j = 0; j < n2; j++) {
rt[j] = a[q + j + 1];
}
lt[n1] = 1000000000; //sentinels
rt[n2] = 1000000000;
int i = 0;
int j = 0;
for (int k = p; k <= r; k++) { //comparing the values of the arrays and merging
if (lt[i] <= rt[j]) {
a[k] = lt[i];
i++;
} else {
a[k] = rt[j];
j++;
}
}
return a;
}
public static int[] mergeSortK(int[] a, int k, int p, int r) {
// k number of steps; p is first index of array; r is last index of array;
if (p < r) {
int[] pos = new int[k + 1]; //array for saving the indices of the "splits"
for (int i = 0; i <= k; i++) {
pos[i] = (int) Math.floor(p + (r - p) / k * i); //saving the array indices
}
for (int i = 0; i < k; i++) {
mergeSortK(a, k, pos[i], pos[i + 1]); //sorting the arrays
}
for (int i = 0; i < k - 1; i++) {
merge(a, pos[i], pos[i + 1], pos[i + 2]); //merging the arrays pairwise
}
}
return a;
}
public static void main(String[] args) {
// task 2.1.a)
// Example Values:
int[] list = { 2, 1, 5, 6, 2, 12 };
int k = 4;
// use MergeSort
int[] newlist = mergeSortK(list, k, 0, list.length);
printList(newlist);
}
// Helper function to print the elements of a list
private static void printList(int[] list) {
for(int i = 0; i < list.length; i++) {
System.out.println(list[i]);
}
}
}
main 方法中给出的输入导致 {2, 1, 2, 5, 6, 12}
非常感谢任何帮助！对不起，如果我做错了，我是来学习的，我真的希望你们能帮助我！
您的代码中存在一些问题：
Math.floor()不需要截断整数除法的结果，不像Java脚本，Java对/和[=13=使用不同的语义] 参数和浮点参数。(p + r) / 2是积分商，但您可能想写p + (r - p) / 2以避免p + r上的潜在溢出。- 当您从
main()传递list.length时，上面的索引被排除在外。这实际上是一个非常方便的约定，可以避免在计算切片大小时需要进行+1调整。删除那些错误的调整并依赖 included/excluded 约定。 - 不要使用标记：使用标记会阻止您正确排序包含大于或等于标记值
1000000000的值的数组。这种做法是没有必要的，应该被禁止。只需将索引变量与切片长度进行比较，并在其中一个切片用完时复制剩余的元素。 - 您在
mergeSortK中对切片边界的计算不正确：p + (r - p) / k * i是用整数算法计算的，因此(r - p) / k在乘法之前四舍五入。如果r - p不是k的倍数，则最后一个切片结束索引将不等于r。在除法之前乘法可以解决这个问题，但可能会溢出类型int. 的范围
mergeSortK不进行k-way合并，而是进行一系列的部分合并，对k > 2. 来说是不够的
- 你的测试集有点小
这是更正后的版本：
public class MergeSort {
public static int[] mergeSort(int[] a, int p, int r) {
// p is left bound (included)
// r is right bound (excluded)
if (r - p >= 2) {
int q = p - (r - p) / 2;
mergeSort(a, p, q);
mergeSort(a, q, r);
return merge(a, p, q, r);
} else {
return a;
}
}
// p is left bound (included)
// q is start of right slice
// r is end of right slice (excluded)
public static int[] merge(int[] a, int p, int q, int r) {
int n1 = q - p; // length of first array
int n2 = r - q; // length of second array
int[] lt = new int[n1];
for (int i = 0; i < n1; i++) {
lt[i] = a[p + i];
}
int i = 0; // index into lt
int j = q; // index into a for right slice
int k = p; // index into a for merged list
while (i < n1 && j < r) { //comparing the values of the arrays and merging
if (lt[i] <= a[j]) {
a[k] = lt[i];
i++;
k++;
} else {
a[k] = a[j];
j++;
k++;
}
}
while (i < n1) { // copy remaining elements from right slice
a[k] = lt[i];
i++;
k++;
}
// remaining elements from right slice are already in place
return a;
}
public static int[] mergeSortK(int[] a, int k, int p, int r) {
// k amount of steps; p is first index of slice; r is last index of slice (excluded);
if (r - p >= 2) {
if (k > r - p)
k = r - p;
int[] pos = new int[k + 1]; //array for saving the indices of the "splits"
for (int i = 0; i <= k; i++) {
pos[i] = p + (r - p) * i / k; //saving the array indices
}
for (int i = 0; i < k; i++) {
mergeSortK(a, k, pos[i], pos[i + 1]); //sorting the arrays
}
while (k > 1) {
int i, n = 1;
for (i = 0; i < k - 1; i += 2) {
// merge slices 2 at a time: this will produce the expected output
// but is not a direct k-way merge.
merge(a, pos[i], pos[i + 1], pos[i + 2]);
pos[n++] = pos[i + 2];
}
if (i < k)
pos[n++] = pos[i + 1];
k = n - 1;
}
}
return a;
}
public static void main(String[] args) {
// task 2.1.a)
// Example Values:
int[] list = {
64, 36, 46, 31, 45, 52, 4, 48, 74, 59,
12, 16, 70, 67, 71, 26, 73, 34, 46, 84,
60, 16, 26, 68, 56, 57, 97, 6, 39, 74,
25, 69, 29, 69, 77, 26, 44, 53, 20, 6,
77, 31, 71, 91, 28, 6, 24, 75, 26, 33,
3, 20, 55, 94, 17, 81, 88, 32, 94, 32,
3, 90, 76, 69, 9, 96, 76, 53, 78, 14,
97, 32, 17, 15, 61, 63, 21, 0, 16, 14,
61, 4, 81, 86, 29, 29, 27, 57, 85, 5,
91, 54, 6, 68, 40, 88, 41, 9, 90, 51 };
int k = 4; // must be at least 2
// use MergeSort
int[] newlist = mergeSortK(list, k, 0, list.length);
printList(newlist);
}
// Helper function to print the elements of a list
private static void printList(int[] list) {
for (int i = 0; i < list.length; i++) {
System.out.println(list[i]);
}
}
}
我没有在 mergeSortK 末尾编写正确的 k 路合并阶段，上面的代码应该可以工作，但会在 ceil(log2(k)) 遍中合并 k 个切片。直接一次通过 k 路合并是棘手的，通常不值得。