2

我有这个快速排序实现来对字符进行排序。

int main(){
char val[] = "dcbeaaae";
    QuickSort(val, 0, length);

    for(int i=0;i<length;i++) //Sorted print
        cout<<val[i];
return 0
}

void QuickSort(char values[], int first, int last)
{
    if(first<last)
    {
        int splitPoint;
        Split(values, first, last, splitPoint);
        QuickSort(values, first, splitPoint-1);
        QuickSort(values, splitPoint+1, last);
    }
}

void Split(char values[], int first, int last, int& splitPoint)
{
    int splitVal = values[first];
    int saveFirst = first;
    bool onCorrectSide;

    first++;
    do
    {
        onCorrectSide = true;
        while(onCorrectSide)
        {
            if(values[first] > splitVal)
                onCorrectSide = false;
            else
            {
                first++;
                onCorrectSide = (first<=last);
            }
        }
        onCorrectSide = (first<=last);
        while(onCorrectSide)
            if(values[last] <= splitVal)
                onCorrectSide = false;
            else
            {
                last--;
                onCorrectSide = (first<=last);
            }

        if(first<last)
        {
            Swap(values[first], values[last]);
            first++;
            last--;
        }
    }while(first<=last);

    splitPoint = last;
    Swap(values[saveFirst], values[splitPoint]);
}

void Swap(char& item1, char& item2)
{
    char temp = item1;
    item1 = item2;
    item2 = temp;
}

但是，我从中得到的输出有点错误，即在这些排序字符的开头我得到了一个额外的空间。在放置断点时，我看到在 index 0，元素是 = 0

输入：aaabcdee
输出：（aaabcdee第一个 a 之前的一个额外空格）

有什么建议我在这里错过了吗？

4

1 回答 1

6

假设length是字符数组中的字符数（不包括 NUL 字符）。您需要将快速排序函数调用为：

QuickSort(val, 0, length-1);

因为函数的最后一个参数QuickSort是数组最后一个元素的索引，并且在长度为 的字符数组中length这个索引是length - 1.

通过传递length给该函数，您甚至可以使 NUL 字符参与排序，并且由于它比其他字符小，它被移动到已排序数组的开头，该数组在打印时打印为空白。

于 2012-06-08T18:03:14.597 回答