使用Quicksort C++排序数组

我正在研究项目（对于学校），其中一个要求是对数组进行排序。所以我决定使用quicksort。（我选择它是因为它是一种我现在不知道的算法）我设法了解它是如何工作的，并且我还找到了一个在C++中实现的选项。使用Quicksort C++排序数组

void quicksort(size_t v[], size_t start_pos, size_t end_pos) 
{ 
    size_t i, j, di, dj; 
    if (start_pos < end_pos) 
    { 
     i = start_pos, j = end_pos; 
     di = 0, dj = 1; 
     do 
     { 
      while (i < j && (v[j] > v[i] || v[j] == v[i])) i += di, j -= dj; 
      if (i < j) 
       std::swap(v[i], v[j]), di = (di + 1) % 2, dj = (dj + 1) % 2; 
     } while (i < j); 
     if (i - start_pos > 1) 
      sort(v, start_pos, i - 1); 
     if (end_pos - i > 1) 
      sort(v, i + 1, end_pos); 
    } 
}

我不明白的是......为什么在最后2条if语句中使用“> 1”？我希望有人能为我澄清这一点。谢谢！ :)

来源

2015-06-24 alfa_peste

因此，你被要求为你的项目编写一个排序函数，而不是实际写一个函数，你只是随机找到一个在线，现在你想让我们向你解释它是如何工作的？那是不是总结了一下？ – CoryKramer

你应该了解它是如何工作的，而不是通过代码，而是通过研究算法规范。否则，你的问题不是关于算法，而是关于你在某处找到的代码。 –

已有[函数]（http://en.cppreference.com/w/cpp/algorithm/sort）[排序]（http://en.cppreference.com/w/cpp/algorithm/qsort）数组。 –

两种计算都分别提供了左右细分的大小。

如果大小为1或零，则该零件已经排序并且不需要任何进一步处理。

if (i - start_pos > 1) 
     sort(v, start_pos, i - 1);

仅当范围是两个或更多个元素时才进行排序调用。正如Barry指出的，这可能应该是

if (i - start_pos > 1) 
     quicksort(v, start_pos, i - 1);

胜利者的评论也是重点。

来源

2015-06-24 11:28:09

如果仔细看看，代码的上半部分确实排列了与在i处索引的枢轴元素相对应的数组，并且如果对剩余部分进行排序，即排列在枢轴元素的右侧和左侧，但在如果您的枢轴索引已经到达end_pos，您不需要将元素排序到枢轴元素的右侧，因此存在if条件，无论我是否end_pos。

来源

2015-06-24 11:35:15

使用Quicksort C++排序数组

回答

相关问题