我的QuickSort和MergeSort不能正常工作

我的MergeSort和QuickSort調用插入當段爲< = 15個索引大小時進行排序。插入排序工作正常，合併工作正常，和分區工作正常，但我的MergeSort和QuickSort不能正常工作...他們似乎沒有排序...請幫助：我的QuickSort和MergeSort不能正常工作

這是我的插入排序功能方面，上下文：

int ndxCopy = 0, ndx, ndxSort, comp, result, ndxProper; 
String sortMe = null; 
for (ndx = (1 + firstIndex); ndx < numberToSort; ndx++) { 
    sortMe = data.get(ndx); 
    for (ndxSort = firstIndex; ndxSort < ndx; ndxSort++) { 
     comp = sortMe.compareTo(data.get(ndxSort)); 
     if (comp < 0) { 
      ndxProper = ndxSort; 
      for (ndxCopy = ndx; ndxCopy > ndxProper; ndxCopy--) 
       data.set(ndxCopy, data.get(ndxCopy - 1)); 

      data.set(ndxProper, sortMe); 
     } 
    } 
}

這是我的我的快速排序：

if (numberToSort <= 15) 
    insertionSort(data, firstIndex, numberToSort); 
else { 
    int partitionNdx = partition(data, firstIndex, numberToSort); 

    int sizeLeft = (partitionNdx - firstIndex); 
    int sizeRight = (numberToSort - sizeLeft - 1); 

    quickSort(data, firstIndex, sizeLeft); 
    quickSort(data, (firstIndex + sizeLeft + 1), sizeRight); 
}

這是我的分區： 的medianOfThree方法只是隨機數索引的範圍內產生3個數字，這些索引存儲3個值，並使用該值作爲樞軸...

int pivotNdx = medianOfThree(data, firstIndex, numberToPartition); 
String temp = data.get(firstIndex); 
String pivot = data.get(pivotNdx); 

data.set(firstIndex, pivot); 
data.set(pivotNdx, temp); 

int TooBigNdx = (firstIndex + 1), TooSmallNdx = (firstIndex + numberToPartition - 1); 

while (TooBigNdx < TooSmallNdx) { 
    while ((TooBigNdx < TooSmallNdx) && ((data.get(TooBigNdx)).compareTo(pivot) <= 0)) 
     TooBigNdx++; 

    while ((TooSmallNdx > firstIndex) && ((data.get(TooSmallNdx)).compareTo(pivot) > 0)) 
     TooSmallNdx--; 

    if (TooBigNdx < TooSmallNdx) { 
     temp = data.get(TooSmallNdx); 
     String TooBig = data.get(TooBigNdx); 

     data.set(TooSmallNdx, TooBig); 
     data.set(TooBigNdx, temp); 
    } 

} 

if (pivot.compareTo(data.get(TooSmallNdx)) >= 0) { 
    temp = data.get(firstIndex); 
    String TooSmall = data.get(TooSmallNdx); 

    data.set(firstIndex, TooSmall); 
    data.set(TooSmallNdx, temp); 

    return TooSmallNdx; 
} else 
    return firstIndex;

這是我的歸併方法：

if (numberToSort <= 15) 
    insertionSort(data, firstIndex, numberToSort); 
else { 
    int sizeLeft = (numberToSort/2); 
    int sizeRight = (numberToSort/2) + (numberToSort % 2); 

    mergeSort(data, firstIndex, sizeLeft); 
    mergeSort(data, (firstIndex + sizeLeft), sizeRight); 

    merge(data, firstIndex, sizeLeft, sizeRight); 
}

這是我的合併方法：

ArrayList<String> temp = new ArrayList<String>(); 
int ndxTemp = 0, ndxLeft = firstIndex, ndxRight = (firstIndex + leftSegmentSize), comp, ndx; 
String left, right; 
int sizeLeft = leftSegmentSize, sizeRight = rightSegmentSize; 

while ((sizeLeft > 0) || (sizeRight > 0)) { 
    if ((sizeLeft > 0) && (sizeRight > 0)) { 
     left = data.get(ndxLeft); 
     right = data.get(ndxRight); 

     comp = left.compareTo(right); 
     if (comp <= 0) { 
      temp.add(data.get(ndxLeft++)); 
      sizeLeft--; 
     } else { 
      temp.add(data.get(ndxRight++)); 
      sizeRight--; 
     } 
    } else { 
     if (sizeLeft > 0) { 
      temp.add(data.get(ndxLeft++)); 
      sizeLeft--; 
     } else { 
      temp.add(data.get(ndxRight++)); 
      sizeRight--; 
     } 
    } 
} 

ndx = firstIndex; 
for (ndxTemp = 0; ndxTemp < temp.size(); ndxTemp++) 
    data.set(ndx++, temp.get(ndxTemp));

請幫我找出什麼是錯的......

來源

2015-05-03 that-ru551an-guy

我的問題的根源竟然是在這行代碼：

for (ndx = (1 + firstIndex); ndx < numberToSort; ndx++) {

特別：

ndx < numberToSort

這應該改爲：

ndx < (numberToSort + firstIndex), as we are not necessarily starting at 0.

來源

2015-05-14 10:38:10

我的QuickSort和MergeSort不能正常工作

回答

相關問題