【数据结构入门】排序算法之交换排序与归并排序

19 阅读 0 评论 0 点赞

前言

在前一篇博客，我们学习了排序算法中的插入排序和选择排序，接下来我们将继续探索交换排序与归并排序，这两个排序都是重头戏，让我们接着往下看。

一、交换排序

1.1 冒泡排序

冒泡排序是一种简单的排序算法。

1.1.1 基本思想

它的基本思想是通过相邻元素的比较和交换，让较大的元素逐渐向右移动，从而将最大的元素移动到最右边。

动画演示：

1.1.2 具体步骤

从列表的第一个元素开始，重复进行以下步骤，直到最后一个元素：
- 遍历列表中的每一个相邻的元素。
- 如果相邻元素的顺序错误（较大的元素在前），则交换它们的位置。
重复上述步骤，直到列表中的所有元素都按照从小到大的顺序排列。

1.1.3 算法特性

冒泡排序是一种非常容易理解的排序
时间复杂度：O(N^2) ，其中n是列表的长度。因为算法需要对列表中的每个元素进行多次比较和交换操作。
空间复杂度：O(1)
稳定性：稳定

1.1.4 算法实现

void BubbleSort(int* a, int n)
{
	int isorder = 1;
	for (int i = 0; i < n; i++)
	{
		for (int j = 1; j < n-i; j++)
		{
			if (a[j-1] > a[j])
			{
				Swap(&a[j - 1], &a[j]);
				isorder = 0;
			}
		}
		if (isorder == 1)
		{
			break;
		}
	}
}

1.2 快速排序

快速排序是一种常用的排序算法。

1.2.1 基本思想

任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。

注意：

由于选取基准值是任意的，所以会有多种实现方式，每种方式最后的结果也不尽相同。

一般实现的大思路主要有三种：

1.hoare版本（左右指针法）

注意事项：

左边做key，右边先走；右边做key，左边先走。这样能够保证两个指针相遇时，以左边为key，相遇位置比key小正好可以交换；以右边为key时，相遇的位置比key大，正好可以交换。

原理如下：

以左边为例：

1.R找小，L找大没有找到，L遇到R

2.R找小，没有找到，直接遇到L，要么就是一个比key小的位置或者直接到keyi

类似的，右边做key，左边先走，相遇的位置就比key要大。

2.挖坑版本

3.前后指针版本

实现思路：

1.cur找到比key小的值，++prev， cur与prev位置的值交换，++cur；

2.cur找到比key大的值，++cur；

方法：

1.a[cur] < key , 交换left 和 cur 数据， left++, cur++;

2.a[cur] == key, cur++;

3.a[cur] > key, 交换cur 和 right数据， right++；

4.cur > right 结束

核心思想：

1.与key相等的值，往后推

2.比key小的值，往前甩

3.比key大的值，往后甩

4.与key相等的就在中间

1.2.2 具体步骤

选择列表中的一个元素作为基准值（pivot），一般选择列表的第一个元素。
遍历列表，将比基准值小的元素放到基准值的左边，将比基准值大的元素放到基准值的右边。
将基准值放到它最终的位置上，即左边的元素都比它小，右边的元素都比它大。
对基准值左边和右边的子列表，分别进行递归快速排序。

1.2.3 算法特性

快速排序整体的综合性能和使用场景都是比较好的，所以才敢叫快速排序
时间复杂度：O(N*logN)（经过优化后），在最坏情况下，快速排序的时间复杂度为O(n^2)，但是通过一些优化技巧，可以将其降低到O(nlogn)。快速排序是一种原地排序算法，即不需要额外的空间来存储排序结果。
空间复杂度：O(logN)
稳定性：不稳定

1.2.4 算法实现

在算法整体实现之前我们需要考虑一下快速排序算法的特殊性：

这个算法利用了分治的思想，理想的状态下，从中间分开，时间复杂度大大降低，如果每次选key都正好选到中间值，那么完全可以达到 $\log (n)$ ；

但是要是key选的不好，假如说选到最小值或最大值，那么这个排序的效率就会大打折扣，不如直接使用插入排序。

所以，不能简单的直接取左边的数或者右边的数，这样很容易造成key的选择不好，降低效率。

