0

所以我试图用算法对字符串数组进行排序。

注意：对于这个作业，我不允许使用任何内置的排序功能。

public boolean insert(String s)
{
  boolean result = false;
  int index = 0;
  int k = 0;
  String temp = "";

  if (numUsed < values.length)
  {
    if (index == 0) 
    {
      values[index] = s;
    }    
    else 
    {
      index = 0;
      while (values[index].compareTo(s) < 0);
      k = index;
      while (k < numUsed)
      {
        values[k + 1] = values[k];
      }
      values[index] = s;
    }
    numUsed++;
    result = true;
  }
}

给定“apples”、“cats”和“bees”的输入，输出的顺序与输入的顺序相同。无论我做什么，它似乎永远不会排序。

有人可以帮我找到问题吗？

4

2 回答 2

0

从回到基础开始。想象一下，你面前有一大堆随机排序的索引卡，你需要按字母顺序排列它们。一个简单但可行的方法是首先找到所有以 A 开头的单词，然后将它们放在一个单独的堆中（提示：如何在程序中模拟单独的堆？）。然后你遍历第一堆，找到所有以 B 开头的单词，并将它们放在排序后的堆的后面（另一个提示）。

我建议将您当前的代码放在一边并重新开始。编写一个遍历未排序数组的循环，并找到最接近字典开头的单词。这里有一些伪代码可以帮助您开始：

String leastSoFar = "ZZZZZZ";
for each String in values:
    compare the string to leastSoFar
    if the string is closer to the start of the dictionary than leastSoFar:
        leastSoFar = ???? //I'll let you fill those in
于 2013-10-01T05:22:20.023 回答
0

对集合进行排序和向集合添加元素通常是两个独立的功能。当然，可以以对元素进行排序的方式将元素添加到集合中……但这与简单地对元素数组进行排序是一项非常不同的任务。

如果您只是尝试实现一个简单的排序算法，那么一种易于编码的简单（但不是最优）算法就是“延迟替换排序”。伪代码 fpr 将算法按升序排序如下：

 Begin DELAYEDSORT
     For ITEM=1 to maximum number of items in list-1
        LOWEST=ITEM
        For N=ITEM+1 to maximum number of items in list
           Is entry at position N lower than entry at position LOWEST?
              If so, LOWEST=N
        Next N
        Is ITEM different from LOWEST
           If so, swap entry at LOWEST with entry in ITEM
     Next ITEM
  End DELAYEDSORT

延迟替换排序算法易于理解且易于编码。它通常比冒泡排序更快（交换次数更少），但仍然具有糟糕的时间复杂度 O(n^2)，因此不适合对非常大的数据集进行排序。

如果您真的想将项目添加到已排序的集合中，则可以将新项目添加到集合的末尾，并使用上述方法对其进行处理。如果您正在处理大于几百或几千个元素的数据集，那么效率会很差。

仍然具有 O(n^2) 时间复杂度但可以适应组合添加和排序的替代解决方案是“插入排序”，其伪代码如下所示：

// The values in A[i] are checked in-order, starting at the second one
for i ← 1 to i ← length(A)
  {
    // at the start of the iteration, A[0..i-1] are in sorted order
    // this iteration will insert A[i] into that sorted order
    // save A[i], the value that will be inserted into the array on this iteration
    valueToInsert ← A[i]
    // now mark position i as the hole; A[i]=A[holePos] is now empty
    holePos ← i
    // keep moving the hole down until the valueToInsert is larger than 
    // what's just below the hole or the hole has reached the beginning of the array
    while holePos > 0 and valueToInsert < A[holePos - 1]
      { //value to insert doesn't belong where the hole currently is, so shift 
        A[holePos] ← A[holePos - 1] //shift the larger value up
        holePos ← holePos - 1       //move the hole position down
      }
    // hole is in the right position, so put valueToInsert into the hole
    A[holePos] ← valueToInsert
    // A[0..i] are now in sorted order
  }
于 2013-10-01T13:04:33.520 回答