4月6号排序算法（2）

堆排序

讲堆排序之前我们需要了解几个定义

什么叫做最大堆，父亲节点，以及孩子节点

将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。

 每个节点都是它的子树的根节点的父亲 。 反过来每个节点都是它父亲的孩子 。

下面讲一下思路：

第一步我们将待排序数组调整成最大堆的形式：父亲节点大于孩子节点（堆结构，父亲节点的下标为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)

稳定