0

我编写了一个就地合并排序算法，用于对大量随机大小（100,000 个元素或更多）的数据进行排序。我正在考虑在数据几乎排序时进行插入排序，以使算法运行得更快一点。我想知道这是否可能与就地合并排序？

这是我的一些代码。

public static void merge(ArrayList<String> list, int low, int high) {
   if (low < high) {
        int mid = (low + high) / 2;
        merge(list, low, mid);
        merge(list, mid + 1, high);
        mergeSort(list, low, mid, high);
    }

}

public static void mergeSort(ArrayList<String> list, int first, int mid,
        int last) {
    int left = first;
    int right = mid + 1;
    String holder = "";

    // if mid <= mid+1 skip merge
    if (compareTo(list.get(mid), list.get(right)) <= 0) {
        return;
    }

    while (left <= mid && right <= last) {
        // if left index <= right index then just add to left
        if (compareTo(list.get(left), list.get(right)) <= 0) {
            left++;
        } else {
            holder = list.get(right);
            copyList(list, left, right - left);//moves everything from left to right-left                       up one index in the arraylist
            list.set(left, holder);

            left++;
            mid++;
            right++;
        }
    }
    // what is left is in place

}

public static void copyList(ArrayList<String> source, int srcPos, int length) {
    String temp1 = "";
    String temp2 = source.get(srcPos);
    for (int i = 0; i < length; i++) {
        temp1 = source.get(srcPos + 1);
        source.set(srcPos + 1, temp2);
        temp2 = temp1;
        srcPos++;
    }
}

现在，当我第一次将元素放入 arraylist 时，我正在考虑通过计数器的数量来实现插入排序，然后将我的合并方法更改为以下。

public static void merge(ArrayList<String> list, int low, int high) {
   if(high-low==dataSize-1){
        int mid = (low + high) / 2;
        merge(list, low, mid);
        merge(list, mid + 1, high);
        insertionSort(list);
   }else if (low < high) {
        int mid = (low + high) / 2;
        merge(list, low, mid);
        merge(list, mid + 1, high);
        mergeSort(list, low, mid, high);
    }

}

但是，这实际上使我的算法具有永恒性。我猜我做错了，算法需要 n^2 来运行，因为数据是完全随机生成的，而且几乎没有排序。

我究竟做错了什么？有什么建议么？我的猜测是因为它就地合并排序它不会工作。

谢谢！

4

1 回答 1

0

这样的算法很复杂，很容易出错。我实现了一些非常相似的东西：就地稳定合并排序。它还对小型子列表使用插入排序。我建议查看源代码并将其与您正在做的事情进行比较。您可能还对就地稳定的快速排序感兴趣。

除非我弄错了，否则您的实现不稳定（它可能会重新排列相等的元素）。根据用例，这可能是也可能不是问题。

此外，您的实现似乎是 O(n^2) 因为 copyList 方法是 O(n) 并且它被调用 n 次。

关于插入排序：什么是dataSize以及为什么使用 equals 比较它？你不想<改用吗？如果你这样做，那else if (low < high)是多余的（它总是正确的）。

于 2012-10-25T07:15:02.860 回答