时间戳

首页 > 解决方案 > c++排序和快速排序算法和for循环问题

c++ - c++排序和快速排序算法和for循环问题

问题描述

请你能帮我从一本书中理解下面的代码吗？

我想知道为什么“ swap(words, start, current); ”不是下面代码中for循环的一部分？

“for 循环 - 检查单词与所选单词”的最终效果应该是将所有小于所选单词的单词放置在所有大于或等于它的单词之前。

但是，在每次 I++ 迭代后不交换“开始”和“当前”，我不明白比较是如何完成的，因为 IF 语句中的“*words[i]”将始终与“*words[start ]" 总是等于 index = 0 （条件在循环中迭代，这意味着总是针对 0 索引进行比较）

// 引用 "*words[i] < *words[start]")

Ps 我最初的假设是交换行“swap(words, start, current);” 应该是 for 循环的一部分，如下所示，它不是循环的一部分，而是在 for 循环之外。

void sort(Words& words, size_t start, size_t end)
{
  // start index must be less than end index for 2 or more elements

  if (!(start < end))
    return;

  // Choose middle address to partition set

  swap(words, start, (start + end) / 2);

// Check words against chosen word

size_t current {start};
for (size_t i {start + 1}; i <= end; i++) 
  {
    if (*words[i] < *words[start])
      swap(words, ++current, i);
  }
  swap(words, start, current);

  if (current > start) sort(words, start, current - 1);
  if (end > current + 1) sort(words, current + 1, end);
}

下面还添加了为交换函数定义的代码（如果您认为它是相关的）

#include <iostream>
#include <iomanip>
#include <memory>
#include <string>
#include <string_view>
#include <vector>

using Words = std::vector<std::shared_ptr<std::string>>;
void swap(Words& words, size_t first, size_t second);
void sort(Words& words);
void sort(Words& words, size_t start, size_t end);
void extract_words(Words& words, std::string_view text, std::string_view separators); void show_words(const Words& words);
size_t max_word_length(const Words& words);

int main() 
{
  Words words;
  std::string text;       
  const auto separators{" ,.!?\"\n"}; 

std::cout << "Enter a string terminated by *:" << std::endl;    getline(std::cin, text, '*');

extract_words(words, text, separators); 
if (words.empty())
 {
std::cout << "No words in text." << std::endl;
return 0;
 }
sort(words);
show_words(words);
}

void extract_words(Words& words, std::string_view text, std::string_view separators) 
{
size_t start {text.find_first_not_of(separators)};
size_t end {};

while (start != std::string_view::npos) 
 {
 end = text.find_first_of(separators, start + 1); 
 if (end ==    std::string_view::npos)
 end = text.length();
words.push_back(std::make_shared<std::string>(text.substr(start, end - start)));
 }
}


void swap(Words& words, size_t first, size_t second)
{
  auto temp{words[first]};
  words[first] = words[second];
  words[second] = temp; 
}

This just swaps the addresses in words at indexes first and second.

标签： c++

解决方案

发生的事情是数组的中间值被选为枢轴值，并将“不碍事”移动到数组的开头：

swap(words, start, (start + end) / 2);

然后循环处理从start+1到end包含的所有值，以便一旦完成，从start到current包含的所有值都小于枢轴值。注意循环是从start+1所以我们永远不会改变枢轴值。

size_t current {start};
for (size_t i {start + 1}; i <= end; i++) 
  {
    if (*words[i] < *words[start])
      swap(words, ++current, i);
  }

但是，在这一点上，支点在错误的位置。为了使递归调用起作用，值words[current]必须包含枢轴值。所以它需要从我们放置它的地方交换 ( words[start]) 到current

swap(words, start, current);

考虑一下如果您对一个简单的小数组进行排序会发生什么可能会很有用

[3,2,1]

您选择中间值并将其移至开头...

[2,3,1]

您移动的所有值都小于枢轴...

[2,1,3]
   ^
   |
current

您将枢轴移回原位

[1,2,3]

您对当前 [1] 之前和当前 [3] 之后的部分进行排序，这不涉及任何更改，因为它们是单个元素。

请注意，如果您没有将枢轴移动到正确的位置，则对子数组进行排序不会产生正确的答案。

推荐阅读