【排序篇3】快速排序、归并排序

发布时间:2024年01月14日

一、快速排序

1.1 递归

快速排序的递归采用二叉树的前序遍历的思路,单趟排序先确定好一个元素的位置,然后往后递归再确定其他子区域内的某个元素的位置,直到只有一个元素返回。

递归的图示:
在这里插入图片描述
代码:

void QuickSort(int* a, int begin, int end)
{
	//区间内小于等于1,就返回
	if (begin >= end)
	{
		return;
	}
	//单趟排序,返回确定位置好的元素下标
	int ki = partsort1(a, begin, end);
	//递归 - 区间:[begin, ki-1],[ki+1, end]
	QuickSort(a, begin, ki - 1);
	QuickSort(a, ki + 1, end);
}

接下来分析单趟排序的实现。有3种方式:Hoare法、挖坑法、前后指针法。

1??Hoare法
整体思路:

  • 通过三数取中获取较靠中间元素的下标mid,然后mid指向的元素与左端的元素进行交换,防止极端情况
  • 定义一个变量 ki = left 便于记录左端的值,注意ki是下标
  • 先移动右边再移动左边,right指向的元素大于等于ki指向的元素就减1往前走,小于就停下;left指向的元素小于等于ki指向的元素就+1往后走,大于就停下,然后两者停下分别指向的元素进行交换,然后先走右再走左继续移动
  • left与right相遇,跳出循环,交换ki指向的元素和left指向的元素,此时left指向的元素就是确定好位置的元素,最后返回下标left

图示:
在这里插入图片描述
代码:

//Hoare法
int partsort1(int* a, int left, int right)
{
	//获取较中间的元素的下标
	int mid = getmid(a, left, right);//三数取中
	Swap(&a[left], &a[mid]);//与左端交换,防止极端情况
	int ki = left;//注意ki得到的是下标
	while (left < right)
	{
		//先走右再走左
		while (left < right && a[right] >= a[ki])//是大于等于往前走,小于就停下
		{	// 防止走的过程中越界
			right--;
		}
		while (left < right && a[left] <= a[ki])//是小于等于往前走,大于就停下
		{    // 防止走的过程中越界
			left++;
		}
		Swap(&a[left], &a[right]);//交换两个元素
	}
	Swap(&a[ki], &a[left]);//把ki指向的元素交换到它最终的位置
	return left;//返回确定位置的元素的下标
}

问题1:为什么要三数取中

因为三数取中可以防止出现极端情况,该极端情况指:ki指向的元素本来就应该放在左端,比如:
在这里插入图片描述

如果大部分是这种最坏情况,导致快速排序的复杂度为O(N ^ 2)

三数取中可以取到较靠中间位置的元素的下标,尽可能避免了以上情况,就算有个别还是在最左端,但是对整体的效率并没有多大影响。所以三数取中对快速排序的优化有很大的帮助。

代码:

//三数取中
int getmid(int* a, int left, int right)
{
	int mid = (left + right) / 2;
	if (a[left] < a[mid])
	{
		if (a[mid] < a[right])
			return mid;
		else if (a[right] < a[left])
			return left;
		else
			return right;
	}
	else
	{
		if (a[mid] > a[right])
			return mid;
		else if (a[right] > a[left])
			return left;
		else
			return right;
	}
}

问题2:为什么ki取的是下标,不是数组元素

这与最后确定元素位置的交换有关,假设ki是数组元素,交换的是left指向的元素和ki,那么结果是left指向的元素变成了ki这个元素,但是数组左端的元素依旧没变。
在这里插入图片描述
ki取的是下标,才能真正交换数组左端和left指向的元素。

问题3:为什么先走右边,再走左边

举个栗子:
在这里插入图片描述
2??挖坑法

