1098.Insertion or Heap Sort (25)

2019-11-06 07:16:10

字体：大中小

来源：转载

供稿：网友

pat-al-1098

2017-03-05

和“插入排序还是归并排序”是一个套路插入排序偷懒用了sort来排堆排要先建堆（对前一半的结点从下向上的每一个都进行一下fixdown），然后将堆顶元素和尾元素交换，（用大根堆，排完序之后得到的就是从小到大的序列），然后整个堆的size-1/** * pat-al-1098 * 2017-03-05 * Cpp version * Author: fengLian_s */#include<stdio.h>#include<algorithm>#define MAX 105using namespace std;int n;int origin[MAX], changed[MAX], tmp[MAX];int isSame(){ for(int i = 0;i < n;i++) { if(origin[i] != changed[i]) return false; } return true;}void showArray(){ PRintf("%d", origin[0]); for(int i = 1;i < n;i++) { printf(" %d", origin[i]); } putchar('/n');}int insertSort(){ int flag = 0; for(int i = 1;i < n;i++) { //printf("i = %d: ", i); //showArray(); if(i != 1 && isSame()) flag = 1; sort(origin, origin+i+1); if(flag == 1) return true; } return false;}void fixDown(int now, int size){ int index = now * 2 + 1; if(index >= size) return; if(origin[index] < origin[index+1] && index+1 < size) index++; if(origin[now] < origin[index]) { swap(origin[now], origin[index]); fixDown(index, size); }}void heapSort(){ //create heap: for(int i = n/2;i >= 0;i--) { fixDown(i, n); } int flag = 0; for(int i = n-1;i >= 0;i--) { if(i != n-1 && isSame()) flag = 1; swap(origin[0], origin[i]); fixDown(0, i); if(flag == 1) return; }}int main(){ freopen("in.txt", "r", stdin); scanf("%d", &n); for(int i = 0;i < n;i++) { scanf("%d", &origin[i]); tmp[i] = origin[i]; } for(int i = 0;i < n;i++) { scanf("%d", &changed[i]); } if(insertSort()) { printf("Insertion Sort/n"); showArray(); } else { for(int i = 0;i < n;i++) { origin[i] = tmp[i]; } printf("Heap Sort/n"); heapSort(); showArray(); }}

-FIN-

上一篇：Ubuntu设置中文方法

下一篇：动态规划之最长子序列长LCS