好用的方法有两个：

1. 随机选key

这种方式使用随机在数中选key的方式，来选择key，降低了选到最大或者最小值的概率。

srand((unsigned int)time(NULL));


void Swap(int* p1, int* p2)
{
	int tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}

int randi = left + (rand() % (right - left));
swap(&a[left], &a[randi]);

2.三数取中法

这种方法使用的较为普遍，通过选择三个数中中间的一个数来定key，在数据没有大量重复的情况下，对提高算法效率有很大帮助。

这里其实留下了一个坑，当数据大量重复时，快速排序的效率会降到Nlog(N)，如何解决这个问题，可以等等下一篇博客，会介绍三路划分优化快速排序算法。

void Swap(int* p1, int* p2)
{
	int tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}

//三数取中，有序情况下最快
int GetMidNumi(int* a, int left, int right)
{
	int mid = (left + right) / 2;
	if (a[mid] > a[left])
	{
		if (a[mid] < a[right])
		{
			return mid;
		}
		else if (a[left] > a[right])
		{
			return left;
		}
		else
		{
			return right;
		}
	}
	else //a[mid] <= a[left]
	{
		if (a[right] < a[mid])
		{
			return mid;
		}
		else if (a[right] > a[left])
		{
			return left;
		}
		else
		{
			return right;
		}
	}
}

int midi = GetMidNumi(a, left, right);
Swap(&a[left], &a[midi]);

1）hoare版本（左右指针法）

void Swap(int* p1, int* p2)
{
	int tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}

//三数取中，有序情况下最快
int GetMidNumi(int* a, int left, int right)
{
	int mid = (left + right) / 2;
	if (a[mid] > a[left])
	{
		if (a[mid] < a[right])
		{
			return mid;
		}
		else if (a[left] > a[right])
		{
			return left;
		}
		else
		{
			return right;
		}
	}
	else //a[mid] <= a[left]
	{
		if (a[right] < a[mid])
		{
			return mid;
		}
		else if (a[right] > a[left])
		{
			return left;
		}
		else
		{
			return right;
		}
	}
}
//hoare版本
int PartSort1(int* a, int left, int right)
{
	//优化：三数取中
	int midi = GetMidNumi(a, left, right);
	Swap(&a[left], &a[midi]);

	int keyi = left;
	//这地方left 不能先+1，否则最后一步交换会出问题
	while (left < right)
	{
		//右边先找小
		//注意内部没有判断left< right
		while (left < right && a[right] >= a[keyi])
		{
			right--;
		}
		//左边找大
		while (left < right && a[left] <= a[keyi])
		{
			left++;
		}

		Swap(&a[left], &a[right]);
	}
	//相遇位置一定比key小
	Swap(&a[keyi], &a[left]);
	keyi = left;

	return keyi;
}

2）挖坑版本

void Swap(int* p1, int* p2)
{
	int tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}

//三数取中，有序情况下最快
int GetMidNumi(int* a, int left, int right)
{
	int mid = (left + right) / 2;
	if (a[mid] > a[left])
	{
		if (a[mid] < a[right])
		{
			return mid;
		}
		else if (a[left] > a[right])
		{
			return left;
		}
		else
		{
			return right;
		}
	}
	else //a[mid] <= a[left]
	{
		if (a[right] < a[mid])
		{
			return mid;
		}
		else if (a[right] > a[left])
		{
			return left;
		}
		else
		{
			return right;
		}
	}
}
//挖坑版
int PartSort2(int* a, int left, int right)
{
	//优化：三数取中
	int midi = GetMidNumi(a, left, right);
	Swap(&a[left], &a[midi]);

	int key = a[left];
	int pit = left;
	//这地方left 不能先+1，否则最后一步交换会出问题
	while (left < right)
	{
		//右边先找小
		//注意内部没有判断left< right
		while (left < right && a[right] >= key)
		{
			right--;
		}
		a[pit] = a[right];
		pit = right;
		//左边找大
		while (left < right && a[left] <= key)
		{
			left++;
		}

		a[pit] = a[left];
		pit = left;
	}
	//相遇位置一定比key小
	a[pit] = key;

	return pit;
}