整体思路:

  • 三数取中,与Hoare法的步骤一样
  • ki取的是left指向的元素,为后面的填坑作准备
  • 定义一个坑hole = left (是下标)
  • 先走右边,停下后,将此时right指向的元素覆盖坑位的元素,然后产生新的坑位,right变成坑
  • 再走左边,停下后,将此时left指向的元素覆盖坑位的元素,然后产生新的坑位,left变成坑
  • 循环全部走完后,最终的hole就是ki要确定的位置,覆盖坑位,然后返回hole

图示:
在这里插入图片描述
代码:

//挖坑法
int partsort2(int* a, int left, int right)
{
	//获取较中间的元素的下标
	int mid = getmid(a, left, right);//三数取中
	Swap(&a[left], &a[mid]);//与左端交换,防止极端情况
	int ki = a[left];//注意ki得到的是数组元素
	int hole = left;//初始的坑的位置
	while (left < right)
	{
		//先走右再走左
		while (left < right && a[right] >= ki)//是大于等于往前走,小于就停下
		{	// 防止走的过程中越界
			right--;
		}
		a[hole] = a[right];//覆盖坑位的元素
		hole = right;//产生新的坑位
		while (left < right && a[left] <= ki)//是小于等于往前走,大于就停下
		{    // 防止走的过程中越界
			left++;
		}
		a[hole] = a[left];//覆盖坑位的元素
		hole = left;//产生新的坑位
	}
	a[hole] = ki;//确定元素的位置
	return hole; //返回确定位置的元素的下标
}

3??前后指针法

通过前面的两种方法可以发现:确定好某个元素的位置后,该元素的左右两个区间分别是小于这个元素和大于这个元素(以数组是1,2,3,4,5,6,7,8,9,10为例),也就是说要确定位置的元素是区分两个不同区间的标杆,所以这里可以使用前后指针法,用来区分两块区域。

整体思路:

  • 定义前后指针,cur=left+1,pre = left
  • 如果cur指向的元素小于等于ki指向的元素,pre先加1,再交换pre和cur分别指向的元素,然后cur++
  • cur循环完,交换pre和ki分别指向的元素,pre的位置就是确定好的位置,然后返回pre

图示:

在这里插入图片描述
代码:

//前后指针法
int partsort3(int* a, int left, int right)
{
	int mid = getmid(a, left, right);//三数取中
	Swap(&a[left], &a[mid]);//与左端交换,防止极端情况
	int ki = left;//注意ki得到的是下标
	int cur = left + 1, pre = left;//定义前后指针
	while (cur <= right)//范围限制
	{
		if (a[cur] <= a[ki])//如果小于,先++pre再交换分别指向的元素
		{
			Swap(&a[++pre], &a[cur]);
		}
		cur++;//cur都要往后走
	}
	Swap(&a[ki], &a[pre]);//把ki指向的元素交换到它最终的位置
	return pre;//返回确定位置的元素的下标
}

1.2 非递归

快速排序的非递归是用栈模拟递归来实现的,栈的特点是后进先出,递归是先左边再右边的,所以放入栈的数据应该先放右再放左,这样取数据才是先左再右。

图示:
在这里插入图片描述
代码:

//快速排序 - 非递归
void QuickSortNoR(int* a, int begin, int end)
{
	stack<int> st;//定义一个栈
	st.push(end);//先放右
	st.push(begin);//再放左
	while (!st.empty())//不为空进入循环
	{
		int left = st.top();//取左值
		st.pop();//删除栈顶元素
		int right = st.top();//取右值
		st.pop();//删除栈元素
		int ki = partsort3(a, left, right);//一趟排序确定某个元素的位置,返回该位置
		if (ki + 1 < right)//整体先放右
		{
			st.push(right);//里面先放右
			st.push(ki + 1);//里面再放左
		}
		if (left < ki - 1)//整体再放左
		{
			st.push(ki - 1);//里面先放右
			st.push(left);//里面再放左
		}
	}
}

快速排序特性总结:

  • 时间复杂度:O(N * logN)
  • 空间复杂度:O(logN)
  • 不稳定

二、归并排序

