合併排序 - 向量下標超出範圍

Question

我試圖得到一個合併排序程序工作，以及已經工作，使用向量的基數排序。

但是，合併排序總是給我「Vector下標超出範圍」的錯誤。我知道爲什麼會出現這個錯誤，但我無法弄清楚我應該採取什麼措施來阻止它。

代碼：

#include "Includes.h" 

class Mergesort 
{ 
public: 

std::vector<int> mergeSort(std::vector<int> list, int low, int high, int max) 
{ 
    int mid; 

    if (low < high) // Does not continue to merge sort when low is less than high. 
    { // This will be when the given set is a single number. 
     mid = low + (high - low)/2; 
     list = mergeSort(list, low, mid, max); // Split the given set into two halves down the middle. 
     list = mergeSort(list, mid + 1, high, max); 
     list = merge(list, low, mid, high, max); 
    } 

    return list; 
} 

std::vector<int> merge(std::vector<int> list, int low, int mid, int high, int max) // Call requires the bottom, middle and top numbers of the set. 
{ 
    int h, i, j, k; 
    std::vector<int> listb(max); // Merged list. 
    h = low - 1; 
    i = low - 1; 
    j = mid; 

    while ((h <= mid) && (j <= high)) 
    { 
     if (list[h] <= list[j]) // If the low part of the array is less than the upper middle of the array, 
     { 
      listb[i] = list[h]; // The next number in the merged array becomes h (initially low part). 
      h++; // Increment h to the next part of the array 
     } 
     else // Otherwise, 
     { 
      listb[i] = list[j]; // The next number in the merged array becomes j (initially upper middle). 
      j++; // Increment j to the next part of the array. 
     } 
     i++; // Always increment i, the position of the merged array. Starts at the bottom of the array. 
    } // End of while loop 

    if (h > mid) // If h - the progress from the bottom of the array - is beyond the middle. 
    { 
     for (k = j; k <= high; k++) // Loop until k is out of the array's range. 
     { 
      listb[i] = list[k]; // Set the next element in the merged array to the k element in the unmerged. 
      i++; // I.e. this starts from the middle, goes to the top of the array copying it into the merged one. 
     } 
    } 
    else // Otherwise, progress has not reached the the j value 
    { 
     for (k = h; k <= mid; k++) // K will start from h instead 
     { 
      listb[i] = list[k]; 
      i++; 
     } 
    } 
    // Then, 
    for (k = low; k <= high; k++) // Loop through the entire original array, copying the merged array into it. 
    { 
     list[k] = listb[k]; 
    } 

    return list; 
} 
}; 

和主：

#include "Mergesort.h" 
#include "Radixsort.h" 

// Import things we need from the standard library 
using std::chrono::duration_cast; 
using std::chrono::milliseconds; 
using std::cout; 
using std::endl; 
using std::this_thread::sleep_for; 

// Define the alias "the_clock" for the clock type we're going to use. 
// (You can change this to make the code below use a different clock.) 
typedef std::chrono::steady_clock the_clock; 

using namespace std; 

Mergesort mergeSorter; 
Radixsort radixSorter; 

void main() 
{ 
int num, i = 0, j = 0, k = 0; 
int inputNumber = 0; 

cout << "Please input the size of the list to sort, then press enter:" << endl; 
cin >> num; 

vector<int> intList(num); 

cout << endl << "Please enter a 1 for manual input or 2 for random generation between 0 and 99, then press enter:" << endl; 
while (j != 1 && j != 2) 
{ 
    cin >> j; 
    if (j != 1 && j != 2) 
    { 
     cout << "Please enter 1 or 2." << endl; 
    } 
    else 
    { 
     cout << endl; 
    } 
} 
if (j == 1) 
{ 
    cout << "Now, Please enter the " << num << " numbers, pressing enter between each:" << endl; 
    for (i = 0; i < num; i++) 
    { 
     cin >> inputNumber; 
     intList[i] = (inputNumber); 
    } 
} 
else if (j == 2) 
{ 
    for (i = 0; i < num; i++) 
    { 
     inputNumber = rand() % 100; 
     intList[i] = (inputNumber); 
    } 
    cout << "The list generated is: "; 
    for (std::vector<int>::iterator it = intList.begin(); it != intList.end(); it++) // Loops through the list, printing it out. 
    { 
     cout << *it << " "; 
    } 
    cout << endl << endl; 
} 

cout << endl << "Now, Please enter a 1 for merge sort or 2 for radix sort, then press enter:" << endl; 
while (k != 1 && k != 2) 
    { 
     cin >> k; 
     if (k != 1 && k != 2) 
     { 
      cout << "Please enter 1 or 2." << endl; 
     } 
    } 

if (k == 1) 
{ 
    intList = mergeSorter.mergeSort(intList, 1, num, num); 
    cout << endl << "So, the sorted list using merge sort will be:"; 
} 
else if (k == 2) 
{ 
    intList = radixSorter.radixSort(intList, num); 
    cout << endl << "So, the sorted list using radix sort will be:"; 
} 
cout << endl << endl; 

for (std::vector<int>::iterator it = intList.begin(); it != intList.end(); it++) // Loops through the list, printing it out. 
{ 
    cout << *it << " "; 
} 
cout << endl << endl; 
} 

Answer 1

參數Max從未使用過。通常，mergesort的正確索引是結束索引（比向量中的最後一個索引多一個索引）。在merge（）中，將h和i設置爲low-1會導致超出範圍的問題，將它們都設置爲低，而不是-1。由於合併拷貝回列表，然後歸併和合並應該是使用用於參數參考空隙功能：

void mergeSort(std::vector<int> &list, int low, int high) 

void merge(std::vector<int> &list, int low, int mid, int high) 

在歸併的主要代碼應該是：

if ((high-low) > 1) // nothing to do if 0 or 1 elements 
    { // This will be when the given set is a single number. 
     mid = low + (high - low)/2; 
     mergeSort(list, low, mid); 
     mergeSort(list, mid, high); 
     merge(list, low, mid, high; 

在合併早期線路應：

h = low; 
    i = low; 
    j = mid; 

    while ((h < mid) && (j < high)) // change <= to < 

使用<其他行=應改爲使用<。

的初始調用歸併排序應該是：

mergeSort(std::vector<int> list, 0, list.size()); 

您可能需要使用的size_t的指標，而不是INT。