九大排序之选择排序和归并排序

1.前言

每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。

本章重点：

堆排序和选择排序和归并排序

2.选择排序

基本思路

left和right记录区间的左端和右端；
不断遍历数组，经过一次遍历选出区间中的最大值和最小值；
然后将最小值换到左端，最大值换到右端；
++left; --right; 当left < right时循环继续。

注意：交换元素时如果先后交换的下标恰好相同需要做出调整。

代码如下：

void SelectSrot(int *arr, int n){
	assert(arr != NULL);
	
	int begin = 0;
	int end = n-1;
	//begin,end向中间靠拢
	while (begin < end)
	{
		int maxi = begin;
		int mini = begin;
		//一次循环找出一个最大值和一个最小值分别放到begin和end位置
		for (int i = begin; i <= end; i++)
		{
			if (arr[i] < arr[mini])
			{
				mini = i;
			}
			if (arr[i] > arr[maxi])
			{
				maxi = i;
			}
		}
		//因为先将maxi和end交换，所以当后换的mini==end 时原来end的值已经被换走了，转换一下
		if (maxi == begin)
		{
			maxi = mini;
		}
        Swap(&arr[begin], &arr[mini]);	
		Swap(&arr[end], &arr[maxi]);
		begin++;
		end--;
	}
}

直接选择排序的特性总结：
1. 选择排序思路简单好理解，但是对有序序列无反应，复杂度恒为O(N^2)。效率低，实际中很少使用。
2. 时间复杂度：O(N^2)
3. 空间复杂度：O(1)
4. 稳定性：不稳定(有可能两个相等元素的相对顺序会发生变化)
5. 数据敏感性：不敏感，不管有序无序都要进行多轮次的选择

2.堆排序

在写堆排序之前先写一个节点向上调整和节点向下调整

AdJustDown:

//向下调整，小的在上，大的在下
void AdjustDown(int *arr, int sz, int root)//父亲节点的下标
{
    assert(arr!=nullptr);
    int parent=root;
    int child=2*parent+1;//左节点
    while(child<sz)
    {
        //先判断谁小---找小
        if(child+1<sz&&arr[child]<arr[child+1])
            child++;
        if(arr[child]<arr[parent])
        {
            swap(&arr[child],&arr[parent]);
            parent=child;
            child=2*parent+1;
        }
        else  break;
    }
}

AdJustUp:向上调整

//向上调整---大的在顶部
void  AdJustUp(int *arr,int sz,int root)//这里传来的是孩子节点
{
    assert(arr!=nullptr);
    int child=root;
    int parent=(child-1)/2;
    while(child<sz)
    {
        if(arr[child]<arr[parent])
        {
            swap(&arr[child],&arr[parent]);
            child=parent;
            parent=(child-1)/2;
        }
        else break;
    }
    
}

构建一个堆，一般来说都是从第一个非叶子节点开始构建堆。

void  HeapSort(int* arr,int sz)
{
      assert(arr!=nullptr);
      for(int i=(sz-1-1)/2;i>=0;i--)
       {
           AdJustDown(arr,sz,i);
       }

       //大堆建立完了之后。开始排序
       for(int end=sz-1;end>=0;end--)
    {
        swap(&arr[end],&arr[0]);//最大值调整到了最后一个，最小值调整到了第一个
        AdJustDown(arr,sz,0);//再把最小值进行调整
        
    }    
}

思路总结：

1.首先写一个向上调整或者向下调整函数

2.调整堆：如果是需要升序的话---那么就是大堆---大堆就是说大的在上

如果是需要降序的话--那么就是小堆---小堆就是说小的在上

3.利用堆删除的思想来进行排序

记录堆尾下标end；
交换堆顶(0)堆尾(end)元素——将最大值交换到序列尾。
向下调整，但此时的调整范围到end——恢复堆结构选出最大值
–end——进行下一轮选择交换。

堆排序(Heapsort)是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。它是通过堆来进行选择数据。需要注意的是排升序要建大堆，排降序建小堆。

堆排序的特性总结：
堆排序使用堆来选数，效率就高了很多。
时间复杂度：O(N*logN)
空间复杂度：O(1)
稳定性：不稳定，由于使用了堆结构，无法保证稳定性数据
敏感性：不敏感，不管有序无序都要重新建堆排序

3.归并排序

归并排序就是找到一个基准值，大的在基准值的右，小的在基准值的左边。

然后开始递归-------当只有一个元素时就不需要了，然后返回上一层，再次进行排序即可。

具体步骤如下：

正式排序前需要创建与待排数组相同大小的数组tmp。
首先计算出中间位置的下标，将序列一分为二。
如果子区间元素个数大于1则向下递归先使左右子区间有序
然后将左右子区间归并到tmp数组
最后将数据考回原数组。

代码如下：

void _MergeSort(int *arr, int left, int right, int *tmp)
{
	//注意递归的结束条件
	if (left >= right)
	{
		return;
	}
	//计算出中间位置的下标
	int mid = left + (right - left) / 2;
	//划分左右区间
	int begin1 = left, end1 = mid;
	int begin2 = mid + 1, end2 = right;
	//先使左右两区间有序
	_MergeSort(arr, begin1, end1, tmp);
	_MergeSort(arr, begin2, end2, tmp);
	//将左右两区间归并到tmp数组
	//注意排序的区间不从0开始
	int i = left;
	while (begin1 <= end1 && begin2 <= end2)
	{
		if (arr[begin1] < arr[begin2])
		{
			tmp[i++] = arr[begin1++];
		}
		else
		{
			tmp[i++] = arr[begin2++];
		}
	}
	while (begin1 <= end1)
	{
		tmp[i++] = arr[begin1++];
	}
	while (begin2 <= end2)
	{
		tmp[i++] = arr[begin2++];
	}
	//将排好的数据从tmp数组考回arr
	for (int j = left; j <= right; j++)//注意这里一定是从left-right而不是从0-sz-1
    //因为当递归进去之后，就不一定是0-sz-1了。也有可能是只有两个数：例 下标2-3
	{
		arr[j] = tmp[j];
	}
}

void MergeSort(int *arr, int sz){
	//递归排序过程中需使用额外空间
	int *tmp = (int*)malloc(sizeof(int) * sz);
	if (tmp == NULL)
	{
		perror("MergeSort");
		exit(1);
	}
	_MergeSort(arr, 0, sz - 1, tmp);

	//排序结束后记得释放额外空间
	free(tmp);
	tmp = NULL;
}