2.1 递归

归并排序的递归采用二叉树的后序遍历的思想,先分解成小块区间,然后再合并两个小块空间的同时将这两块子区间的元素进行排序。依次类推。这里还要额外开辟一块临时空间,用来对两个子区间排序,在临时空间排完序后,然后把已经排序的元素的拷贝到原数组对应的位置,最终将整个数组排完序。

图示:
在这里插入图片描述

代码:

//归并排序-递归
void MergeSort(int* a, int* tmp, int begin, int end)
{
	//区间内元素个数小于等于1返回
	if (begin >= end)
	{
		return;
	}
	int mid = (begin + end) / 2;//取划分区域的下标
	MergeSort(a, tmp, begin, mid);//递归左边
	MergeSort(a, tmp, mid + 1, end);//递归右边
	int begin1 = begin, end1 = mid;//合并的第一块小区间
	int begin2 = mid + 1, end2 = end;//合并的第二块小区间
	int k = begin;//注意k为begin当前区域的初始位置
	while (begin1 <= end1 && begin2 <= end2)
	{   //  谁小谁先放入tmp
		if (a[begin1] <= a[begin2])
		{
			tmp[k++] = a[begin1++];
		}
		else
		{
			tmp[k++] = a[begin2++];
		}
	}
	// 哪块小区间有剩余,直接放入tmp
	while (begin1 <= end1)
	{
		tmp[k++] = a[begin1++];
	}
	while (begin2 <= end2)
	{
		tmp[k++] = a[begin2++];
	}
	//最后拷贝到原数组对应的位置,完成排序
	memcpy(a + begin, tmp + begin, sizeof(int) * (end2 - begin + 1));
}

2.2 非递归

归并排序的非递归也是模拟递归的过程,只是没有递,只有归,即只有合并的过程,用for循环控制合并区间的大小和范围即可,也要借助临时空间来排序,最后拷贝给原数组。

图示:
在这里插入图片描述
代码:

//归并排序-非递归
void MergeSortNoR(int* a, int* tmp, int n)
{
	int gap = 1;//初始合并的子区间大小
	while (gap < n)//范围
	{
		for (int i = 0; i < n; i += gap * 2)
		{
			int begin1 = i, end1 = i + gap - 1;//合并的第一块小区间
			int begin2 = i + gap, end2 = i + gap * 2 - 1;//合并的第二块小区间
			int k = i;
			if (begin2 >= n)//只有第一块小区间,没有第二块小区间
			{
				break;//不能合并,跳出
			}
			if (end2 >= n)//第二块小区间个数较少,但是不影响合并
			{
				end2 = n - 1;//修改end2的值
			}
			while (begin1 <= end1 && begin2 <= end2)
			{
				if (a[begin1] <= a[begin2])
				{
					tmp[k++] = a[begin1++];
				}
				else
				{
					tmp[k++] = a[begin2++];
				}
			}
			while (begin1 <= end1)
			{
				tmp[k++] = a[begin1++];
			}
			while (begin2 <= end2)
			{
				tmp[k++] = a[begin2++];
			}
			memcpy(a + i, tmp + i, sizeof(int) * (end2 - i + 1));//排序+拷贝回原数组
		}
		gap *= 2;//区间增大
	}
}

注意:
上面的代码有两个特殊处理用于非2的次方个元素的数组,如果begin2大于等于n,说明要合并的两个子区间仅仅只有第一块小区间,没有第二块小区间,这时就不需要合并了(第一块小区间在之前已经合并为有序)。如果end2大于等于n,第二块小区间还是存在的,只是元素个数少些,这时就把end2的指向的位置该成第二块小区间内最后一个元素的位置即可。

归并排序特性总结:

  • 归并排序要额外开辟一块空间用来处理排序的问题
  • 时间复杂度:O(N * logN)
  • 空间复杂度:O(N)
  • 稳定
文章来源:https://blog.csdn.net/2301_77459845/article/details/135568817
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。