【数据结构常见七大排序（三）上】—交换排序篇【冒泡排序】And【快速排序】

void BubbleSort(int* a, int n)
{
	assert(a);
 
	for (int j = 0; j < n - 1; ++j)
	{
		int exchange = 0;//这里的exchange的值作为是否交换的标志
		for (int i = 1; i < n - j; ++i)
		{
			if (a[i - 1] > a[i])
			{
				Swap(&a[i - 1], &a[i]);
				exchange = 1;
			}
		}
 
		if (exchange == 0)//一趟下来exchange的值还为0，证明就没有发生交换，也就是已经有序
		{
			break;
		}
	}
}

1.3冒泡排序的特性总结

1. 冒泡排序是一种非常容易理解的排序

2. 时间复杂度： O(N^2)   最坏O(N^) 、最好O(N)

3. 空间复杂度： O(1)

4. 稳定性：稳定

2.快速排序👑

排序中

①先选出一个基准值key（一般是最左边或者最右边) 

②然后右边【L】先走找比key小的值，找到了就停下，然后再左边找比key大的值，找到了也停下

🥇

🥈

排序后

由于是一个一个先走一个后走，肯定会出现相遇的时候，相遇就停下来。相遇后将相遇坐标的值和基准值key交换，这时就完成了单趟的hoare排序

---

【这时的key其实就是在正确的位置上了】

---

相遇时如下图

🥉

2.2hoare版本快排源代码

void QuickSort(int* a, int begin, int end)
{
	// 区间不存在，或者只有一个值则不需要在处理
	if (begin >= end)
	{
		return;
	}
 
	int left = begin, right = end;
	int keyi = left;
	while (left < right)
	{
		// 右边先走，找小
		while (left < right && a[right] >= a[keyi])
		{
			--right;
		}
 
		// 左边再走，找大
		while (left < right && a[left] <= a[keyi])
		{
			++left;
		}
 
		Swap(&a[left], &a[right]);
	}
 
	Swap(&a[keyi], &a[left]);
	keyi = left;
 
	// [begin, keyi-1] keyi [keyi+1, end]
	QuickSort(a, begin, keyi - 1);
	QuickSort(a, keyi+1, end);
}

2.3分析先走

情况2🥈

这边也可以去画一下左边做key，左边先走的情况，会发现相遇位置的值不能保证比key要小

如果觉得文章不错，期待你的一键三连哦，你个鼓励是我创作的动力之源，让我们一起加油，顶峰相见！！！