1098. Insertion or Heap Sort (25) 21'

简介: #include #include #include using namespace std;vector a, b;//note:堆排序从1开始void downAdjust(int low, int high...
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> a, b;
//note:堆排序从1开始
void downAdjust(int low, int high){
    int i = 1, j = i * 2;
    while (j <= high) {
        if(j + 1 <= high && b[j] < b[j] + 1)
            j = j + 1;
        if (b[i] < b[j]) {
            swap(b[i], b[j]);
            i = j;
            j = i * 2;
        }else break;
    }
}

int main(){
    int n;
    cin >> n;
    a.resize(n+1);
    b.resize(n+1);
    for (int i = 1; i <= n; i++)  cin >> a[i];
    for (int i = 1; i <= n; i++)  cin >> b[i];
    int i, j;
    for (i = 1; i <= n - 1 && b[i] <= b[i+1]; i++);
    for (j = i + 1; a[j] == b[j] && j <= n; j++) ;
    if (j == n+1) {
        cout << "Insertion Sort" << endl;
        sort(b.begin() + 1, b.begin() + i + 2);
    }else{
        cout << "Heap Sort" << endl;
        j = n;
        while(j >= 2 && b[j] >= b[j - 1]) j--;
        swap(b[1], b[j]);
        downAdjust(1, j - 1);
    }
    for (int i = 1; i <= n; i++)
        printf("%d%c", b[i], i == n ? '\n' : ' ');
    return 0;
}
目录
相关文章
|
1月前
|
人工智能 搜索推荐 算法
sort-04-heap sort 堆排序算法详解
这是一个关于排序算法的系列文章摘要,包括了10篇关于不同排序算法的链接,如冒泡排序、快速排序、选择排序、堆排序等。堆排序是一种基于比较的排序算法,利用了近似完全二叉树的结构并满足最大堆或最小堆的性质。最大堆中,每个节点的值都大于或等于其子节点。文章详细解释了最大堆的概念、节点访问方式以及堆的操作,包括堆调整和堆排序的过程,并通过图解展示了堆排序的具体步骤。此外,还提供了一个Java实现的堆排序代码示例。整个排序系列来源于一个开源项目,读者可以通过链接查看完整内容。
sort-04-heap sort 堆排序算法详解
|
1月前
|
搜索推荐 算法 Java
sort-08-counting sort 计数排序
这是一个关于排序算法的系列文章摘要。文章详细介绍了多种排序算法,包括冒泡排序、快速排序、选择排序、堆排序、插入排序、希尔排序、归并排序、计数排序、桶排序以及大文件外部排序。计数排序是一种线性时间复杂度的稳定排序算法,由 Harold H. Seward 在1954年提出。基础版计数排序通过创建一个与最大元素等长的新数组来统计每个元素出现的次数,然后填充排序结果。改良版则考虑了空间浪费问题,通过找出最小值来减少数组长度。此外,还提出了使用 TreeMap 来扩展排序算法以适应非数字元素的情况。
|
1月前
|
搜索推荐 算法 Java
sort-07-merge sort 归并排序
这是一个关于排序算法的系列文章摘要。文章涵盖了多种排序算法的详细解释,包括冒泡排序、快速排序、选择排序、堆排序、插入排序、希尔排序、归并排序、计数排序、桶排序以及大文件外部排序。归并排序是一种效率为O(nlogn)的排序算法,基于分治法,将序列分成两半,分别排序后再合并。文章提供了Java实现的递归和迭代版本。在归并排序的递归实现中,代码通过不断拆分和合并子序列完成排序,而迭代实现则是通过逐步增大子序列长度并进行两两归并来排序。整个系列可在GitHub找到相关源码。
|
1月前
|
搜索推荐 Python
堆排序(Heap Sort)
堆排序(Heap Sort)是一种选择排序算法,通过将待排序的元素构建成一个最大堆(或最小堆),然后将堆顶元素与堆尾元素交换,将堆的大小减一,再调整堆,使其重新满足最大堆(或最小堆)的性质。重复以上步骤,直到堆中只剩下一个元素,即排序完成。
25 2
|
8月前
|
存储 搜索推荐 算法
计数排序(Counting Sort)详解
计数排序(Counting Sort)是一种非比较排序算法,其核心思想是通过计数每个元素的出现次数来进行排序,适用于整数或有限范围内的非负整数排序。这个算法的特点是速度快且稳定,适用于某些特定场景。在本文中,我们将深入探讨计数排序的原理、步骤以及性能分析。
185 1
计数排序(Counting Sort)详解
|
11月前
|
算法 搜索推荐 Java
|
C++
【PAT甲级 - C++题解】1098 Insertion or Heap Sort
【PAT甲级 - C++题解】1098 Insertion or Heap Sort
64 0
2-路插入排序(Two-Way Insertion Sort)
算法介绍 算法描述 算法分析 代码实现 参考
|
移动开发 算法 搜索推荐
python实现【堆排序】(Heap Sort)
python实现【堆排序】(Heap Sort)
python实现【堆排序】(Heap Sort)