0

我正在尝试实现一个快速排序算法，以通过 4 个不同标准之一对填充了“电影”类型的对象的数组进行排序。每个电影对象都包含一个排名、票数、评级和电影名称。我还在类定义中编写了 4 个静态 bool 函数，它们接受两个电影对象引用，如果第一个更小则返回 true，如果更大则返回 false。

前任：

bool Movie::GetLowerRank(const Movie& x, const Movie& y){
    if (x.rank < y.rank)
        return true;
    else
        return false;
}

就像我说的那样，我正在尝试实现一个快速排序算法，该算法将根据用户偏好对数组进行排序。我想将我的 4 个排序函数之一传递给我的快速排序函数，类似于向量排序的工作方式。我的问题是我有两个快速排序函数，递归函数和基函数：

void quickSort(Movie array[], int min, int max, bool (*compare_function)(Movie&, Movie&)){
    if (min < max) {
        int pivot_i = (min + max)/2;
        int pivot_i2 = quickSort(array, min, max, pivot_i, compare_function);
        quickSort(array, min, pivot_i2 - 1);
        quickSort(array, pivot_i2 +1, max);
    }   
}

int quickSort(Movie array[], int min, int max, int pivot, bool (*compare_function)(Movie& a, Movie& b)){
    Movie pivot_entry = array[pivot];
    swap (array[pivot], array[max]);
    int pivot_final_index = min;
    for (int i = min; i < max; i++) {
        if(compare_function(array[i], pivot_entry)){
            swap(array[i], array[pivot_final_index]);
            ++pivot_final_index;
        }
    }
    swap(array[max], array[pivot_final_index]);
    return pivot_final_index;
}

我试图将函数参数添加到参数列表中，但我不知道如何让 void quickSort 将函数（在 main 中获得）传递给实际使用它的 int quickSort。

4

2 回答 2

1

首先简化GetLowerRank为

bool Movie::GetLowerRank(const Movie& x, const Movie& y) {
    return x.rank < y.rank;
}

compare_function只是作为最后一个参数传递给quickSort. 既然void quickSort(...)调用了int quickSort(...)，你当然必须先声明或定义int quickSort() 。否则void quickSort()会尝试调用自身并抱怨参数数量不匹配

int quickSort(Movie array[], int min, int max, int pivot, bool (*compare_function)(Movie& a, Movie& b)){
    Movie pivot_entry = array[pivot];
    swap (array[pivot], array[max]);
    int pivot_final_index = min;
    for (int i = min; i < max; i++) {
        if(compare_function(array[i], pivot_entry)){
            swap(array[i], array[pivot_final_index]);
            ++pivot_final_index;
        }
    }
    swap(array[max], array[pivot_final_index]);
    return pivot_final_index;
}

void quickSort(Movie array[], int min, int max, bool (*compare_function)(Movie&, Movie&)){
    if (min < max) {
        int pivot_i = (min + max)/2;
        int pivot_i2 = quickSort(array, min, max, pivot_i, compare_function);
        quickSort(array, min, pivot_i2 - 1, compare_function);
        quickSort(array, pivot_i2 +1, max, compare_function);
    }   
}
于 2013-05-07T21:14:53.017 回答
0

第一个 quickSort 中的递归调用似乎是在没有使用函数指针的情况下调用的：

    quickSort(array, min, pivot_i2 - 1);
    quickSort(array, pivot_i2 +1, max);

下面的代码使用函数指针并将编译：

注意： int 已被替换为 Movie：

如果仍然存在错误，Movie这是一个好主意，即使不是严格需要验证

(1) the assignment operator and 
(2) copy constructor and 
(3) equality operator

（所有三个）都是为电影定义的（你可能已经知道了）。 

void quickSort(int array[], int min, int max, bool (*compare_function)(int&, int&));

int quickSort(int array[], int min, int max, int pivot, bool (*compare_function)(int& a, int& b));

void swap(int array[], int a, int b);


void swap(int array[], int a, int b) {
    int temp;
    if (array != NULL) {
        temp = array[a];
        array[a] = array[b];
        array[b] = temp;

    }

}

void quickSort(int array[], int min, int max, bool (*compare_function)(int&, int&)){

    if (min < max) {

        int pivot_i = (min + max)/2;
        int pivot_i2 = quickSort(array, min, max, pivot_i, compare_function);
        quickSort(array, min, pivot_i2 - 1, compare_function);
        quickSort(array, pivot_i2 +1, max, compare_function);
    }   
}

int quickSort(int array[], int min, int max, int pivot, 
    bool (*compare_function)(int& a, int& b)){

    int pivot_entry = array[pivot];

    swap (array, pivot, max);

    int pivot_final_index = min;

    for (int i = min; i < max; i++) {
        if(compare_function(array[i], pivot_entry)){
            swap(array, i, pivot_final_index);
            ++pivot_final_index;
        }
    }
    swap(array, max, pivot_final_index);
    return pivot_final_index;
}
于 2013-05-07T21:16:36.567 回答