Skip to content

2021年 408 数据结构 第 42 题

数据结构2021年综合题5分

题目 ​

已知某排序算法如下:

c
void cmpCountSort(int a[], int b[], int n) {
    int i, j, *count;
    count = (int *)malloc(sizeof(int) * n);   // C++ 语言:count = new int[n];
    for (i = 0; i < n; i++) count[i] = 0;
    for (i = 0; i < n - 1; i++)
        for (j = i + 1; j < n; j++)
            if (a[i] < a[j]) count[j]++;
            else            count[i]++;
    for (i = 0; i < n; i++) b[count[i]] = a[i];
    free(count);   // C++ 语言:delete count;
}

请回答下列问题:

(1) 若有 int a[] = {25, -10, 25, 10, 11, 19}, b[6];,则调用 cmpCountSort(a, b, 6) 后数组 b 中的内容是什么?

(2) 若 a 中含有 n 个元素,则算法执行过程中,元素之间的比较次数是多少?

(3) 该算法是稳定的吗?若是,则阐述理由;否则,修改为稳定排序算法。

最后更新:

⚠️ 这道题暂未配可视化,欢迎在 CodeBrick 反馈区告诉我们你想看哪道题