数据结构第九章作业

第一题

全国有10000人参加物理竞赛，只录取成绩优异的前10名，不需排出名次。问此种情况下，用何种排序方法速度最快？为什么？

解：

使用基于快速排序思想的kth_element算法，递归求解前k大的数。时间复杂度\(O(n)\)。

由于分数的值域有限，也可使用基数排序，时间复杂度同样也是\(O(n)\)，但需要额外的空间开销。

第二题

若待排序列用结带头点的单链表存储，试给出简单选择排序算法。

解：

typedef struct node {
    int key;
    InfoType otherinfo;
    struct node *next;  
} node, *pointer;

void selectsort(pointer h) { // h 为头指针
    if (h == NULL || h->next == NULL) return;
    pointer sorted_head = NULL;
    while (h->next != NULL) {
        pointer pre_max = NULL;
        pointer max = h->next;
        pointer pre = h;
        pointer p = h->next;
        while (p != NULL) {
            if (p->key > max->key) {
                pre_max = pre;
                max = p;
            }
            pre = p;
            p = p->next;
        }
        if (pre_max == NULL) { // max 为 h->next
            h->next = max->next;
        } else {
            pre_max->next = max->next;
        }
        max->next = sorted_head;
        sorted_head = max;
    }
    h->next = sorted_head;
}

第三题

请编写出算法，借助于快速排序的算法思想，在一组无序的记录中查找给定关键字值等于k的记录是记录序列中第几大的数。设此组记录存于数组r[low..high]中，若查找成功，则返回该记录是r数组中第几大的数，否则返回0。 int Index (ElemType r[], int low, int high, int k)

解：

选定枢轴之后分区，比较枢轴上的健与k的大小，然后分治求解。

int Partition(ElemType a[], int low, int high) {
    ElemType pivot = a[low];
    while (low < high) {
        while (low < high && pivot.key <= a[high].key) --high;
        a[low] = a[high];
        while (low < high && pivot.key >= a[low].key) ++low;
        a[high] = a[low];
    }
    a[low] = pivot;
    return low;
}

int Index(ElemType r[], int low, int high, int k) {
    if (low > high) return 0;
    int i = Partition(r, low, high);
    if (r[i].key == k) {
        return i - low + 1;
    } else if (r[i].key < k) {
        int tmp = Index(r, i + 1, high, k); 
        if (tmp == 0) return 0; // 确保能找到再计算答案
        else return i - low + 1 + tmp;
    } else{
        return Index(r, low, i - 1, k);
    }
}

第四题

以关键码序列(503, 087, 512, 061, 908, 170, 897, 275, 653, 426)为例，手工执行以下排序算法，写出每一趟排序结束时的关键码状态： (1) 直接插入排序 (2) 希尔排序(d[1]=5, d[2]=3, d[3]=1) (3) 快速排序(第一个记录为基准记录) (4) 堆排序 (5) 归并排序 (6) 基数排序

解：

(1)

503, 087, 512, 061, 908, 170, 897, 275, 653, 426

087, 503, 512, 061, 908, 170, 897, 275, 653, 426

061, 087, 503, 512, 908, 170, 897, 275, 653, 426

061, 087, 170, 503, 512, 908, 897, 275, 653, 426

061, 087, 170, 503, 512, 897, 908, 275, 653, 426

061, 087, 170, 275, 503, 512, 897, 908, 653, 426

061, 087, 170, 275, 503, 512, 653, 897, 908, 426

061, 087, 170, 275, 426, 503, 512, 653, 897, 908

(2)

170, 087, 275, 061, 426, 503, 897, 512, 653, 908 (d=5)

061, 087, 275, 170, 426, 503, 897, 512, 653, 908 (d=3)

061, 087, 170, 275, 426, 503, 512, 653, 897, 908 (d=1)

(3)

087, 061, 170, 275, 426, 503, 512, 908, 897, 653 (pivot = 503)

061, 087, 170, 275, 426, 503, 512, 908, 897, 653 (pivot = 087)

061, 087, 170, 275, 426, 503, 512, 908, 897, 653 (pivot = 061)

061, 087, 170, 275, 426, 503, 512, 908, 897, 653 (pivot = 170)

061, 087, 170, 275, 426, 503, 512, 908, 897, 653 (pivot = 275)

061, 087, 170, 275, 426, 503, 512, 908, 897, 653 (pivot = 512)

061, 087, 170, 275, 426, 503, 512, 897, 653, 908 (pivot = 908)

061, 087, 170, 275, 426, 503, 512, 653, 897, 908 (pivot = 897)

(4)

908,653,897,275,426,170,512,503,061,087（建堆）

897,653,512,275,426,170,087,503,061,908

653,426,512,275,061,170,087,503,897,908

426,275,170,087,061,503,512,653,897,908

503,275,170,087,061,426,512,653,897,908

275,087,170,061,503,426,512,653,897,908

170,087,061,275,503,426,512,653,897,908

087,061,170,275,503,426,512,653,897,908

061,087,170,275,503,426,512,653,897,908

(5)

087,503, 061,512, 170,908, 275,897, 426,653

061,087,503,512, 170,275,897,908, 426,653

061,087,170,275, 503,512,897,908, 426,653

061,087,170,275,426,503,512,653,897,908

(6)

170,061,512,503,653,275,426,087,897,908 （个位）

503,908,512,426,653,061,170,275,087,897 （十位）

061,087,170,275,426,503,512,653,897,908 （百位）