PAT1098【插入排序+堆排序】
2024-09-07 13:00:45
简单插入排序：
简单插入排序的核心思想：
把一条这么个难看的序列默认分为两个排好序的和未排好序的两个部分；
所以一开始排好序的只有一个a[0]（好看的只有一个），难看的有N（数组长度）-1个a[1,n-1]；
然后呢，你就要顺序下来，把一个个难看的几个人插到好看的那一堆里去，好看的越来越多，难看的越来越少，最后变成了真的好看的；
代码：
void InsertionSort(int a[],int n) //a[]是要处理的数组，n是数组长度
{
int i,j;
int temp;
//默认两部分，一部分好看，一部分难看；
//把难看的解决就好了
for(i=1;i<=n-1;i++) //有n-1个难看的
{
temp=a[i];
for(j=i-1;j>=0;j--)
{
if(a[j]<temp) //这个难看孩子在好看的位置，就是前面那个比他小的时候
break;
a[j+1]=a[j];
}
a[j+1]=temp; //比他小的好看孩子的后面一个啊；就算最小的还比他大，j传出来会变成-1，j+1就是0了
}
}
堆排序：
堆排序的思想：
利用最大堆（最小堆）输出堆顶元素，即最大值（或最小值），将剩下的元素重新生成最大堆（或者最小堆），一直重复这个过程，直到所有的元素输出。
我们来学习一个开辟O(1)空间就能办事的堆排序。
其实很简单，就是把最大堆（或者最小堆）与它最后一个元素交换，然后重新建立最大堆。
代码主要做的事情就是：“向下过滤”，所以我们把这部分代码拿出来。
void Adjust(int a[], int i, int n)
{
int c,temp;
for(temp=a[i];(2*i+1)<n;i=c)
{
c=2*i+1;
if(c!=n-1&&a[c+1]>a[c])
c=c+1;
if(temp<a[c]) a[i]=a[c];
else break;
}
a[i] = temp;
}
然后开始写堆排序的步骤代码：
void Build(int a[],int n)
{
for(int i=(n-1)/2;i>=0;i--)//从有儿子的最后一个结点开始向下过滤
Adjust(a,i,n);
}
然后就是一个交换：
void Exchange(int a[],int n)
{
for(i = n - 1; i > 0; i--)
{
temp = a[0];a[0] = a[i];a[i] = temp;//交换
Adjust(a, 0, i);//将交换的新a[0]向下过滤一下得到最大堆
}
}
题目代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MAXN=1e2+10; bool Check(int a[],int b[],int n)
{
for(int i=0;i < n;i++)
if(a[i]!=b[i]) return false;
return true;
} //第 i 个元素向下过滤；
void Adjust(int a[], int i, int n)
{
int c,temp;
for(temp=a[i];(2*i+1)<n;i=c)
{
c=2*i+1;
if(c!=n-1&&a[c+1]>a[c])
c=c+1;
if(temp<a[c]) a[i]=a[c];
else break;
}
a[i] = temp;
} bool HeapSort(int a[], int n,int b[])
{
int c,i,temp;
//建立最大堆
for(i = (n-1)/2; i >= 0; i--) //从含有儿子节点的根开始。
Adjust(a, i, n);
//然后依次交换。
for(i = n - 1; i > 0; i--)
{
temp = a[0];a[0] = a[i];a[i] = temp;
Adjust(a, 0, i);
if(Check(a,b,n))
{
i--;
temp = a[0];a[0] = a[i];a[i] = temp;
Adjust(a, 0, i);
puts("Heap Sort");
for(int k=0;k<n;k++)
{
if(k) printf(" ");
printf("%d",a[k]);
}
return true;
}
}
return false;
} bool InsertionSort(int a[],int b[],int n)
{
int temp,i,j;
for(i=1;i<=n-1;i++)
{
temp=a[i];
for(j=i-1;j>=0;j--)
{
if(a[j]<temp) break;
a[j+1]=a[j];
}
a[j+1]=temp;
if(Check(a,b,n))
{
i++;
temp=a[i];
for(j=i-1;j>=0;j--)
{
if(a[j]<temp) break;
a[j+1]=a[j];
}
a[j+1]=temp;
puts("Insertion Sort");
for(int k=0;k<n;k++)
{
if(k) printf(" ");
printf("%d",a[k]);
}
return true;
}
}
return false;
} int main()
{
int n;
int a[MAXN],b[MAXN],c[MAXN];
scanf("%d",&n);
for(int i=0;i<n;i++)
{
scanf("%d",&a[i]);
c[i]=a[i];
}
for(int i=0;i<n;i++)
scanf("%d",&b[i]);
if(InsertionSort(a,b,n))
return 0;
if(HeapSort(c,n,b))
return 0;
}最新文章
- The method setPositiveButton(int, DialogInterface.OnClickListener) in the type AlertDialog.Builder is not applicable for the arguments
- 我所理解的Cocos2d-x
- 开发客户端软件时，出现System.Windows.Markup.XamlParseException错误
- MongoDB学习（四）客户端工具备份数据库
- DOM（三）使用DOM + Css
- jQuery1.11源码分析(6)-----jQuery结构总揽
- 使用存储过程来动态调用数据(SELECT)
- Atitit. 最佳实践 QA----减少cpu占有率--cpu占用太高怎么办
- 详解js和jquery里的this关键字
- DOM编程从入门到忘记
- java第一次作业0
- Unity UGUI实现分段式血条
- linux独有的sendfile系统调用--“零拷贝，高效”
- find 递归/不递归 查找子目录的方法
- JAVA JDK 环境变量配置--简单图解
- java 堆排序的实现
- Java并发：多线程和java.util.concurrent并发包总结
- Scrum Meeting Beta - 9
- C# 小叙 Encoding (一)
- 【.net开发者自学java系列】使用Eclipse开发SpringMVC（2）
热门文章