U207421 归并排序 & 快速排序 & 堆排序
题目背景
## 快速排序
```cpp
#include
using namespace std;
void f(int a[],int x,int y){
if (x < y){
int mid = (x + y) / 2;
swap(a[mid],a[x]);
int i = x + 1,j = y;
while (i a[x]){
j--;
}
if (i > n;
for (int i = 0;i < n;i++){
cin >> a[i];
}
f(a,0,n - 1);
for (int i = 0;i < n;i++){
cout
题目描述
## 归并排序
```cpp
#include
using namespace std;
void k(int a[],int b[],int x,int t,int y){ //归并
int z = t + 1,i = x,v = x;
while (x
输入格式
## 堆排序
给出$n$个数，要在$O(nlogn)$的时间复杂度内完成排序。
---
### 思路（分治）
$1、$建立完全二叉树。
$2、$每一棵子树判断，根、左、右中最大的换到根的位置。
$3、$假设数组长度为$n$，为了使其满足大根堆的性质，那么可以从$[n/2,1]$对其进行调节。（$n/2$是最后一个度数不为$0$的结点的下标）
$4、$排序$★$
$(1)$ 将堆顶元素与堆的最后一个元素进行交换。
$(2)$ 输出堆顶元素，堆的大小减一。
$(3)$ 进行调整使其满足堆的性质。
$5、$时间复杂度：最好与最坏情况下均为$O(nlogn)$。
---
## 代码
```cpp
#include
#include
using namespace std;
void heap_adjust(int *arr,int i,int size){
int lchild = 2 * i; //左孩子
int rchild = 2 * i + 1; //右孩子
int max = i;
if (i = 1;i--){
heap_adjust(arr,i,size);
}
}
void heap_sort(int *arr,int size){ // 主排序
int i;
build_heap(arr,size);
for (i = size;i >= 1;i--){
swap(arr[1],arr[i]); //交换末尾值与最大值
heap_adjust(arr,1,i - 1); //下一次调整
}
}
void print_array(int *arr,int size){ //输出函数
for (int i = 1;i arr[i];
}
//输出
cout
输出格式
无