交换排序 (冒泡排序 && 快速排序)

1、冒泡排序

🔑 核心思想 🔑

  所谓交换，就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置，交换排序的特点是：将键值较大的记录向序列的尾部移动，键值较小的记录向序列的前部移动。

❗ 冒泡排序的特性总结：❕

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

  2️⃣ 时间复杂度：O(N^2)

  3️⃣ 空间复杂度：O(1)

  4️⃣ 稳定性：稳定

❗ 动图演示：❕

🧿 实现代码 ：

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

🧿 实现代码 BubbleSort 的优化版本 ：

   当遍厉一遍后发现没有 Swap 时，那么说数组就是有序的

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

         最好 O(N)

void Swap(int* px, int* py)
{
	int temp = *px;
	*px = *py;
	*py = temp;
}
void BubbleSortPro(int* a, int n)
{
	int i = 0;
	int j = 0;
	for (i = 0; i < n - 1; i++)
	{
		int flag = 1;
		for (j = 0; j < n - 1 - i; j++)
		{
			if (a[j] > a[j + 1])
			{
				flag = 0;
				Swap(&a[j], &a[j + 1]);
			}
		}
		//如果flag等于1说明此时数组是升序
		if (flag == 1)
			break;
	}
}

2、快速排序

🔑 核心思想 🔑

  快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法，其基本思想为：任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。

❗ 过程：❕

  1️⃣ 选出一个关键字 key，一般是头或者尾

  2️⃣ 经过一次单趟后，key 放到了正确的位置，key 左边的值比 key 小，key 右边的值比 key 大

  3️⃣ 再让 key 的左边区间有序、key 的右边区间有序

❗ 动图演示：❕

 一、首次单趟 (注意这三种方法首次单趟后不一定相同)

   💨 hoare 版本

 ❓ 如何保证相遇位置的值小于 key ❔

   💨 挖坑版本

   💨 前后指针法

 二、非首次单趟

🧿 实现代码 ：首次 + 非首次 + 递归版本

void Swap(int* px, int* py)
{
	int temp = *px;
	*px = *py;
	*py = temp;
}
void PartSortHoare(int* a, int left, int right)
{
	int keyi = left;
	while(left < right)
	{
		//左边作key，右边先走找小
		while(a[right] >= a[keyi] && left < right)
		{
			right--;
		}
		//右边找到小，再找左边的大
		while(a[left] <= a[keyi] && left < right)
		{
			left++;
		}
		//交换小大
		Swap(&a[right], &a[left]);
	}
	//交换key
	Swap(&a[keyi], &a[right]);
	//返回分割大小的那个下标
	return left;
}
int PartSortHole(int* a, int left, int right)
{
	int key = a[left];
	int hole = left;
	while (left < right)
	{
		//右边找小，填左坑
		while (left < right && a[right] >= key)
		{
			right--;
		}
		a[hole] = a[right];//填坑
		hole = right;//新的坑

		//左边找大，填右坑
		while (left < right && a[left] <= key)
		{
			left++;
		}
		a[hole] = a[left];//填坑
		hole = left;//新的坑
	}

	//将key填最后一个坑
	a[hole] = key;
	return hole;
}
int PartSortPoint(int* a, int left, int right)
{
	int keyi = left;
	int prev = left;
	int cur = prev + 1;
	while (cur <= right)
	{
		//cur比keyi大时，prev不会++；且排除了自己交换自己
		if (a[cur] < a[keyi] && ++prev != cur)
		{
			Swap(&a[prev], &a[cur]);	
		}
		//两种情况cur都要++
		cur++;
	}
	//交换keyi
	Swap(&a[keyi], &a[prev]);
	return prev;
}
void QuickSort(int* a, int left, int right)
{
	//递归的结束条件
	if (left >= right)
	{
		return ;
	}
	//keyi拿到分割大小的下标 - [left, keyi - 1]; [keyi]; [keyi + 1, right]
	//int keyi = PartSortHoare(a, left, right);//版本1
	//int keyi = PartSortHole(a, left, right);//版本2
	int keyi = PartSortPoint(a, left, right);//版本3
	
	//递归左
	QuickSort(a, left, keyi - 1);
	//递归右
	QuickSort(a, keyi + 1, right);
}

❓ QuickSort 的时间复杂度 ❔

🧿 实现 QuickSort 的优化代码 —— 优化有序的情况

  三数取中选 key —— left、mid、right 中不是最大也不是最小的数

