C++ Quicksort字符串指针数组

Question

我不确定是什么问题,但这不是正确的.

这是实施:

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

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

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

Answer 1

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

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

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

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