如何修改快速排序的partition函数实现特定数组排序需求？

我已实现如下快速排序算法：

static void quicksort(int elements[], int start, int end){
        if (start<end){
            int index=partition(elements,start,end);
            quicksort(elements,start,index-1);
            quicksort(elements,index+1,end);
        }
    }
    static void swap(int elements[],int i, int j){
        int temp=elements[i];
        elements[i]=elements[j];
        elements[j]=temp;
    }
    static int partition(int elements[],int start, int end){
        int index;
        int pivot=elements[end];
        int minIndex=start-1;
        for (int i=start;i<end;i++){
            if (elements[i]<pivot){
                minIndex++;
                swap(elements,minIndex,i);
            }
        }
       
        index=minIndex+1;
        swap(elements,index,end);
        return index;
}

我希望修改该算法（我认为需修改partition部分），使得输入数组如[4,0,7,0,5,0,1]时，输出结果为[1,4,5,7,0,0,0]。我想到的一种方案是遍历数组生成两个子数组，一个存非零元素，另一个存零，对非零子数组快速排序后拼接。请问能否仅通过修改partition函数实现该需求？

完全可以仅通过修改partition函数实现这个需求。核心思路是调整分区逻辑，让所有非零元素被优先放在数组左侧，零元素集中在右侧，同时在非零元素内部维持快速排序的正常比较逻辑。

修改后的partition函数实现如下：

static int partition(int elements[], int start, int end) {
    int pivot = elements[end];
    // 标记非零元素的右边界，初始在分区起始位置的左侧
    int nonZeroBoundary = start - 1;

    for (int i = start; i < end; i++) {
        boolean shouldSwap = false;
        if (elements[i] != 0 && pivot != 0) {
            // 两个都是非零元素，按原快速排序规则比较
            shouldSwap = elements[i] < pivot;
        } else if (elements[i] != 0 && pivot == 0) {
            // 当前元素非零、pivot是零，非零元素必须放在零的左侧
            shouldSwap = true;
        }
        // 其余情况（当前元素是零）：不管pivot是否为零，都留在右侧，不交换

        if (shouldSwap) {
            nonZeroBoundary++;
            swap(elements, nonZeroBoundary, i);
        }
    }

    // 将pivot放到正确的位置：非零区域末尾或零区域开头
    int pivotPos = nonZeroBoundary + 1;
    swap(elements, pivotPos, end);
    return pivotPos;
}

逻辑说明 #

1. 分区优先级调整：
   • 当pivot是非零时，非零元素之间按原规则排序（小于pivot的移到左侧），零元素自动留在右侧。
   • 当pivot是零时，所有非零元素都会被移到左侧，零元素集中在右侧。
2. 递归效果：
   • 左侧的非零子数组会被递归排序，最终得到有序的非零序列。
   • 右侧的零子数组因为start >= end会直接终止递归，不需要额外处理，自然保持在数组末尾。

这样修改后，输入[4,0,7,0,5,0,1]会直接输出[1,4,5,7,0,0,0]，完全符合需求，无需拆分数组拼接。

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