以最后一个元素为基准的快速排序不排序

Question

我有一个任务是创建一个快速排序算法，该算法选择最后一个元素作为主元元素。在partition()函数内部，当发现一个大于或等于主元的元素n时，该函数应该执行“环交换”。它应该将 n 与pivot-1 交换，然后将pivot-1 与pivot 交换。

所以我写了这个程序：

int partition(uint8_t *arr, int left, int right){
int pivot_position = right;
if (right-left >1)
{
    for (int i = right; i >= left; i--)
    {
        for (int j = left; j < i; j++)
        {
            if (arr[j] >= arr[i])
            {
                pivot_position = i;
                int tmp = arr[j];
                arr[j] = arr[i-1];
                arr[i-1] = arr[i];
                arr[i] = tmp;
                break;
            }
        }
    }
}else{
    if (right-left == 1 && arr[left] > arr[right])
    {
        int tmp = arr[left];
        arr[left] = arr[right];
        arr[right] = tmp;
    }
    return 0;
}

return pivot_position;

}

void quicksort( uint8_t *arr, int left, int right){
int pivot = partition(arr, left, right);

if (pivot != 0)
{
    quicksort( arr, left, pivot-1);
    quicksort( arr, pivot+1, right);
}

}

如果给定数组：[160, 32, 96, 128, 224, 64, 192, 0, 255] 预期输出：[0, 32 , 64 ,96, 128, 160, 192, 224, 256]

我做错了什么？

编辑： 按要求：

void main() {
uint8_t *arr = malloc(sizeof(uint8_t)*9);

arr[0] = 160;
arr[1] = 32;
arr[2] = 96;
arr[3] = 128;
arr[4] = 224;
arr[5] = 64;
arr[6] = 192;
arr[7] = 0;
arr[8] = 255;

for(int i = 0; i < 9, i++){
    printf(arr[i]);
}
quicksort(arr, 0, 8);

for(int i = 0; i < 9; i++){
    printf(arr[i]);
}
}

抱歉，如果这不起作用，无法测试它，我目前不在我的机器前面。

Answer 1

主要问题是您并不总是与枢轴值进行比较。您的代码假设它位于

i

，但一旦

j

循环找不到任何可交换的内容，情况就不会如此。在这种情况下，你的外循环仍然会减少

i

，此时它不再指向枢轴。

此外，当您更新

pivot_position

时，您应该考虑到您即将 move 该枢轴到索引

i-1

，因此它应该采用 that 值。

如果我们只想修复必要的最小值，您可以更改此：

        if (arr[j] >= arr[i])
        {
            pivot_position = i;

这样：

        if (arr[j] >= arr[pivot_position])
        {
            pivot_position = i-1;

但是双循环效率很低。内循环从

left

开始一遍又一遍。这是不需要的。您只需将值与主元进行一次比较。此外，当只有两个值要分区时，您实际上不需要特殊情况（

else

块）。

这是我的写法——使用 3 周期约束：

int partition(uint8_t *arr, int left, int right) {
    // right will be the pivot index
    while (left < right) {
        if (arr[left] >= arr[right]) {
            int tmp = arr[left];
            arr[left] = arr[right-1];
            arr[right-1] = arr[right]; // Pivot value
            arr[right] = tmp; // Current value
            right--; // Adjust pivot index
        } else {
            left++; // The value is in the correct partition, so move on 
        }
    }
    return right; // Return pivot index
}