算法---分治策略（快排）

分治策略之快速排序

快速排序是对冒泡排序算法的一种改进，快速排序在面试过程中被提到的概率还是很大的，本文章我将介绍一下有关快速排序的一些问题。

算法思想

（1）指定一个定界值，通过该值会将数组分成两部分
（2）将大于定界值的数据都放在右边，小于等于定界值的数据都放在左边，此时，以定界值为中心，左边全部都是小于等于定界值的数，右边全部都是大于定界值的数
（3）将左边的数据拿出来，又重新找一个定界值，重复上面的操作。右边的值也是相同的操作。
（4）可见，上面的操作是一个递归的过程，等左右两边的数据都进行完毕，即数组中的数据已经有序

eg：

矩形：定界值
线段：下一趟要进行快排的子序列

代码展示

递归方式

#include<stdio.h>
#include<assert.h>

int Parition(int* ar, int left, int right)
{
	int tmp = ar[left];
	while (left < right)
	{
		while (left < right && tmp < ar[right])
		{
			--right;
		}
		if(left < right)ar[left] = ar[right];
		while (left < right && ar[left] <= tmp)
		{
			++left;
		}
		if(left < right)ar[right] = ar[left];
	}
	ar[left] = tmp;
	return left;
}

void QuickPass(int* ar, int left, int right)//递归方式的快排
{
	if (left < right)
	{
		int  pos = Parition(ar, left, right);
		QuickPass(ar, left, pos - 1);
		QuickPass(ar, pos + 1, right);
	}
}

void QuickSort(int* ar, int n)
{
	assert(ar != NULL);
	QuickPass(ar, 0, n - 1);
}

非递归方式

#include<stdio.h>
#include<assert.h>
#include<stack>//c++中的栈
#include<queue>//c++中的队列

void NiceQuickSort_stack(int* ar, int n)//非递归用栈的方式
{
	assert(ar != NULL);
	stack<int> ist;
	ist.push(0);
	ist.push(n - 1);
	while (!ist.empty())
	{
		int right = ist.top(); ist.pop();
		int left = ist.top(); ist.pop();
		int pos = Parition(ar, left, right);
		if (left < pos - 1)
		{
			ist.push(left);
			ist.push(pos - 1);
		}
		if (pos + 1 < right)
		{
			ist.push(pos + 1);
			ist.push(right);
		}
	}
}

void NiceQuickSort_queue(int* ar, int n)//非递归用队列的方式
{
	assert(ar != NULL);
	queue<int> ist;
	ist.push(0);
	ist.push(n - 1);
	while (!ist.empty())
	{
		int left = ist.front(); ist.pop();
		int right = ist.front(); ist.pop();
		
		int pos = Parition(ar, left, right);
		if (left < pos - 1)
		{
			ist.push(left);
			ist.push(pos - 1);
		}
		if (pos + 1 < right)
		{
			ist.push(pos + 1);
			ist.push(right);
		}
	}
}

总结

快速排序的缺点:
1.越有序越慢,完全有序则为O(n^2);
2.空间复杂度为O(logn)不是O(1);3.不稳定;