时间戳

首页 > 解决方案 > 实现合并排序

java - 实现合并排序

问题描述

我已经实现了一个 MergeSorting，它采用一个 Generic Data 类型和一个上下索引边界，在它通过这些边界后停止排序。例如 {85,31,321,6549,123,2,1,0} lower = 0 upper = 4 将产生 [31,85,123,321,6549,2,1,0]。虽然当我测试我的代码时，它给出了一个 stackoverflow 错误，我不知道为什么。

我查看了我的代码，但找不到问题，也许我没有突破递归调用的边缘情况。

import java.util.ArrayList;
public class Sorts<T extends Comparable<? super T>> {
   public void merge(ArrayList<T> list, int start, int mid, int end)
   {
        ArrayList<T> tempArr = new ArrayList<T>(end - start);
        int leftidx = start;
        int rightidx = mid;
        while(true)
        {
            if (leftidx ==  mid)
            {
                tempArr.addAll(list.subList(rightidx,end)); 

                break;
            }
            else if (rightidx == end)
           {
                tempArr.addAll(list.subList(leftidx, mid));
                break;
           }

           T left = list.get(leftidx);
           T right = list.get(rightidx);

           int check = left.compareTo(right);

           if (check < 0) 
           {
               tempArr.add(left); 
               leftidx++; 
           }
           else
           {
               tempArr.add(right); 
               rightidx++; 
           }
        }

        for (int j = 0; j < tempArr.size(); j++)
        {
            list.set(start + j, tempArr.get(j));
        }




}
public void MergeSort(ArrayList<T> list, int start, int end) {

    int median = start + (end - start) / 2;
    MergeSort(list, start, median);
    MergeSort(list, median, end);
    merge(list, start, median, end);

   }
}

当我运行测试时，它在第 82 行给出错误“java.lang.StackOverflowError”，这是我的合并排序类中的 MergeSort(list,start,median)。我的测试员课程是：

public class SortsTester extends Sorts{
    public void mergeSortTester{
       Integer [] arr = {85,31,321,6549,123,2,1,0};
       ArrayList<Integer> ranArrLst = new ArrayList<>(Arrays.asList(arr));
       MergeSort(ranArrLst,0,7);
       System.out.println(Arrays.toString(ranArrLst.toArray()));
     }
}

标签： javaarraylist

解决方案

当元素少于两个时，您不应在 MergeSort 中执行任何操作：

public void MergeSort(ArrayList<T> list, int start, int end) {
    if ((end - start) < 2) {
        return;
    }
    int median = start + ((end - start) / 2);
    MergeSort(list, start, median);
    MergeSort(list, median, end);
    merge(list, start, median, end);
}

推荐阅读