堆排序
讲堆排序之前我们需要了解几个定义
什么叫做最大堆，父亲节点，以及孩子节点
将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。
每个节点都是它的子树的根节点的父亲 。 反过来每个节点都是它父亲的孩子 。
下面讲一下思路：
第一步我们将待排序数组调整成最大堆的形式：父亲节点大于孩子节点（堆结构，父亲节点的下标为i，左孩子节点的下标为2*i+1，右孩子的节点下标为2*i+2）
第二步：我们将堆顶元素与待排序数组最后一个元素发生交换
第三步：待排序数组数据量减少一个，继续调整成最大堆形式。
代码如下
adjust函数
void adjust(int* nums, int start, int end) {
int father = start;
int child = 2 * father + 1;
while (child <= end) {
if ((child + 1) <= end && nums[child] < nums[child + 1]) {
child++;
}
if (nums[child] > nums[father]) {
swap(&nums[child], &nums[father]);
father = child;
child = 2 * father + 1;
}
else {
break;//调整防止死循环
}
}
}
堆函数
void heapsort(int* nums, int n) {
//初始化堆（形成最大堆）
//从最后一个父亲节点开始n/2-1;
//一直调整到父亲节点为0；
for (int i = n / 2 - 1; i >= 0; i--) {
adjust(nums, i, n - 1);//i是父亲节点下标，n-1是最后一个元素
}
//堆顶与待排最后一个元素交换
for (int j = n - 1; j >= 1; j--) {
swap(&nums[0], &nums[j]);
adjust(nums, 0, j - 1);
}
}
时间复杂度：O(nlogn)，不稳定。
快速排序
在讲快排之前我们引入三色旗问题
解题思路：
第一步定义两个变量 i=start-1，j=end+1,从index=0的位置开始遍历。
分析
如果后边的元素比基准值大，那么我们不需要交换，只需要将遍历数组的下标index++既可，如果后边的元素比基准值小的话，我们需要交换元素的位置，基准值前边的我们都遍历过了所以不用再依次比较了
思考一下将三色旗问题引入到快速排序算法中呢，
我们需要确定一个基准值，暂且将待排序数组的一个元素设置为基准值。
第二步找到比基准值大，比基准值小的元素，将待排序数组分成三部分。一个比基准值小的数组，基准值，比基准值大的数组。进行进行分区处理。利用递归的思想。
代码如下
void quicksort(int*nums,int start,int end){
if(start>=end)return;
int i=start-1;
int j=end+1;
int index=start;
int temp=nums[start];
while(index<j){
if(nums[index]<temp){
swap(&nums[++i],&nums[index]);
}else if(nums[index]>temp){
swap(&nums[--j],&nums[index]);
}else{
index++;
}
}
quicksort(nums,start,i);
quicksort(nums,j,end);
}时间复杂度：
最好的情况为O(nlogn),最糟糕情况O（n^2）;
稳定性：不稳定的。
归并排序
归并排序是用分治思想，三个步骤：
- 分解（Divide）：将n个元素分成个含n/2个元素的子序列。
- 解决（Conquer）：用合并排序法对两个子序列递归的排序。
- 合并（Combine）：合并两个已排序的子序列已得到排序结果。
将两个有序数组合并成一个有序数组
写一下代码
//归并排序
void merge(int*nums,int left,int mid,int right){
int *temp=(int*)malloc(sizeof(int)*(right-left+1));
int i=left;
int j=mid+1;
int index=0;
while(i<=mid&&j<=right){
if(nums[i]<=nums[j]){
temp[index++]=nums[i++];
}else{
temp[index++]=nums[j++];
}
}
while(i<=mid){
temp[index++]=nums[i++];
}
while(j<=right){
temp[index++]=nums[j++];
}
index=0;
for(int i=left;i<right;i++){
nums[i]=temp[index++];
}
free(temp);
}
void merg(int*nums,int left,int right){
if(left>=right)return;
int mid=(right-left)/2+left;
merg(nums,left,mid);
merg(nums,mid+1,right);
merge(nums.left,mid,right);
}归并排序的时间复杂度：最好的情况：O(nlogn),
最坏的时候O(n^2)
稳定
