时间戳

首页 > 解决方案 > 快速排序的递归代码

c++ - 快速排序的递归代码

问题描述

下面是我正在努力解决的一个函数，它是为基于递归操作的快速排序而定义的：

void quick_sort(QVector<RoiInfo> &roi, int begin, int end)
{
  int     i, j;
  int     pivot;
  RoiInfo work;
  int     half = (begin+end)/2;

  pivot = roi[half].roi.y;
  i = begin;
  j = end;

  //I am confused about the codes below, what kind of sorting it is to do
  while( 1 )
  {
    while( roi[i].roi.y > pivot ){ ++i; }
    while( roi[j].roi.y < pivot ){ --j; }
    if( i >= j ){ break; }


    work = roi[i];
    roi[i] = roi[j];
    roi[j] = work;

    i++;
    j--;
  }

  if( begin < i - 1 ){ quick_sort( roi, begin, i - 1 ); }
  if( j + 1 < end ){ quick_sort( roi, j + 1, end ); }
}

在上面的代码中，RoiInfo是一个用户定义的类，它有一个类型为 public 的成员roi，CvRect它是一个 OpenCV 类，它定义了一个由 指定的矩形(x, y, width, height)。任何人都可以向我解释，最好举个例子，这个quick_sort功能是怎么回事？非常感激！

标签： c++

解决方案

y是按坐标排序吗？！（我无法评论。）仅在y坐标上进行比较，显然它从上到下对矩形进行排序。

下面进行快速排序的分区。

while( roi[i].roi.y > pivot ){ ++i; }
while( roi[j].roi.y < pivot ){ --j; }

如果左侧或右侧仍有元素，我们将递归到较小的子问题。

if( begin < i - 1 ){quick_sort( roi, begin, i - 1 );} //elements to the left
if( j + 1 < end ){quick_sort( roi, j + 1, end );} //elements to the right

推荐阅读