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

Question

我目前正在编写一个程序，该程序读取一个非常大的文本文件并按字母顺序和字符长度对文本文件进行排序。我实现了一个快速排序来做到这一点。我遇到的问题，希望能弄清楚，我有两种快速排序方法。其中一个是 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);
  }

}

比我有 quickSortAlph 这里是代码

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 的长度小于八月。关于如何将两者结合起来有什么建议吗？

Answer 1

您真的需要自己编写快速排序吗？如果你不这样做，你可以使用 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());