3）前后指针版本

//前后指针法
int PartSort3(int* a, int left, int right)
{
	int midi = GetMidNumi(a, left, right);
	if (midi != left)
	{
		Swap(&a[left], &a[midi]);
	}

	int keyi = left;

	int prev = left;
	int cur = left + 1;
			
	while (cur <= right)
	{
		if (a[cur] < a[keyi] && ++prev != cur)
		{
			Swap(&a[prev], &a[cur]);
		}
		
		++cur;
	}
	//这里prev直接换就好了，不用交换
	Swap(&a[prev], &a[keyi]);
	keyi = prev;
	
	return keyi;
}

4）快速排序调用程序

void QuickSort(int* a, int left, int right)
{
	//递归结束条件
	if (left >= right)
	{
		return;
	}

	//小区间优化 -- 小区间使用插入排序
	//这个数字不能太大，否则没有意义
	if ((right - left + 1) > 10)
	{
		int keyi = PartSort3(a, left, right);//只需改变1，2，3就可以改用三个快速排序版本

		//[begin, keyi-1] keyi [keyi+1, end]

		QuickSort(a, left, keyi - 1);
		QuickSort(a, keyi+1, right);
	}
	else
	{
		InsertSort(a + left, right - left +1);
	}
}

优化：

在区间长度小于10时，改用插入排序，然后再递归，增加了算法效率。但是一定要注意区间长度一定要设置的恰到好处，否则区间过长就起不到相应的作用了。

1.2.5 非递归实现(重点)

非递归的实现一般有两种方式：

1.直接改，适用于简单的递归，比如斐波那契数；
2.使用栈辅助改为非递归，适用于复杂的结构，利用栈先进先出的特点，对数据进行排序。

void QuickSortNonR(int* a, int left, int right)
{
	ST st;
	STInit(&st);
    //入栈，先入后出，所以先入右边的值
	STPush(&st, right);
	STPush(&st, left);
    //栈非空时，进行操作
	while (!STEmpty(&st))
	{
        //出栈
		int begin = STTop(&st);
		STPop(&st);
		int end = STTop(&st);
		STPop(&st);

		int keyi = PartSort3(a, begin, end);
		if (end > keyi + 1)
		{
			STPush(&st, end);
			STPush(&st, keyi + 1);
		}
		if (begin < keyi - 1)
		{
			STPush(&st, keyi - 1);
			STPush(&st, begin);
		}
	}
	STDestroy(&st);
}

二、归并排序

归并排序是一种分治算法，它将列表递归地拆分成两个子列表，然后将这两个子列表合并成一个有序的列表。

2.1 基本思想

它的基本思想是将待排序列表分解成若干个子列表，然后将这些子列表逐个合并，最终得到一个有序的列表。

动画演示：

2.2 具体步骤

将列表不断地二分，直到每个子列表只包含一个元素。
将两个有序的子列表合并成一个有序的列表。合并时，比较两个子列表的第一个元素，将较小的元素放到结果列表中，并将指针向后移动一位，依此类推，直到其中一个子列表为空。然后将另一个非空子列表的剩余部分直接放到结果列表中。
重复步骤2，直到所有的子列表都合并为一个有序的列表。

2.3 算法特性

1. 归并的缺点在于需要O(N)的空间复杂度，归并排序的思考更多的是解决在磁盘中的外排序问题。
2. 时间复杂度：O(N*logN)，其中n是列表的长度。
3. 空间复杂度：归并排序是一种稳定的排序算法，它需要额外的空间来存储临时的结果，所以空间复杂度为O(n)。
4. 稳定性：稳定

2.4 算法实现

