排序算法
堆排序
堆(最大堆)的概念
- 是一棵完全二叉树;
- 父节点必大于子结点.
一棵完全二叉树可以直接用一个数组来表示, 上面的堆可以写为int arr[]={10, 5, 8, ...}. 且可以方便地由父节点或子节点推出对方.
假设储存在数组中某一个节点的索引值是3, 则其父节点和子节点的索引值为
heapify(堆化)
对比一组父节点与子节点, 若最大值落在子节点上, 则将该值与父节点上的值交换.
对一棵树作heapify
若树的层数为h, 则从第h-1层开始由下往上进行heapify.
#include <stdio.h>
void swap(int arr[], int i, int j){
arr[i] += arr[j];
arr[j] = arr[i] - arr[j];
arr[i] = arr[i] - arr[j];
}
void heapify(int tree[], int n, int i){
if (i >= n)
return ;
int c1 = 2 * i + 1, c2 = 2 * i + 2;
int max = i;
max = tree[c1] > tree[i] && c1 < n ? (tree[c1] > tree[c2] && c2 < n ? c1 : c2) : (tree[c2] > tree[i] && c2 < n ? c2 : i);
if (max != i){
swap(tree, max, i);
heapify(tree, n, max);
}
}
void build_heap(int tree[], int n){
int lastNode = n - 1;
int parent = (lastNode - 1) / 2;
for(int i = parent; i >= 0; i--)
heapify(tree, n, i);
}
int main(){
int tree[6] = {2, 5, 6, 1, 10, 4};
int n = 6;
build_heap(tree, n);
for(int i = 0; i < n; i++)
printf("%d ", tree[i]);
return 0;
}
最终输出的结果为 10 5 6 1 2 4
排序
知道了heapify的流程后, 可以上手堆排序的完整过程.
- 堆的最大值必然落在根节点上, 我们将其取出, 并砍断最后一位的叶子节点, 将其值赋给根结点;
- 从根结点开始作heapify, 使得最大值再次落在根结点上面;
- 回到第一步循环执行, 直到完成排序.
完整的代码如下
#include <stdio.h>
void Swap(int arr[], int i, int j){
arr[i] += arr[j];
arr[j] = arr[i] - arr[j];
arr[i] = arr[i] - arr[j];
}
void Heapify(int tree[], int n, int i){
if (i >= n)
return;
int c1 = 2 * i + 1, c2 = 2 * i + 2;
int max = i;
if(c1 < n && tree[c1] > tree[max])
max = c1;
if(c2 < n && tree[c2] > tree[max])
max = c2;
if (max != i){
Swap(tree, max, i);
Heapify(tree, n, max);
}
}
void BuildHeap(int tree[], int n){
int lastNode = n - 1;
int parent = (lastNode - 1) / 2;
for(int i = parent; i >= 0; i--)
Heapify(tree, n, i);
}
void HeapSort(int tree[], n){
BuildHeap(tree, n);//建一个堆
for(int i = n - 1; i > 0; i--){
Swap(tree, i, 0);
Heapify(tree, i, 0);
}
}
int main(){
int tree[9] = {4, 5, 3, 2, 1, 6 ,8, 7, 9};
int n = 9;
HeapSort(tree, n);
for(int i = 0; i < n; i++)
printf("%d ", tree[i]);
return 0;
}
归并排序
归并排序是采用分治法的排序算法. 它的基本做法是, 将已有序的子序列合并, 得到完全有序的序列, 即先使每个子序列有序, 再使子序列段间有序. 若将两个有序表合并成一个有序表, 称为二路归并. 假如一个数组有8个元素, 将其划分到最小的序列组成 (8 - 4 - 2 - 1) 需要四次, 即 log28=4, 所以归并排序的时间复杂度为logn.
#include <stdio.h>
void merge(int arr[], int L, int M, int R){
int LeftSize = M - L, RightSize = R - M + 1;
int left[LeftSize], right[RightSize];
for(int i = L; i < M; i++)//将待分数组的左半部分写入left数组
left[i - L] = arr[i];
for(int i = M; i <= R; i++)//将待分数组的右半部分写入right数组
right[i - M] = arr[i];
int i = 0, j = 0, k = L;//将两个有序数组进行归并
while(i < LeftSize && j < RightSize){
if(left[i] < right[j]){
arr[k] = left[i];
i++;
k++;
}
else{
arr[k] = right[j];
j++;
k++;
}}
while(i < LeftSize){//如果归并后left或right数组还有剩余元素
arr[k] = left[i];//则将其全部填入arr数组
i++;
k++;
}
while(j < RightSize){
arr[k] = right[j];
j++;
k++;
}
}
void mergeSort(int arr[], int L, int R){
if(L == R)
return;
int M = (L + R) / 2;
mergeSort(arr, L, M);//递归地对左半部分进行排序
mergeSort(arr, M + 1, R);//递归地对右半部分进行排序
merge(arr, L, M + 1, R);//实际的排序操作
}
int main(){
int arr[] = {2, 9, 8, 3, 4, 7, 6, 5};
mergeSort(arr, 0, 7);
for(int i = 0; i < 8; i++)
printf("%d ", arr[i]);
return 0;
}
