2

我正在研究一种 c++ 快速排序算法，该算法计算排序期间重要操作的数量。它会正确排序 100 个值，但之后会陷入无限循环。任何帮助将不胜感激！

//快速排序.cpp

#include "QuickSort.h"
#include <algorithm>

using namespace std;

QuickSort::QuickSort(int max) : SortData(max)
{
    /*
    maxSize = max;
    theData = new long[max];
    */
    SortData::randomize(12);

}

QuickSort::~QuickSort(void)
{

}

_int64 QuickSort:: sort()
{
    numops = 0;
    quicksort(theData, 0, (size()-1));
    return(numops);
}

//Include counting number of operations
void QuickSort::quicksort(long theData[], int left, int right)
{
    //Default variables

    if (size() <= 1 || left >= size() || right >= size()) return; //Bounds checking

    if (left < right)
    {
        long pivot = partition(theData, left, right);

        quicksort(theData, left, pivot-1);
        quicksort(theData, pivot+1, right);
    }
}

int QuickSort::partition(long theData[], int left, int right)
{
    long pivot = theData[left];
    while (true)
    {
        while (theData[left] < pivot) left++;
        numops ++;

        while (theData[right] > pivot) right--;
        numops ++; 

        if (left < right)
        {
            swap(theData[left], theData[right]);
            numops+=3;
        }

        else
        {
            return right;
        }
    }
}

//快速排序.h

#pragma once
#include "SortData.h"

class QuickSort : public SortData
{

public:
    QuickSort(int max = 100);
    ~QuickSort(void);
    _int64 sort();
private:
    _int64 numops;
    void QuickSort::quicksort(long theData[], int left, int right);
    int partition(long theData[], int left, int right);
};
4

2 回答 2

4

在你的分区函数中

 if (left < right)

总是正确的。因此，您将获得无限的 while(true) 循环。

并且 SortData.h 中的 size() 函数可能存在问题，我们还看不到。

由于数据是随机的，您会不时在某些输入集上看到问题。

稍作修改必须有帮助：

if (left <= right) {
         if (left < right) {
             swap(theData[left], theData[right]);
             numops += 3;
         }
         left++;
         right--;
}
else {
    return right;
}

很抱歉再次检查:)

于 2012-05-22T20:11:15.140 回答
1

partitionleft < right如果和会卡住theData[left] == theData[right]。

于 2012-05-22T20:15:14.847 回答