【算法】冒泡排序、快速排序

1 冒泡排序

时间复杂度：O(N^2)
空间复杂度：O(1)
稳定性：稳定

1.1冒泡排序思想

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

1.2冒泡排序代码实现

void BubbleSort(int* a, int n)// 最坏情况：O(N^2)  最好情况：O(N)
{
	for (int i = 0; i < n; i++)//总共遍历n次
	{
		int exchange = 0;
		int pointEnd = (n-1)- i;
		for (int point = 0; point <pointEnd; point++)//单趟把最大的交换到末尾
		{
			if (a[point] > a[point+1])//把大的放到后面
			{
				Swap(&a[point], &a[point+1]);
				exchange = 1;
			}
		}
		if (exchange == 0)//如果此次没发生任何交换，说明已有序
		{
			break;
		}
	}
}

2 快速排序

时间复杂度：O(NlogN)
（最坏情况确实会达到O（N * N），但是有三数取中的优化下，时间复杂度为O(NlogN)，总的来说，一般认为其时间复杂度为O(N*logN)）

空间复杂度：O(logN)
（最坏情况确实会达到O（N），但是有三数取中的优化下，空间复杂度为O(logN)，总的来说，一般认为其空间复杂度为O(logN)）

稳定性：不稳定

2.1快速排序思想

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

将区间按照基准值划分为左右两半部分的常见方式有：
(1)hoare版本

(2)挖坑法

(3)前后指针法

2.2快速排序优化

（1）三数取中：当选中的key值是最大或最小时，快速排序法的时间复杂度会到达O（nn），所以直接选取头或尾的数据可能会达到最坏情况，对此，我们进行三数取中操作，来让key值不是最大或最小。这样可以使时间复杂度变为O(nlogn)
以下为三数取中代码：

int GetMidIndex(int* a, int left, int right)//三数取中：取出三个数中第二大的数
{
	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 left;
		else
			return right;
	}
	else if(a[left] >= a[mid])
	{
		if (a[mid] > a[right])
			return mid;
		else if (a[left] < a[right])
			return left;
		else
			return right;
	}
}

（2）结合其他排序算法：当区间长度过小时可以采用插入排序，即先用快速排序将区间分到较小长度，后面再用普通的排序方法。

2.3快速排序代码实现

(1)hoare版本

int PartSort1(int* a, int left, int right)// hoare
{
	int mid = GetMidIndex(a, left, right);// 三数取中
	Swap(&a[left], &a[mid]);

	int keyIndex = left;//key选left，就先让R找小 反之，就先让L找大

	while (left < right)
	{
		while (left < right && a[right] >= a[keyIndex])//R找小 找的同时还必须满足left<right
		{
			--right;
		}

		while (left < right && a[left] <= a[keyIndex])// L找大 找的同时还必须满足left<right
		{
			++left;
		}

		Swap(&a[left], &a[right]);
	}

	int meetIndex = left;//此时left和right相遇，此时meetIndex就是下一次的分界点处

	Swap(&a[meetIndex], &a[keyIndex]);

	return meetIndex;
}

(2)挖坑法

int PartSort2(int* a, int left, int right)// 挖坑法
{
	int mid = GetMidIndex(a, left, right);	// 三数取中
	Swap(&a[left], &a[mid]);

	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;	  //拿去填坑的数的位置变成新的坑
	}

	a[hole] = key;//left和right相遇后，把key值填到这个相遇的坑上，此时hole就是下一次的分界点处
	return hole;
}

(3)前后指针法

int PartSort3(int* a, int left, int right)// 前后指针法
{
	int mid = GetMidIndex(a, left, right);// 三数取中
	Swap(&a[left], &a[mid]);

	int keyIndex = left;
	int prev = left;
	int cur = left + 1;
	while (cur <= right)
	{
		if (a[cur] < a[keyIndex])// 找小
		{
			prev++;

			if (prev != cur)//两者相等就没必要换，省去无用次数
				Swap(&a[cur], &a[prev]);
		}
		cur++;
	}

	Swap(&a[keyIndex], &a[prev]);

	return prev;
}

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

	int divIndex = PartSort3(a, begin, end);

	QuickSort(a, begin, divIndex - 1);
	QuickSort(a, divIndex + 1, end);
}

void QuickSort_minizoneInsertSort(int* a, int begin, int end)
{
	if (begin >= end)
	{
		return;
	}

	if (end - begin <= 8)//优化：如果区间小了，可以用插入排序，以防递归太深
	{
		InsertSort(a + begin, end - begin + 1);
	}
	else
	{
		int divIndex = PartSort3(a, begin, end);
		QuickSort(a, begin, divIndex - 1);
		QuickSort(a, divIndex + 1, end);
	}
}

3 非递归快速排序

相比于递归方式，非递归的方式主要有两个优点：
(1)递归建立栈会有所消耗，非递归可以减少此消耗，提高效率(不过对于现代计算机，这个优化微乎其微)
(2)递归的最大缺陷就是，如果栈帧的深度太深，可能会导致栈溢出。因为系统栈空间一般不大在MB级别，数据结构栈模拟非递归的话，数据是存储在堆上的，堆是GB级别的空间

3.1非递归快速排序思想

建立一个数据结构栈，将需要排序的区间的左右边界压出栈中，排序后将新的区间的边界在压入栈中，以此类推，模拟递归栈的调用

3.2非递归快速排序代码实现

void QuickSortNonR(int* a, int begin, int end)//非递归方式
{
	Stack st;
	StackInit(&st);
	StackPush(&st, begin);
	StackPush(&st, end);

	while (!StackEmpty(&st))
	{
		int right = StackTop(&st);
		StackPop(&st);

		int left = StackTop(&st);
		StackPop(&st);

		int keyIndex = PartSort3(a, left, right);
		
		if (keyIndex + 1 < right)
		{
			StackPush(&st, keyIndex + 1);
			StackPush(&st, right);
		}

		if (left < keyIndex - 1)
		{
			StackPush(&st, left);
			StackPush(&st, keyIndex - 1);
		}
	}
	StackDestroy(&st);
}