0

我有一个抽象基类（Comparable），它实际上继承了日期和时间，还有一个继承自日期和时间的 DateTime 类。

我的问题是：我的任务是动态分配一个 Comparables 数组。

Comparable ** compArray;
compArray = new Comparable *[n]; // where n is user specified number of elements

然后我以交替的顺序用 DateTimes 填充数组。我需要使用快速排序和冒泡排序组合对这个数组进行排序。如果长度 < 8 则为气泡。Comparable** from 和 Comparable ** to 是我被允许使用的唯一参数。

但我完全被困住了。在这一点上，它不值得粘贴在我的代码中，因为它非常随意。

任何帮助将不胜感激。我花了过去几个小时试图完成这个，我的项目中只剩下排序。明天上午晚些时候到期。

在此先感谢，乔尔

编辑：

  void Sort(Comparable** a);
  void quicksort(Comparable** from, Comparable** to);   
  Comparable** partition(Comparable** from, Comparable** to);
  void Swap(Comparable** from, Comparable** to);    
  void safeRead(istream& sin, Comparable* d, const char* prompt);
  void printArray(ostream & sout, Comparable **a, int size);

我得到了上面的用作我的arraySort.h

我正在使用：int aSize = _msize(a) / sizeof(Comparable) - 1;作为我的长度变量......我必须计算而不是传递它，这有点烦人。

我主要只是对取消引用 ** 并在快速排序中调用它的 lessThan 或 equals 方法感到头疼。一旦我了解如何使用它进行快速排序，我就会“点击”，我就可以轻松地进行冒泡排序。

编辑：我目前有以下作为我的冒泡排序，它根本不对数组进行排序。

  void Swap(Comparable** from, Comparable** to)
  {
    Comparable** tmp;

    tmp = from;
    **from = **to;
    to = tmp;

  }

  void bubbleSort(Comparable** a, int size)
  {

    int i, j;

      for (i=0; i<size-1; i++)
      {
        for (j= size - 1; j > i; j--)
          if(a[j]->lessThan(*a[j-1]))
            Swap(&a[j], &a[j-1]);

      }
  }
4

4 回答 4

2

你必须有交替的日期和时间，所以你不需要创建 DateTime 对象，是吗？

请记住，您正在对就地数组进行排序。From 和 to 类似于 STL 容器的 begin() 和 end() 部分。

void QuickSort(Comparable** from, Comparable** to)
{
    int n = to - from;
    if (n < 8) BubbleSort(from, to);
    else {
        // the trick in here is remembering you have to sort in pairs
    }
}

Comparable** array = new Comparable*[n];
for (int i = 0; i < n; i += 2) {
    array[i] = new Date();
    array[i+1] = new Time();
}

// sort it
QuickSort(array, array+n);
于 2009-10-16T01:02:06.517 回答
1

Comparable**from 和Comparable**to 是我可以使用的唯一参数。

这有点傻，因为有一个 size 参数会是一个更好的 API。

无论如何，一种解决方法（我不知道它允许什么）是做 C 对字符串所做的事情：即使数组一（1）个元素比分配它时需要的大，并设置它最后一个元素为零（null）以标记数组的结尾（以便被调用者可以查找空指针以发现数组的结尾）。

于 2009-10-16T00:35:21.270 回答
1

您应该为您的类重载运算符“<”，以便您可以比较其中两个以便对它们进行排序。之后，就是实现冒泡排序和快速排序的问题了，这很简单（你会在 google 中找到大量的解释和示例代码）。也许我不明白你的问题到底是什么，所以如果这没有帮助，请更明确:)

于 2009-10-16T00:48:36.790 回答
1

请记住以下行：

Comparable ** compArray = new Comparable *[n];

...正在分配一个指针数组；它没有分配任何实际对象。所以分配上述数组后接下来要做的就是将compArray中的每个指针设置为指向一个有效对象。（您是通过为每个对象调用 new 来设置它们，还是将指针设置为指向您在其他地方拥有的现有对象，当然取决于您）

假设您已经这样做了，接下来您可能想要做的是编写一个 IsLessThan() 函数，该函数根据它们指向的内容比较两个指针：

bool IsLessThan(const Comparable * a, const Comparable * b) {return (*a) < (*b);}

请注意，上面与比较指针本身有很大不同！

之后的下一步是编写一个 BubbleSort 函数来对数组进行排序。它可能看起来像这样：

 void BubbleSort(Comparable ** ptrArray, int arrayLen)
 {
    [... bubble sort routine would go here ...]
 }

...并且它可以重复遍历数组中的指针，并且每当它发现一对顺序错误的相邻指针时（即 IsLessThan(ptrArray[i], ptrArray[i+1]) == false )，交换指针。一旦它通过整个数组传递而无需交换任何指针，你就知道你已经完成了，你可以允许函数返回。

一旦它正常工作（当然效率会很低，但没关系），最后一步是编写 QuickSort 例程：

 void QuickSort(Comparable ** ptrArray, int arrayLen)
 {
    if (arrayLen < 8) BubbleSort(ptrArray, arrayLen);
    else
    {
        [... quick sort routine would go here ...]
    }
 }

我对 QuickSort 的记忆不够好，无法在这里解决它，但希望以上内容至少能让你完成任务的大部分时间。

于 2009-10-16T00:50:18.333 回答