sort java实现,这样merge可以在一个数组中工作,而第二个拆分的数组是反向的

elcex8rz  于 2021-06-29  发布在  Java
关注(0)|答案(1)|浏览(364)

挑战:在一次关于数据结构和算法的讲座中,我遇到了merge-sort的一个版本,它使用了merge例程,使后半部分与拆分索引相反,并从中比较第一个和最后一个元素。我尝试用java实现,但总是以某种方式失败。
问题:正在对数组进行排序,以便输出 [1, 2, 4, 8, 6] 所以 6 未排序。似乎递归调用没有查看元素 6 在过去 merge 打电话。
我尝试的是:移动不同的索引并添加不同的打印语句进行检查。我试着 j = r 最后一次之前 for 内循环 merge 每次都会导致堆栈溢出。我试图改变数组大小的计算方式,因为我不确定伪代码是否将数组从1或0开始。我试着换衣服 if(p < r-1)if(p <= r-1) 但是得到一个堆栈溢出。
我研究了java合并例程的不同实现,到目前为止,我发现的每个实现似乎都适用于两个数组。有没有一个严重的原因,为什么上述方法不能正常工作或任何想法如何解决这个问题?
给定以下伪代码:

  1. void merge_sort(array<T>& A, int p, int r) {
  2. if (p < r - 1) {
  3. int q = Floor((p + r) / 2);
  4. merge_sort(A, p, q);
  5. merge_sort(A, q + 1, r);
  6. merge(A, p, q, r);
  7. }
  8. }
  9. void merge(array<T>& A, int p, int q, int r) {
  10. array<T> B(p, r - 1);
  11. int i, j;
  12. for (i = p; i < q; i++)
  13. B[i] = A[i];
  14. // Now i=q
  15. for (j = r; i < r; i++)
  16. B[--j] = A[i];
  17. i = p;
  18. j = r - 1;
  19. for (int k = p; k < r; k++)
  20. A[k] = (B[i] < B[j]) ? B[i++] : B[j--];
  21. }

我试着用java实现如下:

  1. import java.util.Arrays;
  2. public class Mergesort {
  3. private static int[] A = new int[]{ 4, 2, 1, 8, 6 };
  4. public static void main(String[] args) {
  5. merge_sort(0, A.length - 1);
  6. System.out.println(Arrays.toString(A));
  7. }
  8. public static void merge_sort(int p, int r) {
  9. if (p < r - 1) {
  10. int q = Math.floor((p + r) / 2);
  11. merge_sort(p, q);
  12. merge_sort(q + 1, r);
  13. merge(p, q, r);
  14. }
  15. }
  16. public static void merge(int p, int q, int r) {
  17. int[] B = new int[r - p];
  18. int i, j;
  19. for (i = p; i < q; i++)
  20. B[i] = A[i]
  21. for (j = r; i < r; i++)
  22. B[--j] = A[i];
  23. i = p;
  24. j = r - 1;
  25. for (int k = p; k < r; k++)
  26. A[k] = (B[i] < B[j])? B[i++] : B[j--];
  27. }
  28. }
wvmv3b1j

wvmv3b1j1#

代码中存在多个问题:
临时数组太短:因为 r 是最后一个元素的索引,大小应为 r - p + 1 . 传递要简单得多 r 索引超过要排序的切片的最后一个元素。
第一个 for 循环不正确:应该使用不同的索引 B 以及 A .
第二个 for 循环复制到 B[r - 1] 向下,但应该使用 B[r - p] 相反。
合并循环不正确:您应该测试 i 以及 j 在进入前仍在各自的一半的边界内 B[i] 和/或 B[j] .
[次要]没有必要 int q = Math.floor((p + r) / 2); 在java中作为 p 以及 r 你有类型吗 int ,因此除法将使用整数算法。
以下是一个修改版本:

  1. public class Mergesort {
  2. private static int[] A = new int[]{ 4, 2, 1, 8, 6 };
  3. public static void main(String[] args) {
  4. merge_sort(0, A.length);
  5. System.out.println(Arrays.toString(A));
  6. }
  7. public static void merge_sort(int p, int r) {
  8. if (r - p >= 2) {
  9. int q = p + (r - p) / 2;
  10. merge_sort(p, q);
  11. merge_sort(q, r);
  12. merge(p, q, r);
  13. }
  14. }
  15. public static void merge(int p, int q, int r) {
  16. int m = q - p; // zero based index of the right half
  17. int n = r - p; // length of the merged slice
  18. int[] B = new int[n];
  19. int i, j, k;
  20. for (i = p, j = 0; j < m; j++)
  21. B[j] = A[i++];
  22. for (i = r, j = m; j < n; j++)
  23. B[j] = A[--i];
  24. for (i = 0, j = n, k = p; k < r; k++) {
  25. // for stable sorting, i and j must be tested against their boundary
  26. // A[k] = (i < m && (j <= m || B[i] <= B[j - 1])) ? B[i++] : B[--j];
  27. // stability is not an issue for an array of int
  28. A[k] = (B[i] <= B[j - 1]) ? B[i++] : B[--j];
  29. }
  30. }
  31. }

反转后半部分可以实现更简单的合并循环,而无需边界测试。但是请注意,有一种更简单的方法,它使用的内存更少,效率也可能更高:

  1. public static void merge(int p, int q, int r) {
  2. int m = q - p; // length of the left half
  3. int[] B = new int[m];
  4. int i, j, k;
  5. // only save the left half
  6. for (i = p, j = 0; j < m; j++)
  7. B[j] = A[i++];
  8. for (i = 0, j = q, k = p; i < m; k++) {
  9. A[k] = (j >= r || B[i] <= A[j]) ? B[i++] : A[j++];
  10. }
  11. }
展开查看全部

相关问题