9、已知关键字序列（12，33，15，18，43，22，55，78，6，10）。 （1）取增量序列d=（5，3，1），写出希尔排序的每趟序列； （2）给出初始堆为大根堆的序列（3分）

(1) 希尔排序的每趟序列如下：

第一趟（增量为5）：[12, 22, 6], [33, 55, 10], [15, 78], [18], [43]

第二趟（增量为3）：[6, 10, 12, 18, 43], [15, 22, 55, 78], [33]

第三趟（增量为1）：[6, 10, 12, 15, 18, 22, 33, 43, 55, 78]

(2) 初始堆为大根堆的序列如下：

[78, 43, 55, 18, 33, 22, 15, 12, 6, 10]

相关问题

已知关键字序列{49，27 1 35 16 57 55, 9}，使用冒泡排序进行升序排序，请写出每一趟排序结果。 1

好的，以下是使用冒泡排序对给定关键字序列进行升序排序的过程，其中使用了C语言实现：

#include <stdio.h>

void BubbleSort(int A[], int n) {
    int i, j, temp;
    for (i = 0; i < n-1; i++) { // 外层循环控制排序趟数
        for (j = 0; j < n-i-1; j++) { // 内层循环控制每趟排序中的比较次数
            if (A[j] > A[j+1]) { // 如果前一个元素大于后一个元素，则交换它们
                temp = A[j];
                A[j] = A[j+1];
                A[j+1] = temp;
            }
        }
        printf("第%d趟排序结果：", i+1);
        for (j = 0; j < n; j++) { // 输出每趟排序后的结果
            printf("%d ", A[j]);
        }
        printf("\n");
    }
}

int main() {
    int A[8] = {49, 27, 1, 35, 16, 57, 55, 9}; // 给定关键字序列
    BubbleSort(A, 8); // 对关键字序列进行冒泡排序
    return 0;
}

输出结果为：

第1趟排序结果：27 1 35 16 49 55 9 57 
第2趟排序结果：1 27 16 35 49 9 55 57 
第3趟排序结果：1 16 27 35 9 49 55 57 
第4趟排序结果：1 16 27 9 35 49 55 57 
第5趟排序结果：1 16 9 27 35 49 55 57 
第6趟排序结果：1 9 16 27 35 49 55 57 
第7趟排序结果：1 9 16 27 35 49 55 57 

其中，BubbleSort函数实现冒泡排序算法，对给定的关键字序列进行升序排序。主函数中给定关键字序列{49，27 1 35 16 57 55, 9}，调用BubbleSort函数进行排序，并输出每一趟排序后的结果。

已知关键字序列{98，82，105，71，36，77，24，82’,12,55}分别写出直接插入排序、希尔排序、冒泡排序、快速排序、直接选择排序、堆排序的各趟运行结果

直接插入排序：

第1趟：98

第2趟：82，98

第3趟：82，98，105

第4趟：71，82，98，105

第5趟：36，71，82，98，105

第6趟：36，71，77，82，98，105

第7趟：24，36，71，77，82，98，105

第8趟：24，36，71，77，82，82’，98，105

第9趟：12，24，36，71，77，82，82’，98，105

第10趟：12，24，36，55，71，77，82，82’，98，105

希尔排序：

第1趟：

步长为5：77，82’，55，98，36，71，24，82，12，105

步长为2：55，12，36，24，71，77，82’，98，82，105

步长为1：12，24，36，55，71，77，82’，82，98，105

冒泡排序：

第1趟：82，98，71，105，77，36，82’，55，24，12

第2趟：82，71，98，77，105，36，55，82’，24，12

第3趟：71，82，77，98，36，55，82’，12，24，105

第4趟：71，77，82，36，55，82’，12，24，98，105

第5趟：71，77，36，55，82，12，24，82’，98，105

第6趟：71，36，55，77，12，24，82，82’，98，105

第7趟：36，55，71，12，24，77，82，82’，98，105

第8趟：36，55，12，24，71，77，82，82’，98，105

第9趟：36，12，24，55，71，77，82，82’，98，105

第10趟：12，24，36，55，71，77，82，82’，98，105

快速排序：

第1趟：55，36，12，24，82’，98，82，105，71，77

第2趟：24，12，36，55，71，77，82’，82，98，105

直接选择排序：

第1趟：12，82’，105，77，36，71，24，82，55，98

第2趟：12，24，105，77，36，71，55，82，82’，98

第3趟：12，24，36，77，105，55，71，82，82’，98

第4趟：12，24，36，55，77，105，71，82，82’，98

第5趟：12，24，36，55，71，77，105，82，82’，98

第6趟：12，24，36，55，71，77，82，105，82’，98

第7趟：12，24，36，55，71，77，82，82’，105，98

第8趟：12，24，36，55，71，77，82，82’，98，105

堆排序：

第1趟：98，82’，105，77，82，71，24，55，36，12

第2趟：12，24，36，55，71，77，82，82’，98，105