PAT甲级专题复习1：排序专题总结

排序题目主要有以下两种考察形式

1. 手撕经典排序算法

判断时什么排序， 运用排序算法进行下一轮排序

直接插入排序（insertion sort）

• 特点：前n个有序，后半部分与原序列相同

• 代码（用sort函数模拟）

  void insert() {
    for (int i = 1; i <= len; i++) {
        sort(a, a + i);
    }
  }
  

希尔排序（shell sort）

• 模拟每一轮去判断

• 代码

  void shell() {
    for (int d = len / 2; d >= 1; d /= 2) { // d为步长 
        for (int i = d; i < len; i++) {
            if (a[i] < a[i - d]) {
                int num = a[i];
                int j;
                for (j = i - d; j >= 0 && a[j] > num; j -= d) {
                    a[j + d] = a[j];
                }
                a[j + d] = num;
            }
        }
    }
  }
  

简单选择排序（select sort）

• 代码

void select() {
    for (int i = 0; i < len - 1; i++) {
        int k = i;
        for (int j = i; j < len; j++) {
            if (a[j] < a[k]) {
                k = j;
            }
        }
        swap(a[k], a[i]);
    }
}

堆排序

• 数组从0开始编号和从1开始编号会影响代码，此处为从1开始编号：堆中，父节点为i， 左儿子为2 * i+1, 右儿子为2* i+2；堆的最后一个节点编号为len - 1, 最后一个节点的父节点为len/2 - 1;
• 代码

void maxheap(int l, int r) {
    int father = l;
    int son = 2 * l + 1;
    while (son <= r) {
        if (son + 1 <= r && a[son] < a[son + 1]) son++;
        if (a[father] > a[son]) return;
        else {
            swap(a[son], a[father]);
            father = son;
            son = father * 2 + 1; 
        }
    }
}

void heapsort() {
    for (int i = len / 2 - 1; i >= 0; i--) maxheap(i, len - 1);
    for (int i = len - 1; i > 0; i--) {
        swap(a[i], a[0]);
        maxheap(0, i - 1);
    }
}

快速排序

• 代码

int partition(int l, int r) {
    int k = a[l];
    while (l < r) {
        while (l < r && a[r] >= k) r--;
        a[l] = a[r];
        while (l < r && a[l] <= k) l++;
        a[r] = a[l];
    }
    a[l] = k;
    return l;
}

void quicksort(int l, int r) {
    if (l < r) {
        int pivot = partition(l, r);
        cout<<endl;
        quicksort(l, pivot - 1);
        quicksort(pivot + 1, r);
    }
}

归并排序

• 代码： 用sort模拟

void mergesort() {
    for (int i = 2; i <= len;) {
        for (int j = 0; j < len; j += i) {
            int t = min(j + i, len);
            sort(a + j, a + t);
        }
        if (i < len) i = min(2 * i, len);
        else break;
    }
}

2. 结构体排序

结构体数组，结构体向量排序

对sort的使用

该考点比较简单，是题目的考察点之一， 但往往不是解题的难点和关键点