C++ - 仅使用无符号整数实现快速排序？

Question

我有

std::vector<unsigned int> numbers;

其中充满了数字，需要在不使用 int 索引的情况下进行快速排序 - 只允许将 unsigned int 作为 vector 索引。

当我将所有“int”转换为“unsigned int”时，我见过的所有快速排序示例都会中断 因为索引在某些情况下可能为 -1(由于 j--)。

编辑:这是一个例子

void quickSort(std::vector<unsigned int> &numbers, unsigned int left, unsigned int right) {
        unsigned int i = left, j = right;
        unsigned int tmp;
        unsigned int pivot = numbers.size()/2;

        /* partition */
        while (i <= j) {
              while (numbers[i] < pivot)
                    i++;
              while (numbers[j] > pivot)
                    j--;
              if (i <= j) {
                    tmp = numbers[i];
                    numbers[i] = numbers[j];
                    numbers[j] = tmp;
                    i++;
                    j--;
              }
        };

        /* recursion */
        if (left < j)
              quickSort(numbers, left, j);
        if (i < right)
              quickSort(numbers, i, right);
  }

修改版本:http://diogopinho.hubpages.com/hub/easy-quicksort-with-examples

上述段错误的示例是因为如果 j 是无符号整数并变为 0，则 j-- 变为一个巨大的数字 (0xffffffff) 并且 (i<=j) 始终为真。 有谁知道如何仅使用 unsigned int 索引实现快速排序？

Answer 1

如果您查看链接到的包含数据透视表描述的页面，它会被错误地实现。这可能导致找不到主元并且 j 变得小于 0。如果主元被正确选择为包含在范围内的数字，我认为该算法也适用于无符号整数。