c++ - 使用模板实现排序类

Question

我昨晚发布了一个关于数组类的帖子，现在我在排序类上遇到了麻烦。大约一半的函数是教授定义的，或者是他给我们的算法定义的，但是很多定义让我感到困惑。我不确定是什么让它们与上面的有什么不同。

#ifndef SORTS_H
#define SORTS_H
#include <iostream>
#include <string>
#include "Array.h"
using namespace std;
template <class T>
void insertionSort(Array<T> &a);

template <class T>
void selectionSort(Array<T> &a);

template <class T>
void selectionSort(T a[], int n);

template <class T>
void mergesort(T *input, int size);

template <class T>
void mergesort(T *input, int left, int right, T *scratch);

template <class T>
T less(T x, T y);

template <class T>
void mergesort(Array<T> &input, int left, int right, Array<T>&scratch);

template <class T>
void mergesort(Array<T> & input);

Array<int> & random(int n);

template <class T>
void selectionSort(T a[], int n) {
    int i, j, tmp;
    int min_idx = 0;
    for (size_t i = 0; i < n-1; i++) {
        min_idx = i;
        for (size_t j = i+1; j < n; j++) {
            if (a[j] < a[min_idx]) {
                min_idx = j;
            }
            tmp = a[i];
            a[i] = a[min_idx];
            a[min_idx] = tmp;
        }
    }
}

template <class T>
void selectionSort(Array<T> &a) {
    int tmp;
    int min_idx = 0;

    for (int i = 0; i < a.getSize() - 1; i++) {
        min_idx = i;
        for (int j = i + 1; j < a.getSize(); j++) {
            if (a[j] < a[min_idx]) {
                min_idx = j;
            }
            tmp = a[i];
            a[i] = a[min_idx];
            a[min_idx] = tmp;
        }
    }
}

template <class T>
void insertionSort(Array<T> &a) {
    // put your code here 
}

template <class T>
bool sorted(Array<T> a) {

    for (int i = 1; i < a.getSize(); i++)
    if (a[i - 1] > a[i]) return false;

    return true;
}

Array<int> & random(int n) {
    Array<int> *tmp = new Array<int>(n);

    for (int i = 0; i < n; i++)
        (*tmp)[i] = rand() % 1000;

    return *tmp;
}

template <class T>
T less(T x, T y) {
    if (x < y) {
        return x;
    }
    else {
        return y;
    }
}

template <class T>
void mergesort(T *input, int left, int right, T *scratch) {
    if (right == left + 1) {
        return;
    }
    else {
        int i = 0;
        int length = right - left;
        int midpoint_distance = length / 2;
        int l = left, r = left + midpoint_distance;

        mergesort(input, left, left + midpoint_distance, scratch);
        mergesort(input, left + midpoint_distance, right, scratch);

        /* merge the arrays together using scratch for temporary storage */
        for (i = 0; i < length; i++) {
            /* Check to see if any elements remain in the left array; if so,
            * we check if there are any elements left in the right array; if
            * so, we compare them.  Otherwise, we know that the merge must
            * use take the element from the left array */
            if (l < left + midpoint_distance &&
               (r == right || min(input[l], input[r]) == input[l])) {
                scratch[i] = input[l];
                l++;
            }
            else {
                scratch[i] = input[r];
                r++;
            }
        }
        /* Copy the sorted subarray back to the input */
        for (i = left; i < right; i++) {
            input[i] = scratch[i - left];
        }
    }
}

template <class T>
void mergesort(T *input, int size) {
    int *scratch = new int[size];
    mergesort(input, 0, size, scratch);
    delete [] scratch;
}

template <class T>
void mergesort(Array<T> &input, int left, int right, Array<T>&scratch) {
    if (right == left + 1) {
        return;
    }
    else {
        int i = 0;
        int length = right - left;
        int midpoint_distance = length / 2;
        int l = left, r = left + midpoint_distance;

        mergesort(input, left, left + midpoint_distance, scratch);
        mergesort(input, left + midpoint_distance, right, scratch);

        /* merge the arrays together using scratch for temporary storage */
        for (i = 0; i < length; i++) {
            /* Check to see if any elements remain in the left array; if so,
            * we check if there are any elements left in the right array; if
            * so, we compare them.  Otherwise, we know that the merge must
            * use take the element from the left array */
            if (l < left + midpoint_distance &&
               (r == right || min(input[l], input[r]) == input[l])) {
                scratch[i] = input[l];
                l++;
            }
            else {
                scratch[i] = input[r];
                r++;
            }
        }
        /* Copy the sorted subarray back to the input */
        for (i = left; i < right; i++) {
            input[i] = scratch[i - left];
        }
    }
}

template <class T>
void mergesort(Array<T> &input) {
    // put your code here 
}

#endif

我还注意到有一个 void insertionSort(Array<T> &a);函数，但我得到的算法是:

void insertionSort(int a[], int n){
    int tmp;
    int i, j;

    for (i = 1; i < n; i++) {
        tmp = a[i];

        for (j = i - 1; j >= 0; j--)

        if (a[j] > tmp) a[j + 1] = a[j];
        else break;
        a[j + 1] = tmp;
    }
}

我是否应该以同样的方式实现它，只是替换 int a[]与，说... &arr ？我猜是因为这包括 array.h数组类有 T * arr; ，我应该指向那个数组的地址？这是否也适用于在其参数中包含地址运算符的每个定义？

Answer 1

区别在于，如您所说，采用典型的 int 数组 a[]，但您如何知道大小？所以这个版本要求用户将其发送给以n为元素个数的函数。在您的 Array 类中，您提供了一个大小，因此不需要它。通常，您会为多种情况提供重载。

我不确定你用 &arr 替换 int a[] 是什么意思，签名在那里，使用给你的东西，除非你是应该改变它。

如果您回到有关 Array 类的问题，您会看到一个答案，它像往常一样使用引用，即，

template <class T>
Array<T>::Array(const Array &other) : size(other.size), arr(new T[size])
{                        // ^^^^^^
  for (int i = 0; i < size; ++i)
    arr[i] = other.arr[i];
}         // ^^^^^

现在将其应用于这种情况。

此外，

template <class T>
void selectionSort(Array<T> &a) {
    // I'm not sure I understand what this is supposed to do that's different from the above selectionSort.
    // I know that & is the reference operator, so should I just return whatever &a is?
}

考虑到 void 作为返回和引用的使用，您不会在此处返回任何内容。您通过引用而不是通过值传递，以便您在函数中所做的事情是持久的。您可以选择传回已排序的数组而不使用引用，但我相当确定考虑到赋值和复制，它总体上会更慢。这就是为什么您的其他问题中的示例使用 const Array &other 的原因。它可以防止整个数组(可能很大)被复制并发送到函数以及被更改。