Question

This question is unlikely to help any future visitors; it is only relevant to a small geographic area, a specific moment in time, or an extraordinarily narrow situation that is not generally applicable to the worldwide audience of the internet. For help making this question more broadly applicable, visit the help center.

Closed 11 years ago.

我正在开发一种 c+++ 快速排序算法, 该算法将计算此类型中重大操作的数量。它将正确排序 100 个值, 但在此之后它会陷入无休止的循环中。任何帮助都会非常感激!

//快速求收

#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);
};

Answer 1

在您的分区函数中,分隔函数

 if (left < right)

总是真实的。因此,您正在得到无限的循环, 而( true) 循环。

从 SOCData.h 函数的大小() 函数中可能存在问题, 我们目前还看不到这个问题。

由于数据是随机的,所以您不时在某些输入组中看到问题。

微小修改必须帮助:

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

抱歉重复检查 :)

Answer 2

partitation 被卡住, 如果 left & lt; 右 和 theData[left] ==Data[right] 。

友情链接