按字母顺序和字符长度快速排序

Question

按字母顺序和字符长度快速排序

5

我正在编写一个程序，用于读取一个相当大的文本文件，并按字母顺序和字符长度对文本文件进行排序。我使用了快速排序算法来实现这一功能。我现在遇到的问题是，我有两种快速排序方法。其中一种是 quickSortLen，这里是代码：

void SortingCompetition::quickSortLen(vector<char*>& words,   int left,   int right){
  int i, j, middle, underMiddle, overMiddle;
  char* pivot;

  //Median of FIVE pivot point
  i = left;
  j = right;
  middle = left + (right - left) / 2;
  underMiddle = left + (middle - left) / 2;
  overMiddle = middle + (right - middle) / 2;

  //Right and Left
  if(strlen(words[right]) < strlen(words[left]))
  {
      swap(words[right], words[left]);

  }

  // 4/5 and left
  if(strlen(words[overMiddle]) < strlen(words[left]))
  {
      swap(words[overMiddle], words[left]);

  }

  //Middle and Left
  if(strlen(words[middle]) < strlen(words[left]))
  {
      swap(words[middle], words[left]);

  }

  // 2/5 and Middle
  if(strlen(words[underMiddle]) < strlen(words[left]))
  {
      swap(words[underMiddle], words[left]);

  }

  //right and 4/5
  if(strlen(words[right]) < strlen(words[underMiddle]))
  {
      swap(words[right], words[underMiddle]);

  }

  //Right and Middle
  if(strlen(words[overMiddle]) < strlen(words[underMiddle]))
  {
      swap(words[overMiddle], words[underMiddle]);

  }

  //Middle and UnderMiddle
  if(strlen(words[middle]) < strlen(words[underMiddle]))
  {
      swap(words[middle], words[underMiddle]);

  }

  //Right and Middle
  if(strlen(words[right]) < strlen(words[middle]))
  {
      swap(words[right], words[middle]);

  }

  //OverMiddle and Middle
  if(strlen(words[overMiddle]) < strlen(words[middle]))
  {
      swap(words[overMiddle], words[middle]);

  }

  //Right and OverMiddle
  if(strlen(words[right]) < strlen(words[overMiddle]))
  {
      swap(words[right], words[overMiddle]);

  }

  //PIVOT POINT ESTABLISHED
  pivot = words[middle];

  //Partition
  while (i <= j)
  {
        //Check from start
        while (strlen(words[i]) < strlen(pivot))
        {
              ++i;
        }

        //Check from end
        while (strlen(words[j])  > strlen(pivot))
        {
              --j;
        }

        //Switch
        if(i <= j)
        {
            swap(words[i], words[j]);
            ++i;
            --j;
        }

  }


  //Recursion
  if (left < j)
  {
      quickSortLen(words, left, j);
  }

  if(i < right)
  {
      quickSortLen(words, i, right);
  }

}

接下来是快速排序代码：

void SortingCompetition::quickSortAlph(vector<char*>& words, int left, int right){
int i, j, middle, underMiddle, overMiddle;
char* pivot;
int x = 1;
//Median of FIVE pivot point
i = left;
j = right;
middle = left + (right - left) / 2;
underMiddle = left + (middle - left) / 2;
overMiddle = middle + (right - middle) / 2;

//Right and Left
if(strcmp(words[right], words[left]) < 0)
{
    swap(words[right], words[left]);

}

// 4/5 and left
if(strcmp(words[overMiddle], words[left]) < 0)
{
    swap(words[overMiddle], words[left]);

}

//Middle and Left
if(strcmp(words[middle], words[left]) < 0)
{
    swap(words[middle], words[left]);

}

// 2/5 and Middle
if(strcmp(words[underMiddle], words[left]) < 0)
{
    swap(words[underMiddle], words[left]);

}

//right and 4/5
if(strcmp(words[right], words[underMiddle]) < 0)
{
    swap(words[right], words[underMiddle]);

}

//Right and Middle
if(strcmp(words[overMiddle], words[underMiddle]) < 0)
{
    swap(words[overMiddle], words[underMiddle]);

}

//Middle and UnderMiddle
if(strcmp(words[middle], words[underMiddle]) < 0)
{
    swap(words[middle], words[underMiddle]);

}

//Right and Middle
if(strcmp(words[right], words[middle]) < 0)
{
    swap(words[right], words[middle]);

}

//OverMiddle and Middle
if(strcmp(words[overMiddle], words[middle]) < 0)
{
    swap(words[overMiddle], words[middle]);

}

//Right and OverMiddle
if(strcmp(words[right], words[overMiddle]) <  0)
{
    swap(words[right], words[overMiddle]);

}

//PIVOT POINT ESTABLISHED
pivot = words[middle];

//Partition
while (i <= j)
{
      //if((strcmp(words[i], pivot) < 0) && (strcmp(words[j], pivot) < 0)
      //Check from start
      while (strcmp(words[i], pivot) < 0)
      {
            ++i;
      }

      //Check from end
      while (strcmp(words[j], pivot) > 0)
      {
            --j;
      }

      //Switch
      if((i <= j))
      {
          swap(words[i], words[j]);
          ++i;
          --j;
      }else{
          i++;
          j--;
      }

}


//Recursion
if (left < j)
{
    quickSortAlph(words, left, j);
}

if(i < right)
{
    quickSortAlph(words, i, right);
}
}

两者都正常工作，但我在合并它们时遇到了问题，因为像August这样的单词的ASCII值比Bravo要小，但Bravo的长度却小于August。有没有建议如何将两者结合起来？

- Nathaniel OToole

我假设这里使用了典型的字典组织方式，即仅在较短单词的所有字符与较长单词相同的情况下按长度排序。如果是这样的话，那么如何创建一个仅包含需要按长度排序的单词的新向量，并将该向量传递到 quickSortLen 中。例如，不要将整个字典传递到 quickSortLen 中，而是只传递一个包含 "abs"、"absolute" 和 "absolutely" 的向量。 - bpgeck

函数指针。 - Rostislav

@bpgeck：标准字符串比较程序会处理这个问题。它绝对不可能认为 abs 大于或等于 absolute。 - Jongware

1

那么，“august”和“bravo”应该如何进行比较呢？你有两个完全不兼容的截然不同的要求。 - Jongware

在vector<char*>中，bravo应该在august之前。它应该按长度字母顺序排序。 - Nathaniel OToole

@NathanielOToole - 所以标题应该是按长度和字母顺序排序？如果对指向单词的指针数组进行排序，并且允许使用第二个临时指针数组进行归并排序，则归并排序可能更快，因为它执行更多的移动（指针）但比较（单词）较少。 - rcgldr

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- NathanOliver · Accepted Answer

你真的需要自己编写快速排序算法吗？如果不需要，你可以使用std::sort和一个functor自定义比较。

struct string_cmp
{
    bool operator()(const std::string& lhs, const std::string& rhs)
    {
        if (lhs.size() == rhs.size())
            return lhs < rhs;
        else
            return lhs.size() < rhs.size();
    }
};

// and then we call sort on the container 
std::sort(container_name.begin(), container_name.end(), string_cmp());