关于算法-数据结构:PAT甲级1098-Insertion-or-Heap-Sort

给定一个待排序序列和排序若干次的序列, 要求判断是失去指标序列是通过插入排序还是堆排序, 而后在输入再排序一次后的序列即可。

这里考查的就是插入排序和堆排序的残缺排序的过程，循序渐进的来就好。

插入排序：

首先将序列划分为有序序列局部和无序序列局部，初始有序序列为序列中第一个元素，对于长度为 N 的序列，插入排序会通过 N - 1 趟排序，实现将 N - 1 个无序序列的元素顺次插入到有序序列之中，那么能够看到，插入排序分为内部循环管制趟数，外部循环负责找到插入地位，每次循环应用 t 暂存待插入元素，而后在 $[1,j]$(有序序列)中查问待插入地位 loc, 只有 $t>=temp[j]$，阐明找到插入地位 $j+1$，退出内层循环，将 $j+1$ 地位的元素赋值为 t 即可。

堆排序：

因为指标序列是递增系列，那么咱们须要建设大根堆，咱们初始序列作为大根堆的层序遍历序列，而后从最初一个非叶子节点到根节点，顺次向下调整，只有孩子节点中有比当期父节点大的，就替换孩子节点和父节点，并且向下顺次递推查问，直到孩子节点的权重均比父节点小进行调整。这样就实现了初始大根堆的建设过程。堆排序就是将根节点和最初一个节点 (未排序节点) 进行替换，而后再向下调整根节点。这样就实现了一次堆排序的过程，每一次堆排序都会固定一个最大的元素在最初。

因为题目要求判断已排序局部的序列是插入排序还是堆排序的后果之上再进行一次排序，那么咱们应用 $same$ 标记已排序的局部序列是否是由以后的排序算法失去的，如果在排序实现后，判断 $same$ 为 $true$，那么就阐明能够退出排序过程，进行相应的输入。如果 $same$ 为 $false$，那么就应用 $isSame$ 函数更新 $same$ 的值。

1、堆排序的根节点下标为 1.
2、插入排序的初始插入地位默认为 1，是为了解决像 3 1 这种非凡状况。
3、初始序列不参加和局部有序序列的比拟，肯定得先排序一次当前再比拟是否雷同。
4、这里题目要求是指标朝着递增序列的方向排序, 也即是最初的后果是从小到大, 这里得留神堆排序是大根堆排序后才是递增序列, 小根堆排序后是递加序列, 因为每次都是从根节点和最初一个结点替换, 最大 (大根堆) 或者最小 (小根堆) 的结点都在前面.

#include <cstdio>
#include <algorithm>

using namespace std;

int N;// 节点个数
int init[105];// 初始序列
int temp[105];// 暂存初始序列
int partial_sorted[105];// 局部排序序列

bool isSame(){for (int i = 1; i <= N; ++i) {if(temp[i]!=partial_sorted[i]){return false;}
    }
    return true;
}

bool InsertionSort(){
    bool same = false;
    // N- 1 轮排序
    for (int i = 1; i < N; ++i) {int t = temp[i+1];// 暂存待插入元素
        int loc = 1;// 待插入地位, 初始为 1，思考 3 1 的非凡状况
        for (int j = i; j >= 1; --j) {if(t<temp[j]){temp[j+1] = temp[j];
            } else {
                // 找到插入地位
                loc = j+1;
                break;
            }
        }
        temp[loc] = t;
        if(same){
            // 在相等的状况下，又排序了一次
            break;
        }
        if(isSame()) same = true;// 曾经雷同了，再排序一次
    }
    return same;
}

// 调整 [low,high] 的节点权重,low 从最初一个非叶节点开始始终到 1，high 为以后堆须要调整的最初一个元素
void downAdjust(int low,int high){
    int i = low;
    int j = 2*i;// i 的左孩子
    while (j<=high){
        // 只有左孩子始终存在, 就向下调整
        if(j+1<=high&&temp[j+1]>temp[j]){
            // 右孩子节点更小
            j = j+1;
        }
        if(temp[j]>temp[i]){
            // 孩子节点的值更小
            swap(temp[j],temp[i]);
            i = j;
            j = 2*i;
        }else {
            // 孩子权重更加小，就进行比拟
            break;
        }
    }
}

void createHeap(){for(int i=N/2;i>=1;--i){downAdjust(i,N);
    }
}

void print(){for(int i=1;i<=N;++i){printf("%d",temp[i]);
        if(i<N) printf(" ");
    }
}

void HeapSort(){createHeap();// 先建堆
    // 将最初的节点和堆顶的节点替换，而后调整
    bool same = false;
    for(int i=N;i>=1;--i){swap(temp[i],temp[1]);
        downAdjust(1,i-1);
        if(same){printf("Heap Sort\n");
            print();
            break;
        }
        if(isSame()){same = true;}
    }
}

int main()
{scanf("%d",&N);
    for (int i = 1; i <= N; ++i) {scanf("%d",&init[i]);
        temp[i] = init[i];
    }
    for (int i = 1; i <= N; ++i) {scanf("%d",&partial_sorted[i]);
    }
    if(InsertionSort()){printf("Insertion Sort\n");
        print();} else {
        // 重置 temp
        for (int i = 1; i <= N; ++i) {temp[i] = init[i];
        }
        HeapSort();}
    return 0;
}

关于算法-数据结构:PAT甲级1098-Insertion-or-Heap-Sort

题目粗心：

算法思路：

插入排序：

堆排序：

留神点：

提交后果：

AC 代码：