//归并排序，O(NlogN)
void _MergeSort(int* a, int begin, int end, int* tmp)
{
	//递归结束条件
	if (begin >= end)
	{
		return;
	}
	int mid = (begin + end) / 2;
	//mid控制递归
	_MergeSort(a, begin, mid, tmp);
	_MergeSort(a, mid + 1, end, tmp);

	//[begin, mid] [mid+1, end]归并
	int begin1 = begin, end1 = mid;
	int begin2 = mid + 1, end2 = end;
	//i为每个栈帧中的独立变量，控制每一次的归并
	int i = begin;
	while (begin1 <= end1 && begin2 <= end2)
	{
		//begin1<=begin2，可以做到稳定
		if (a[begin1] <= a[begin2])
		{
			tmp[i++] = a[begin1++];
		}
		else
		{
			tmp[i++] = a[begin2++];
		}
		
	}
	//没排到的直接接到后面
	while (begin1 <= end1)
	{
		tmp[i++] = a[begin1++];
	}
	while (begin2 <= end2)
	{
		tmp[i++] = a[begin2++];
	}
	//覆盖到原数组
	memcpy(a+begin, tmp+begin, sizeof(int)*(end-begin+1));
}

void MergeSort(int* a, int n)
{
	int* tmp = (int*)malloc(sizeof(int) * n);
	if (tmp == NULL)
	{
		perror("malloc fail");
		return;
	}
	_MergeSort(a, 0, n - 1, tmp);

	free(tmp);
	tmp = NULL;
}

归并在实现时使用了递归所以一定要注意栈帧的开辟，防止爆栈。

事实上，归并的递归写法并不难，但是在大量数据归并时对栈帧的开销很大，很容易造成栈溢出，所以作为一名合格的程序员，一定要学会将递归改为非递归。

修正思路：

归并排序改非递归：数据多不好调试，可以打印出来看边界

复杂问题分解为简单问题：分类处理

1.end1越界？不归并了

2.end1没有越界，begin2越界了？跟1一样处理

3.end1、begin没有越界，end2越界了？继续归并，修正

void MergeSortNonR(int* a, int n)
{
	int* tmp = (int*)malloc(sizeof(int) * n);
	if (tmp == NULL)
	{
		perror("malloc fail");
		return;
	}

	int gap = 1;//gap是归并过程中，每组数据的个数
	while (gap < n)
	{
		for (int i = 0; i < n; i += 2*gap)
		{			
			//归并一次，拷贝一次（推荐）
			if (end1 >= n || begin2 >= n)
			{
				break;
			}
			if (end2 >= n)
			{
				end2 = n - 1;
			}
			//归并
			int j = i;
			while (begin1 <= end1 && begin2 <= end2)
			{
				//begin1<=begin2时可以做到稳定
				if (a[begin1] <= a[begin2])
				{
					tmp[j++] = a[begin1++];
				}
				else
				{
					tmp[j++] = a[begin2++];
				}
			}
			//没排到的直接接到后面
			while (begin1 <= end1)
			{
				tmp[j++] = a[begin1++];
			}
			while (begin2 <= end2)
			{
				tmp[j++] = a[begin2++];
			}
			//数据覆盖到原数组
			memcpy(a + i, tmp + i, sizeof(int) * (end2 - i + 1));
		}

		gap *= 2;//gap控制遍历
	}
	free(tmp);
	tmp = NULL;
}

三、算法复杂度及稳定性分析

总结

冒泡排序是简单的排序算法，通过交换相邻元素使得较大（小）的元素逐渐向右（左）移动，时间复杂度为O(n^2)。
快速排序是高效的排序算法，采用分治思想，通过选择基准元素将数组分割成左右子数组，进一步递归排序，平均时间复杂度为O(nlogn)。
归并排序也是高效的排序算法，采用分治思想，将数组分割成左右子数组，递归排序后再合并，时间复杂度为O(nlogn)。

快速排序和归并排序相比，快速排序更常用，但快速排序在最坏情况下可能达到O(n^2)的时间复杂度。在实际应用中，需要根据具体情况选择合适的排序算法。

本站资源均来自互联网，仅供研究学习，禁止违法使用和商用，产生法律纠纷本站概不负责！如果侵犯了您的权益请与我们联系！

转载请注明出处：免费源码网-免费的源码资源网站 » 【数据结构入门】排序算法之交换排序与归并排序

点赞(0) 打赏

本文分类：文章资讯
本文标签：【数据结构入门】排序算法之交换排序与归并排序
浏览次数：19 次浏览
本文链接：https://freeymw.com/article/26690.html

评论列表共有 0 条评论

暂无评论