排序|冒泡排序|快速排序|霍尔版本|挖坑版本|前后指针版本|非递归版本|优化|三数取中(C)

交换排序

基本思想

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

冒泡排序

单趟

void Swap(int* x, int* y)
{
	int tmp = *x;
	*x = *y;
	*y = tmp;
}

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

		if (exchang == 0)
		{
			break;
		}
	}
}

• 两两比较，将较大的数换到后面，单趟把最大的数排到最后
• 第二趟排次大的数
• 直到全部排完

特性总结

1. 冒泡排序是一种非常容易理解的排序
2. 时间复杂度：$O(N^2)$
3. 空间复杂度：$O(1)$
4. 稳定性：稳定

快速排序

快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法

基本思想

任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列

• 左子序列中所有元素均小于基准值
• 右子序列中所有元素均大于基准值，
  然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。

霍尔版本

• 确定一个Key值
• 创建两个指针从两边往中间遍历
• 右指针找比Key值小的数，左指针找比Key值大的数，相互交换，把小的换到左边，把大的换到右边
• 继续往中间遍历，右边继续找小，左边继续找大，再交换
• 直到左右指针相遇停止，相遇的位置一定比Key小，交换Key和相遇位置
  意义：
  Key已经到达最终的位置，也就是排好序的位置
  Key左边和右边的数已然无序

int PartSort(int* a, int left, int right)
{
	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]);
	return left;
}

• 用left和right指向数组的最左边的数和最右边的数

• 将left赋给keyi，keyi指向最左边的数
  

• 左边找大，右边找小
  

• 交换left和right
  

• 继续走指针，交换
  

• 继续走，直到left和right相遇
  

• 将left与keyi交换
  

• 最后返回left

• 相等的值不需要交换

• 找大找小的过程中遇到key停止，防止数组越界

递归

//左闭右闭
void QuickSort(int* a, int begin, int end)
{
	if (begin >= end)
		return;

	int keyi = PartSort(a, begin, end);
	//[begin, keyi-1],keyi,[keyi+1,end]
	QuickSort(a, begin, keyi - 1);
	QuickSort(a, keyi + 1, end);

}

• 递归返回条件为begin与end相遇
• 走单趟排序，找出keyi，即中间位置的正确位置的数
• 继续递归排左半部分和右半部分
  

如何保证相遇位置比Key小

右边先走做到的，L先动
相遇：

1. R动，L不动，去跟L相遇
   L找见大，不动；R动，相遇的位置是在L的位置上，L和R在上一轮交换过，L是找大交换，交换后是换了一个比Key小的数在左边，所以相遇位置比Key小
2. L动，R不动，去跟R相遇
   R先走找到比Key小的数，停下来了；这是L找大，没有找到跟R相遇，相遇位置比Key小；相遇位置就是R停留的位置，停留的原因是比Key小
   所以左后相遇位置直接和Key交换

时间复杂度

理想情况下：
每次Key都是中位数，时间复杂度为$O(N\cdot {\log }_{2}N)$
有序或接近有序的情况下：
时间复杂度为$O(N^2)$

三数取中

大小取中间的那一个

int GetMidi(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[left] > a[right]) //mid是最大值
		{
			return left;
		}
		else
		{
			return right;
		}
	}
	else  //a[left] > a[mid]
	{
		if (a[mid] > a[right])
		{
			return mid;
		}
		else if (a[left] < a[right]) // mid最小
		{
			return left;
		}
		else
		{
			return right;
		}
	}
}

int PartSort(int* a, int left, int right)
{
	int midi = Getmidi(a, left, right);
	Swap(&a[left], &a[midi]);

	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]);
	return left;
}

有了三数取中，最坏情况几乎不会出现
因为三数取中是二分，所以越有序越快

挖坑法

int PartSort2(int* a, int left, int right)
{
	int midi = Getmidi(a, left, right);
	Swap(&a[left], &a[midi]);

	int key = a[left];
	//保存key值后，左边形成第一个坑
	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;
	}

	a[hole] = key;
	return hole;
}

• 将left和right指向数组的两边

• 将left位置的6赋给key，第一个位置空出来
  

• 右边先走，找小，填到左边
  

• 左指针走，找大，填到右边的坑
  

