快速排序(数组和迭代器法)

[TOC]

###### 快速排序的效率
>在平均状况下，排序 n 个项目要Ο(n log n)次比较。在最坏状况下则需要Ο(n2)次比 较，但这种状况并不常见。事实上，快速排序通常明显比其他Ο(n log n) 算法更快，因为它的内部循环（inner loop）可以在大部分的架构 上很有效率地被实现出来。

###### 算法步骤
* 从数列中挑出一个元素:“基准数”，
* 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。
* 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。

快速排序巧妙的利用了递归分治法
>递归分治法就是：将一个问题分解为与原问题相似但规模更小的若干子问题，递归地解这些子问题，然后将这些子问题的解结合起来构成原问题的解。这种方法在每层递归上均包括三个步骤
-  分解：将问题划分为若干个子问题
-  求解：递归地解这些子问题；若子问题Size足够小，则直接解决之
-  组合：将子问题的解组合成原问题的解

如果仅仅利用分治法说明快速排序，这样不足以使得小白明白,其实快速排序还有一个重点就是`(挖坑法)`。
###### 举个例子
一个有存放8个整数的数组a

|0|1|2|3|4|5|6|7|
|--|--|--|--|--|--|--|--|
|3|2|5|6|4|4|6|1|

- 第一步，将`left`代表数组第一个元素下标0（left=0），将`right`代表数组最后一个元素下标7（right=7），并且用`basic`记下第一个数组元素a[0]作为基准数，相当于挖坑挖了a[0]，如下图。

|0|1|2|3|4|5|6|7|
|--|--|--|--|--|--|--|--|
|[3]|2|5|6|4|4|6|1|

- 第二步，从right=7开始查找,直到找到一个数比`basic`小，显然`a[7]=1`比`basic`要小，所以将当前的数a[7]挖坑，将a[7]填入a[0]位置，现在的a[7]就是大坑，如下图。

|0|1|2|3|4|5|6|7|
|--|--|--|--|--|--|--|--|
|1|2|5|6|4|4|6|[1]|

- 第三部，从left=1开始查找，直到找到一个数比`basic`大，显然`a[2]=5`要比`basic`要大，所以将当前的a[2]挖坑，将a[2]填入a[7]的大坑,现在a[2]变成了大坑，如下图。

|0|1|2|3|4|5|6|7|
|--|--|--|--|--|--|--|--|
|1|2|[5]|6|4|4|6|5|

- 第四步，从right=6开始查找,直到找到一个数比`basic`小，显然直到`right=3于left值相同`也找不到，这时就要将basic填入a[2]大坑了，如下图。

|0|1|2|3|4|5|6|7|
|--|--|--|--|--|--|--|--|
|1|2|3|6|4|4|6|5|

- 从当前的数组看，基准数的左边的值都比基准值(3)要小，右边的值都比基准数(3)要大。

###### c语言实现
```c
/*************************************************************************
    > Function Name: quickSort
	> Function: 实现快速排序
	> Author: 卢孙远
    > Mail: 476941913@qq.com 
    > Created Time: 2017年04月14日 星期五 00时26分52秒
 ************************************************************************/
int quickSort(int a[],int left,int right)
{
	if(left < right){
		/*将该参数数组中的第一个数基准数,也就是说先挖一个坑*/
		int basic = a[left];
		int l = left,r = right;
		while(l < r){
			/*直到右边有一个数比基准数要小，就停止*/
			while(l < r && basic <= a[r])
				r--;
			/*补上了a[l]那个坑后又重新挖了a[r]这个坑*/
			if(l < r){
				a[l] = a[r];
				l++; /*l++放在最后面，防止不同编译器意外出错(《C陷阱与指针》有讲述)*/
			}
			/*直到左边有一个数比基准数要大，就停止*/
			while(l < r && basic > a[l])
				l++;
			/*补上了a[r]那个坑后又重新挖了a[l]这个坑*/
			if(l < r){
				a[r] = a[l];
		   	/*r--放在最后面，防止不同编译器意外出错(《C陷阱与指针》有讲述)*/
				r--;
			}
		}
		a[l] = basic;
		/*基准左边继续上述的操作*/
		quickSort(a,left,l-1);
		/*基准右边继续上述的操作*/
		quickSort(a,l+1,right);
	}
}
```
# 迭代器式
```
template<typename RandomAccessIterator,typename Compare>
void quick_sort1(RandomAccessIterator first, RandomAccessIterator last,Compare comp)
{
	if (first < last)
	{
		typename std::iterator_traits<RandomAccessIterator>::value_type basic = *first;
		RandomAccessIterator l = first;
		RandomAccessIterator r = last-1;
		while (l < r)
		{
			while (comp(basic,*r)&&l < r) --r;
			if (l < r)
			{
				*l = *r;
				l++;
			}
			while (comp(*l,basic)&&l < r)++l;
			if (l < r)
			{
				*r = *l;
				--r;
			}
		}
		*l = basic;
		quick_sort1(first, l - 1,comp);
		quick_sort1(l + 1, last,comp);
	}
}

测试：
std::function<void(int&)> print = [](int &x) { std::cout << x << " "; };
std::function<bool(int&, int&)> comp = [](const int& x, const int& y) {return x < y; };
int *a = SortTestHelper::generateRandomArray(20, 220, 1000);
std::vector<int> v(a,a+ 20);
//for_each(v.begin(), v.end(), print);
//rw_sort::sort(v.begin(), v.end());
self::quick_sort1(v.begin(), v.end(), [](int &x, int &y) {return x > y; });
std::cout << "\n";
//std::nth_element(v.begin(), v.begin() + 5, v.end(),std::greater<int>()); //不做全排序
for_each(v.begin(), v.end(), print);
std::cout << "\n";
```

###### 关于源码和文章
可以查看代码示例：[git源代码](https://git.oschina.net/LSU/alg.git)
此文章的markdown笔记：[git笔记](https://git.oschina.net/LSU/shujujiegouyusuanfamarkdown.git)

Simon 's Blog

导航

OHH,最近发表

这里随便填填,没事