快速排序算法打印分段错误，无法正常工作

Question

我目前正在研究一种快速排序算法，该算法接受随机双精度数、整数、字符和浮点数。目前正在测试双打，我得到了

(process 27368) exited with code -1073740791

。我确实知道这是一个段错误，但我没有发现我所拥有的问题。代码是 C++ 的。这是：

// Code for generating random doubles
vector<double> generateDouble(int size, double min, double max)
{
    srand(time(0));
    vector<double> array(size);

    for (int index = 0; index < size; ++index)
    {
        double r = (((double)rand() / (double)RAND_MAX) * (max - min)) + min;
        array[index] = r;
    }

    return array;
}

// here is the getIter() function
int Sorting::getIter() const
{
    return iter;
}

void Sorting::quickSort()
{
    int first = 0;
    int last = listData.size() - 1;
    quickSort(listData, first, last);
}

void Sorting::quickSort(vector<double>& list, int first, int last)
{
    if (first < last)
    {
        int index = partition(list, first, last);

        quickSort(list, first, index - 1);
        quickSort(list, index + 1, last); // Corrected index
    }
}

int Sorting::partition(vector<double>& list, int first, int last)
{
    double pivot = list[last - 1];
    int i = first - 1; // Initialize i with first instead of (first - 1)

    for (int j = first; j < last; j++)
    {
        if (list[j] < pivot)
        {
            // Increment i before swapping
            i++;
            swap(list[i], list[j]);
        }
        iter++;
    }
    // Swap pivot with the element at (i + 1)
    swap(list[i], list[last - 1]);
    return i;
}

// how I am calling it in main

Sorting quickDSort(dd);
time.startTimer();
quickDSort.quickSort();
time.stopTimer();
cout << "(quick sort) Double Iterations: " << quickDSort.getIter() << endl;
cout << time.getSeconds() << endl;

我已经被困了一段时间，不知道该怎么办。谢谢。

我需要代码来获取

vector<double>

并对其进行排序。目前，它不会打印对数字进行排序所需的次数。

Answer 1

在代码中看到与您实际执行的操作无关的注释很奇怪。 举个例子，

    // Swap pivot with the element at (i + 1)
    swap(list[i], list[last - 1]);

...您

不

与(i + 1)处的元素交换，实际上您

应该

。 其次，当前子数组中的最后一个元素不在

last-1

处，而是在

last

处。所以这个索引也是错误的，无论是在上面引用的代码中，还是在

partition

函数的开头。这是您的

partition

函数，并纠正了这些错误：

int partition(vector<double>& list, int first, int last)
{
    double pivot = list[last]; // Should be last, not last-1
    int i = first - 1;

    for (int j = first; j < last; j++)
    {
        if (list[j] < pivot)
        {
            i++;
            swap(list[i], list[j]);
        }
    }
    i++; // Must increment
    swap(list[i], list[last]); // Should be last, not last-1
    return i;
}