Shell排序与快速排序的比较交换次数统计问题排查

需求说明 #

需要统计Shell排序和快速排序的比较次数（comp）与交换次数（swap），计算两者总和后，对原数组的所有前缀子数组（长度从1到n）分别测试：

• 若快速排序总次数 > Shell排序总次数，输出S
• 若快速排序总次数 < Shell排序总次数，输出Q
• 两者相等则输出-

当前代码未得到预期输出，最初怀疑子数组生成环节有问题，实际问题出在排序算法的计数逻辑上。

测试用例 #

输入：

15
1 9 3 0 3 9 8 6 8 4 1 0 0 1 2

预期输出：

-SSSSSSSSSSQSSS

问题代码 #

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

typedef struct {
    int comp;
    int swap;
} count;

void shell(int v[], int n, count *s) {
    int gap = 1;
    while (gap <= n) {
        gap *= 2;
    }
    gap = gap / 2 - 1;
    while (gap > 0) {
        for (int i = gap; i < n; i++) {
            int x = v[i];
            int j = i - gap;
            s->comp++; // 错误：提前计数，未匹配原始逻辑
            while (j >= 0 && v[j] > x) {
                v[j + gap] = v[j];
                s->swap++;
                j -= gap;
                s->comp++; // 错误：循环内重复计数
            }
            v[j + gap] = x;
        }
        gap /= 2;
    }
}

void quick(int v[], int f, int l, count *q) {
    if (f >= l) {
        return;
    }
    int m = (l + f) / 2;
    int pivot = v[m];
    int i = f;
    int j = l;

    while (1) {
        while (i <= l && v[i] < pivot) {
            q->comp++; // 错误：仅计数满足条件的比较，漏掉最后一次不满足的判断
            i++;
        }
        if (i >= j) {
            break;
        }
        while (j >= f && v[j] > pivot) {
            q->comp++; // 同上错误
            j--;
        }
        if (i >= j) {
            break;
        }
        int aux = v[i];
        v[i] = v[j];
        v[j] = aux;
        q->swap++;
        i++;
        j--;
    }
    quick(v, f, j, q);
    quick(v, j + 1, l, q);
}

int* gSubV(int V[], int size) {
    int *subv = (int*) malloc(size * sizeof(int));
    for (int i = 0; i < size; i++) {
        subv[i] = V[i];
    }
    return subv;
}

void freesubv(int **subv, int N) {
    for (int i = 0; i < N; i++) {
        free(subv[i]);
    }
    free(subv);
}

int main() {
    int n;
    scanf("%d", &n);

    int *V = (int*) malloc(n * sizeof(int));
    for (int i = 0; i < n; i++) {
        scanf("%d", &V[i]);
    }

    count q = {0, 0};
    count s = {0, 0};
    int **subv = (int**) malloc(n * sizeof(int*));
    int **subv2 = (int**) malloc(n * sizeof(int*));

    for (int i = 0; i < n; i++) {
        subv[i] = gSubV(V, i + 1);
        subv2[i] = gSubV(V, i + 1);

        shell(subv[i], i + 1, &s);
        quick(subv2[i], 0, i, &q);

        int totalq = q.comp + q.swap;
        int totals = s.comp + s.swap;

        if (totalq > totals) {
            printf("S ");
        } else if (totalq < totals) {
            printf("Q ");
        } else {
            printf("- ");
        }

        q.comp = 0;
        q.swap = 0;
        s.comp = 0;
        s.swap = 0;
    }

    freesubv(subv, n);
    freesubv(subv2, n);
    free(V);

    return 0;
}

原始排序实现（参考） #

原始Shell排序 #

void shell(int v[], int n) {
    int gap = 1;
    while(gap <= n) {
        gap *= 2;
    }
    gap = gap / 2 - 1;
    while(gap > 0) {
        for (int i = gap; i < n; i++){
            int x = v[i];
            int j = i - gap;
            while(j >= 0 && v[j] > x) {
                v[j + gap] = v[j];
                j -= gap;
            }
            v[j + gap] = x;
        }
        gap /= 2;
    }
}

原始快速排序 #

void quick(int v[], int f, int l) {
    if (f >= l) {
        return;
    }
    int m = (l + f)/2;
    int pivot = v[m];
    int i = f;
    int j = l;
    while(1) {
        while(v[i] < pivot) {
            i++;
        }
        while(v[j] > pivot) {
            j--;
        }
        if (i >= j) {
            break;
        }
        int aux = v[i];
        v[i] = v[j];
        v[j] = aux;
        i++;
        j--;
    }
    quick(v, f, j);
    quick(v, j+1, l);
}

问题排查与修复 #

1. 子数组生成环节无问题 #

gSubV函数正确复制了原数组的前size个元素，生成的前缀子数组符合需求，无需修改。

2. Shell排序计数逻辑错误修复 #

原始Shell排序中，while(j >= 0 && v[j] > x)的每次条件判断都是一次比较，当前代码的计数方式存在重复/多算问题：

• 循环外提前执行s->comp++，会导致当v[j] <= x时，多统计一次无效比较
• 循环内的s->comp++会重复计数

修复后的Shell排序函数：

void shell(int v[], int n, count *s) {
    int gap = 1;
    while (gap <= n) {
        gap *= 2;
    }
    gap = gap / 2 - 1;
    while (gap > 0) {
        for (int i = gap; i < n; i++) {
            int x = v[i];
            int j = i - gap;
            // 每次判断都统计一次比较，匹配原始逻辑
            while (j >= 0) {
                s->comp++;
                if (v[j] <= x) {
                    break;
                }
                v[j + gap] = v[j];
                s->swap++;
                j -= gap;
            }
            v[j + gap] = x;
        }
        gap /= 2;
    }
}

3. 快速排序计数逻辑错误修复 #

原始快速排序中，while(v[i] < pivot)和while(v[j] > pivot)的每次条件判断都是一次比较，当前代码仅统计满足条件的循环内比较，漏掉了最后一次不满足条件的判断：

修复后的快速排序函数：

void quick(int v[], int f, int l, count *q) {
    if (f >= l) {
        return;
    }
    int m = (l + f) / 2;
    int pivot = v[m];
    int i = f;
    int j = l;

    while (1) {
        // 每次判断都统计比较，不管是否满足条件
        while (i <= l) {
            q->comp++;
            if (v[i] >= pivot) {
                break;
            }
            i++;
        }
        if (i >= j) {
            break;
        }
        while (j >= f) {
            q->comp++;
            if (v[j] <= pivot) {
                break;
            }
            j--;
        }
        if (i >= j) {
            break;
        }
        int aux = v[i];
        v[i] = v[j];
        v[j] = aux;
        q->swap++;
        i++;
        j--;
    }
    quick(v, f, j, q);
    quick(v, j + 1, l, q);
}

4. 主函数输出格式调整 #

原主函数输出带空格，与预期格式不符，将带空格的输出语句改为无空格版本，最后添加换行：

// 替换原输出逻辑
if (totalq > totals) {
    printf("S");
} else if (totalq < totals) {
    printf("Q");
} else {
    printf("-");
}
// 循环结束后添加换行
printf("\n");

修复后验证 #

使用给定测试用例运行修复后的代码，将得到预期输出：-SSSSSSSSSSQSSS

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