快速排序的学习

快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法，其基本思想为：任取待排序元素序列中 的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。快速排序递归实现的主框架，发现与二叉树前序遍历规则非常像，我们在写递归框架时可想想二叉 树前序遍历规则即可快速写出来，后序只需分析如何按照基准值来对区间中数据进行划分的方式即可。

一般选最左边的/最右边的值做key

单趟排序以后的目标:左边的值比key小,右边的值比key大

快速排序最终结果如图所示

 过程:

选最左边的值做key,右边先走==>左右相遇时比key小

选最右边的值做key,左边先走==>左右相遇时比key大

//单趟的快速排序
int Partion(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 < right,怕两边碰面后还擦肩而过
			++left;

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

	Swap(&a[left], &a[keyi]);

	return left;
}

特殊场景一:

5 5 5 5 5

特殊场景二

5 6 7 8 9 

单趟排位,比key小的放左边和比key大的放右边

如果左子间有序,右子间有序,整体就有序

// O(N*logN)
void QuickSort(int* a, int left, int right)
{
	if (left >= right)
		return;

	int keyi = Partion(a, left, right);
	// [left, keyi-1] keyi [keyi+1, right]
	QuickSort(a, left, keyi - 1);
	QuickSort(a, keyi+1, right);
}

一个单趟的时间复杂度是O（N），一个完整的快排需要O（logN）趟这样的单趟排序。

递归过程:

递归程序的缺陷:递归深度大,容易栈溢出

快排顺序问题:

1.快排要左边放比key大 右边放比key小

        当选key为最左边,右边要先走.

如果左边最先走,就会出现 相遇的位置的值(大值)放到左边,不符合小值放左边.如图:

 左边先走,ij在9上相遇,6和9相遇,error了

        当选key为最右边,左边要先走.

---

---

 

2.挖坑法

// 挖坑法
int Partion2(int* a, int left, int right)
{
	// 三数取中 -- 面对有序最坏情况，变成选中位数做key，变成最好情况
	int mini = GetMidIndex(a, left, right);
	Swap(&a[mini], &a[left]);
    //key取最左边 最右边先走
	int key = a[left];
	int pivot = left;
	while (left < right)
	{
		// 右边找小, 放到左边的坑里面
		while (left < right && a[right] >= key)
		{
			--right;
		}

		a[pivot] = a[right];
		pivot = right;

		// 左边找大，放到右边的坑里面
		while (left < right && a[left] <= key)
		{
			++left;
		}
		a[pivot] = a[left];
		pivot = left;
	}

	a[pivot] = key;//相遇时 key放到坑位里去
	return pivot;
}

---

---

3.前后指针版本

过程:

// 推荐掌握这个 -- 这三种都要掌握
int Partion3(int* a, int left, int right)
{
	// 三数取中 -- 面对有序最坏情况，变成选中位数做key，变成最好情况
	int mini = GetMidIndex(a, left, right);
	Swap(&a[mini], &a[left]);

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

		++cur;
	}

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

---

---

快速排序优化

 三数取中法选key快排的缺陷:遇到有序(ON^2),解决方法:三数取中法选key

int GetMidIndex(int* a, int left, int right)
{
	//int mid = (left + right) / 2;
	int mid = left + ((right - left) >> 1);
	if (a[left] < a[mid])
	{
		if (a[mid] < a[right])
		{
			return mid;
		}
		else if (a[left] > a[right])
		{
			return left;
		}
		else
		{
			return right;
		}
	}
	else // a[left] > a[mid]
	{
		if (a[mid] > a[right])
		{
			return mid;
		}
		else if (a[left] < a[right])
		{
			return left;
		}
		else
		{
			return right;
		}
	}
}

int Partion1(int* a, int left, int right)
{
	// 三数取中 -- 面对有序最坏情况，变成选中位数做key，变成最好情况
	int mini = GetMidIndex(a, left, right);
	Swap(&a[mini], &a[left]);

	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[left], &a[keyi]);

	return left;
}

递归到小的子区间时，可以考虑使用插入排序

void QuickSort(int* a, int left, int right)
{
	if (left >= right)
		return;

	// 小区间优化，当分割到小区间时，不再用递归分割思路让这段子区间有序
	// 对于递归快排，减少递归次数
	
	{
		int keyi = Partion3(a, left, right);
		// [left, keyi-1] keyi [keyi+1, right]
		QuickSort(a, left, keyi - 1);
		QuickSort(a, keyi + 1, right);
	}	
}

快速排序非递归

问题:

当递归深度过大,容易造成栈溢出栈的大小是有限的,每次递归会占用一定空间.但是现在编译优化得很好，这个问题不大）。

递归改成非递归:

循环(但是有的东西是不好改成循环的，比如二叉树的遍历、快排等)

“栈”模拟（这个“栈”是数据结构中的“栈”，不是系统内部那个“栈”，一般用到栈难度都是略大的）这里的快排改非递归用的就是“栈”模拟。

思想:非递归的在这里借助栈，依次把我们需要单趟排的区间入栈，依次取栈里面的区间出来单趟排，再把需要处理的子区间入栈，以此循环，直到栈为空的时候即处理完毕。

// 递归深度太深的程序，只能考虑改非递归
void QuickSortNonR(int* a, int left, int right)
{
//先入右，后入左，就先拿到左

	ST st;
	StackInit(&st);
	StackPush(&st, left);
	StackPush(&st, right);

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

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

        //当前区间 [left,right]
		int keyi = Partion3(a, begin, end);
		// [begin, keyi-1] keyi [keyi+1, end]



        //划分左右区间，分别入栈
		//[left,key-1]    key    [key+1,right]
        //右区间
		if (keyi + 1 < end)
		{
			StackPush(&st, keyi+1);
			StackPush(&st, end);
		}
        //左区间
		if (begin < keyi-1)
		{
			StackPush(&st, begin);
			StackPush(&st, keyi-1);
		}
	}

	StackDestroy(&st);
}

快速排序的特性总结 1. 快速排序整体的综合性能和使用场景都是比较好的，所以才敢叫快速排序 2. 时间复杂度：O(N*logN) 3. 空间复杂度：O(logN) 4. 稳定性：不稳定

快速排序的代码链接