• 右指针走，找大，填到左边的坑
  

• 左指针继续走
  

• 右指针继续走
  

• 左指针走，这时left和right相遇，将key赋给left
  

前后指针版本

前后两个指针往后走
cur找小，++prev，交换prev和cur的值
prev有两种情况：

1. 在cur还没遇到比key大的值的时候，prev紧跟着cur
2. 在cur遇到比key大的值的时候，prev在比key大的一组值的前面
   交换：把比key大的值往后推，把比key小的值往前甩
   本质是把一段大于key的区间，推箱子似的往右推，同时小的甩到左边去

int PartSort3(int* a, int left, int right)
{
	int prev = left;
	int cur = prev + 1;

	int keyi = left;
	while (cur <= right)
	{
		if (a[cur] < a[keyi])
		{
			Swap(&a[++prev], &a[cur]);
		}
		++cur;
	}

	Swap(&a[prev], &a[keyi]);
	return prev;
}

• 将left赋给prev，cur为prev+1，left赋给keyi
  

• cur与prev一起向后遍历，直到cur遇到比key大的值时，prev停下
  

• 这样，cur指向第一个小于keyi的数，prev指向一组大于keyi的数的第一个数，交换prev和cur
  

• 继续遍历
  

• 继续
  

• 直到cur遍历完整个数组
• 最后交换prev与keyi
  

prev所在的位置是交换过的，cur把比keyi小的数交换过来，所以prev的数一定比keyi小

相同不交换版本

int PartSort3(int* a, int left, int right)
{
	int prev = left;
	int cur = prev + 1;

	int keyi = left;
	while (cur <= right)
	{
		if (a[cur] < a[keyi] && ++prev != cur)
		{
			Swap(&a[prev], &a[cur]);
		}
		++cur;
	}

	Swap(&a[prev], &a[keyi]);
	return prev;
}

优化

1. 三数取中法选key
2. 递归到小的子区间时，可以考虑使用插入排序
   满二叉树，最后一层的节点占总节点数的50%，倒数第二层占25%
   对比到快速排序的递归里而言，有序的情况下，三数取中，都是完整的二分，结构类似二叉树，一个节点就像一次递归一样
   只剩十个数的时候，还需要递推3次，消耗太大
   综合而言，对十个数的排序比对80%的数的递归分割让他有序消耗低，性能就有一定程度的提高
   递归分割过程，区间比较小以后，不再分割排序，选择插入排序

//左闭右闭
void QuickSort(int* a, int begin, int end)
{
	if (begin >= end)
		return;

	//小区间优化，小区间不再递归分割排序，降低递归次数
	if ((end - begin + 1) > 10)
	{
		int keyi = PartSort(a, begin, end);
		
		//[begin, keyi-1],keyi,[keyi+1,end]
		QuickSort(a, begin, keyi - 1);
		QuickSort(a, keyi + 1, end);
	}
	else
	{
		InsertSort(a + begin, end - begin + 1)
	}

}

非递归

借助栈
先入右再入左
先把数组的区间入栈0-9，找出key为6
先入6-9，再入0-4，出0-4，找出key为2，
先入3-4，再入0-1，出0-1，找出key为1，左为00，右为21，这时不再入栈
以此类推
用队列也可以，但用栈才是真正模拟递归的过程

void QuickSortNonR(int* a, int begin, int end)
{
	ST st;
	STInit(&st);
	STPush(&st, end);
	STPush(&st, begin);
	while (STEmpty(&st))
	{
		int left = STTop(&st);
		STPop(&st);
	
		int right = STTop(&st);
		STPop(&st);

		int keyi = PartSort3(a, left, right);
		//[left, keyi-1],keyi,[keyi+1, right]
		if (keyi + 1 < right)
		{
			STPush(&st, right);
			STPush(&st, keyi + 1);
		}
		
		if (left < keyi - 1)
		{
			STPush(&st, keyi - 1);
			STPush(&st, left);
		}
	}
	
	STDestroy(&t);
}

特性总结

1. 快速排序整体的综合性能和使用场景都是比较好的，所以才敢叫快速排序
2. 时间复杂度：$O(N\cdot {\log }_{2}N)$
3. 空间复杂度：$O({\log }_{2}N)$
4. 稳定性：不稳定