1

我不确定出了什么问题，但这不是正确的排序。

这是实现：

int quickSort(std::string **arr, int left, int right)
{
    static int swaps;
    int i = left, j = right;
    std::string *tmp;
    std::string pivot = *arr[(left + right) / 2]; //middle element
    //partition
    while( i <= j ) {
        while ((*arr[i]).compare(pivot) < 0) {
            i++;
        }
        while ((*arr[j]).compare(pivot) < 0) {
            j--;
        }
        if ( i <= j ) {
            swaps++;
            tmp = arr[i];
            arr[i] = arr[j];
            arr[j] = tmp;
            i++;
            j--;
        }
    }
    //recursion
    if ( left < j ) {
        quickSort(arr, left, j);
    }
    if ( i < right ) {
        quickSort(arr, i, right);
    }
    return swaps;
}

arr是一个字符串指针数组。每个索引指向一个字符串，在这种情况下，字符串都是名称。该方法肯定是进行交换，我只是无法理解它到底在做什么。

例如，给定这些初始值：

Pointer    Value
0055B5D8 - JAMES
0055B3F8 - JOHN
0055C808 - ROBERT
0055C8A8 - MICHAEL
0055CB88 - WILLIAM
0055CC28 - DAVID
0055CCC8 - RICHARD
0055CD68 - CHARLES
0055CE08 - JOSEPH
0055CEA8 - THOMAS

我的quickSort方法始终将它们按以下顺序移动：

Pointer    Value
0055C8A8 - MICHAEL
0055B5D8 - JAMES
0055C808 - ROBERT
0055B3F8 - JOHN
0055CB88 - WILLIAM
0055CEA8 - THOMAS
0055CE08 - JOSEPH
0055CD68 - CHARLES
0055CCC8 - RICHARD
0055CC28 - DAVID

“未排序”列表具有按升序排列的指针，因为我将所有这些指针一个接一个地分配以构建初始数组。但是“排序”列表似乎根本没有排序。

为清楚起见，目标是按字母顺序排列名称列表。

4

1 回答 1

6

您对枢轴的两侧使用相同的比较。这意味着您允许较小的值保留在右侧。您需要进行如下修改：

    while ((*arr[i]).compare(pivot) < 0) {
        i++;
    }

    while ((*arr[j]).compare(pivot) > 0) {    // <----
        j--;
    }

这是典型的复制粘贴错误。复制一段代码而不是从头开始编写时要小心。你的大脑很容易被欺骗，认为你改变了所有重要的部分。

于 2013-11-12T00:51:02.713 回答