0
我寫了一個適當的合併排序算法，用於排序隨機大小（100,000個元素或更多）的大量數據。我正在考慮在數據幾乎排序時進行插入排序，以使算法運行得更快一些。我想知道這是否可以用mergesort？正在完成一個就地mergesort算法與插入排序可能/可行？
這是我的一些代碼。
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++;
}
}
現在，我想通過計數器實現插入排序的元素個數當我第一次把它們到數組列表，然後改變了我的合併方法爲以下的。
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運行，因爲數據是完全隨機生成的，沒有接近幾乎排序的地方。
我在做什麼錯？有什麼建議麼？我的猜測是，因爲它就地合併排序它不會工作。
謝謝！