[数据结构与算法]手撕快排（总结）

• 快排、堆排、归并排序
• 链表快排（区分允许用值交换和不允许用值交换两种情况）
• 非递归快排要掌握
• 快排时间复杂度的推导过程？
• 写出来后，也要把下面这几个点考虑下 - 时间复杂度计算 - 控件复杂度计算 - 轴点随机取值 - 为什么与轴点相等也要换位置

快排思路

• 随便找一个数作为基准数6
• 初始状态下，数字6在序列的第1位
• 先从右往左找一个小于6的数，再从左往右找一个大于6的数，然后交换他们。这里可以用两个变量i和j，分别指向序列最左边和最右边。（i和j称为哨兵）
  
• 首先哨兵j开始出动。因为此处设置的基准数是最左边的数，所以需要让哨兵j先出动，这一点非常重要
• 哨兵j的使命就是要找小于基准数的数，而哨兵i的使命就是要找大于基准数的数，直到i和j碰头为止
  
  -哨兵i和哨兵j相遇于3，则将基准数6和3进行交换。
• 现在基准数6已经归位，此时我们已经将 将这个序列中所有比基准数大的数放在6的右边，比基准数小的数放在6的左边，接下来还需要分别处理这两个序列。

复杂度

快速排序的时间复杂度为：

快排实现

递归版本快排

//快速排序（从小到大）
void quickSort(int left, int right, vector<int>& arr)
{
	if(left >= right)
		return;
	int i, j, base, temp;
	i = left, j = right;
	base = arr[left];  //取最左边的数为基准数
	while (i < j)
	{
		while (arr[j] >= base && i < j)
			j--;
		while (arr[i] <= base && i < j)
			i++;
		if(i < j)
		{
			temp = arr[i];
			arr[i] = arr[j];
			arr[j] = temp;
		}
	}
	//基准数归位
	arr[left] = arr[i];
	arr[i] = base;
	quickSort(left, i - 1, arr);//递归左边
	quickSort(i + 1, right, arr);//递归右边
}

非递归版本快排：
1.用栈集合存放左右下标
2.用一个方法来得出中下标位置
3.判断中下标的左右区间
4.回到步骤1循环这几步操作，知道栈为空，则排序完成。

#include <iostream>
#include <stack>
using namespace std;
 
//划分算法
int Partition( int a[], int low, int high )
{
	//假设每次都以第一个元素作为枢轴值，进行一趟划分：
	int pivot = a[low];
	 
	while( low<high )
	{
		while( low<high && a[high]>=pivot )
		--high;
		a[low] = a[high];  //停下来做交换 
		while( low<high && a[low]<=pivot )
		++low;
		a[high] = a[low];  //停下来做交换 
	}
	
	a[low] = pivot;  //pivot的最终落点 
	return low;
}
 
//非递归快排
void QuickSort(int a[], int left, int right)
{
	//手动利用栈来存储每次分块快排的起始点
	//栈非空时循环获取中轴入栈
	stack<int> s;
	if( left<right )
	{
		int boundary = Partition(a,left,right);
		
		if( boundary-1>left ) //确保左分区存在 
		{
			//将左分区端点入栈 
			s.push(left);
			s.push(boundary-1);
		}
		if( boundary+1<right ) //确保右分区存在 
		{
			s.push(boundary+1);
			s.push(right);
		}
		
		while( !s.empty() )
		{
			//得到某分区的左右边界 
			int r = s.top();
			s.pop();  
			int l = s.top();
			s.pop();
			
			boundary = Partition(a,l,r);
			if( boundary-1>l ) //确保左分区存在 
		    { 
			    //将左分区端点入栈 
		    	s.push(l);
		    	s.push(boundary-1);
	    	}
		    if( boundary+1<r ) //确保右分区存在 
	     	{
	 	    	s.push(boundary+1);
	    		s.push(r);
	    	}
		}
	}
}
 
int main()
{
	int a[5] = { 4, 1, 5, 3, 2 };
	int left = 0, right = 4;
	QuickSort(a,left,right);
	
	//输出，检验结果 
	for( int i=0; i<5; ++i )
	{
		cout << a[i] << " ";
	}
	
	cout << endl;
}

point1

当基准数选择最左边的数字时，那么就应该先从右边开始搜索；当基准数选择最右边的数字时，那么就应该先从左边开始搜索。不论是从小到大排序还是从大到小排序！