快速排序模板不起作用，使我的程序无响应

Question

我正在尝试对生日向量进行排序（使用我的快速排序实现），并根据它们的变化方式更改包含姓名和生日的两个向量的顺序。我关注了一个关于如何实现快速排序的在线资源，但我不确定为什么它不起作用。这是我的代码：

template <class T>
void sortBDay(vector<T> &birthday, vector<string> &name, vector<T> &birthdate, int startPos, int size) { // This template sorts all data by their birthday
    if (startPos < size - 1) { // if the first value is less than the last value
        T pivotVal = birthday[startPos]; // the pivot value is the vector's first value
        int pivotPos = startPos; // the pivot position is the vector's starting position
        for (int pos = startPos + 1; pos <= size; pos++) { // repeat for all values of vector
            if (birthday[pos] < pivotVal) { // if the current position is less than the starting position
                swap(birthday[pivotPos + 1], birthday[pos]);
                swap(birthday[pivotPos], birthday[pivotPos + 1]); // switch the positions

                swap(name[pivotPos + 1], name[pos]); // and their names
                swap(name[pivotPos], name[pivotPos + 1]);

                swap(birthdate[pivotPos + 1], birthdate[pos]); // and their birthdates
                swap(birthdate[pivotPos], birthdate[pivotPos + 1]);
                pivotPos++; // then go onto the next one
            }
            sortBDay(birthday, name, birthdate, startPos, size - 1); // do the same for upper and lower pivots
            sortBDay(birthday, name, birthdate, startPos, size + 1); // recursion
        }   
    }
}

我不知道这个实现有什么问题。任何帮助，将不胜感激！提前致谢。

Answer 1

您将递归放入循环中，这不是快速排序的工作原理。传递给递归函数的开始和结束位置不正确。

这里是修复。我将参数 size 更改为 end 因为这就是代码中变量的行为方式。

template <class T>
void sortBDay(vector<T> &birthday, vector<string> &name, vector<T> &birthdate, int startPos, int end) { // This template sorts all data by their birthday
    if (startPos < end - 1) { // if the first value is less than the last value
        T pivotVal = birthday[startPos]; // the pivot value is the vector's first value
        int pivotPos = startPos; // the pivot position is the vector's starting position
        for (int pos = startPos + 1; pos < end; pos++) { // repeat for all values of vector
            if (birthday[pos] < pivotVal) { // if the current position is less than the starting position
                swap(birthday[pivotPos + 1], birthday[pos]);
                swap(birthday[pivotPos], birthday[pivotPos + 1]); // switch the positions

                swap(name[pivotPos + 1], name[pos]); // and their names
                swap(name[pivotPos], name[pivotPos + 1]);

                swap(birthdate[pivotPos + 1], birthdate[pos]); // and their birthdates
                swap(birthdate[pivotPos], birthdate[pivotPos + 1]);
                pivotPos++; // then go onto the next one
            }
        }   

        sortBDay(birthday, name, birthdate, startPos, pivotPos); // do the same for upper and lower pivots
        sortBDay(birthday, name, birthdate, pivotPos + 1, end); // recursion
    }
}

快速排序模板不起作用，使我的程序无响应

Quicksort template does not work, and makes my program unresponsive

c++

algorithm

quicksort