以最后元素为基准的快速排序无法正常排序问题排查

需求背景 #

需要实现以最后一个元素为基准的快速排序，partition()函数中找到大于等于基准的元素n时，执行环形交换：先将n与基准前一个元素交换，再将基准前一个元素与基准交换。

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

但当前代码无法正确排序，以下是实现代码：

实现代码 #

partition函数 #

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;
}

quicksort函数 #

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);
}
}

main函数 #

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]);
}
}

问题点分析 #

1. partition函数核心逻辑偏离需求

   • 需求明确以最后一个元素为基准，但当前代码的双层循环没有固定基准，而是不断将i位置的元素作为比较对象，完全不符合快速排序partition的核心逻辑——将小于基准的元素放到左侧，大于等于的放到右侧。
   • 环形交换的触发条件错误：要求是找到大于等于基准的元素时执行交换，但代码中是和arr[i]（而非固定的基准元素）比较，逻辑完全错位。
   • 基准位置返回值混乱：right-left>1分支返回的pivot_position并不是基准元素最终的正确位置，导致后续递归的区间划分完全错误。

2. quicksort函数递归终止条件错误

   • 用pivot != 0作为递归判断条件完全不合理，当基准位置恰好为0时，会错误终止递归。正确的终止条件应该是当left >= right（区间内只有一个或没有元素）。

3. main函数存在语法与输出错误

   • for(int i = 0; i < 9, i++)中的逗号是语法错误，应改为分号;。
   • printf(arr[i])缺少格式符，无法正确输出数值，应改为printf("%d ", arr[i]);。
   • 未释放malloc分配的内存，存在内存泄漏；且main函数标准返回值应为int而非void。

修复建议 #

修正partition函数（符合需求逻辑） #

int partition(uint8_t *arr, int left, int right) {
    uint8_t pivot = arr[right]; // 固定基准为最后一个元素
    int pivot_pos = right;

    // 遍历基准左侧的所有元素
    for (int j = left; j < pivot_pos; j++) {
        if (arr[j] >= pivot) {
            // 执行要求的环形交换
            uint8_t tmp = arr[j];
            arr[j] = arr[pivot_pos - 1];
            arr[pivot_pos - 1] = arr[pivot_pos];
            arr[pivot_pos] = tmp;
            pivot_pos--; // 基准位置左移一位
            j--; // 交换后当前位置需重新检查新元素
        }
    }

    return pivot_pos;
}

修正quicksort函数（正确递归逻辑） #

void quicksort(uint8_t *arr, int left, int right) {
    if (left >= right) {
        return; // 区间无有效元素，终止递归
    }
    int pivot = partition(arr, left, right);
    quicksort(arr, left, pivot - 1);
    quicksort(arr, pivot + 1, right);
}

修正main函数（语法与输出修复） #

#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>

int main() {
    uint8_t *arr = malloc(sizeof(uint8_t) * 9);
    if (!arr) {
        printf("内存分配失败\n");
        return 1;
    }

    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;

    printf("原数组：");
    for (int i = 0; i < 9; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    quicksort(arr, 0, 8);

    printf("排序后数组：");
    for (int i = 0; i < 9; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    free(arr);
    return 0;
}

内容的提问来源于stack exchange，提问作者Apollox