//三数取中
int GetMidIndex(int* a, int left, int right)
{
	//int mid = (left + right) / 2;
	int mid = left + (right - left) / 2;//防止溢出版本
	if (a[left] < a[mid])
	{
		if (a[mid] < a[right])
		{
			return mid;
		}
		else if (a[left] < a[right])
		{
			return right;
		}
		else
		{
			return left;
		}
	}
	else //a[left] > a[mid]
	{
		if (a[mid] > a[right])
		{
			return mid;
		}
		else if(a[left] < a[right])
		{
			return left;
		}
		else
		{
			return right;
		}
	}
}
int PartSortHoarePro(int* a, int left, int right)
{
	int midi = GetMidIndex(a, left, right);
	Swap(&a[left], &a[midi]);
	int keyi = left;
	while (left < right)
	{
		while (a[right] >= a[keyi] && left < right)
		{
			right--;
		}
		while (a[left] <= a[keyi] && left < right)
		{  
			left++;
		}
		Swap(&a[right], &a[left]);
	}
	Swap(&a[keyi], &a[right]);

	return left;
}
int PartSortHolePro(int* a, int left, int right)
{
	int midi = GetMidIndex(a, left, right);
	Swap(&a[left], &a[midi]);
	int key = a[left];
	int hole = left;
	while (left < right)
	{
		//右边找小，填左坑
		while (left < right && a[right] >= key)
		{
			right--;
		}
		a[hole] = a[right];//填坑
		hole = right;//新的坑

		//左边找大，填右坑
		while (left < right && a[left] <= key)
		{
			left++;
		}
		a[hole] = a[left];//填坑
		hole = left;//新的坑
	}

	//将key填最后一个坑
	a[hole] = key;
	return hole;
}
int PartSortPointPro(int* a, int left, int right)
{
	int midi = GetMidIndex(a, left, right);
	Swap(&a[left], &a[midi]);
	int keyi = left;
	int prev = left;
	int cur = prev + 1;
	while (cur <= right)
	{
		//cur比keyi大时，prev不会++；且排除了自己交换自己
		if (a[cur] < a[keyi] && ++prev != cur)
		{
			Swap(&a[prev], &a[cur]);
		}
		//两种情况cur都要++
		cur++;
	}
	//交换keyi
	Swap(&a[keyi], &a[prev]);
	return prev;
}
void QuickSortPro(int* a, int left, int right)
{
	if (left >= right)
	{
		return;
	}
	//int keyi = PartSortHoarePro(a, left, right);//版本1
	//int keyi = PartSortHolePro(a, left, right);//版本2
	int keyi = PartSortPointPro(a, left, right);//版本3

	QuickSortPro(a, left, keyi - 1);
	QuickSortPro(a, keyi + 1, right);
}

❓ QuickSortHoarePro 的时间复杂度 ❔

  这里就不会出现最坏的情况 —— 有序，因为有了三数取中算法。

 
🧿 实现代码 ：首次 + 非首次 + 非递归版本

  任何一个递归代码，要改成非递归

   1、循环

   2、栈 (数据结构) + 循环

  显然这里的快排不好直接改成循环，还要借助栈，所以这里复用了之前 C 实现的栈，详解请转 ➡ 爆肝两万字，我爷爷都看的懂的《栈和队列》，建议各位观众姥爷先收藏

🔑 核心思想 🔑

void QuickSortNonR(int* a, int left, int right)
{
	ST st;
	StackInit(&st);
	//先入第一组区间
	StackPush(&st, right);
	StackPush(&st, left);
	//栈不为空
	while (!StackEmpty(&st))
	{
		//取栈顶left，并Pop
		int begin = StackTop(&st);
		StackPop(&st);

		//再取栈顶right，并Pop
		int end = StackTop(&st);
		StackPop(&st);

		//这里就用前后指针版本进行单趟排
		int keyi = PartSortPointPro(a, begin, end);
		
		//再入区间 [left, keyi - 1]; [keyi]; [keyi + 1, end]
			//右区间 —— 只有1个值不会入
		if (keyi + 1 < end)
		{
			StackPush(&st, end);
			StackPush(&st, keyi + 1);
		}
			//左区间 —— 只有1个值不会入
		if (begin < keyi - 1)
		{
			StackPush(&st, keyi - 1);
			StackPush(&st, begin);
		}
	}
	StackDestory(&st);
}