基础算法（一）排序

快速排序

快速排序（quick sort）是一种比较常用而且比较基础的排序算法，第一次知道这个算法还是当我查询c++的sort函数是如何实现的时候知道的，其实，c++的sort就是一种优化之后的快排。

基本思想

快速排序的基本思想其实就是分治（divide and conquer），具体的实现逻辑可分为三步：

先从数组中确定一个数作为分界点，这个分界点的取法没有限制，我们一般取第一个数，最后一个数或中间的数均可。
调整区间，在确定分界点x后，数组被分成两个区间，我们在这一步要做的就是把数组中所有小于等于x的数放到左区间，所有大于等于x的数放到右区间。
递归处理左右两段，处理完左右两段后，两个区间已经有了基本的有序性，接下来我们只需对两段继续进行上述操作，直至个区间只有一个数，这样整个数组就是有序的了。

实现方法

在了解快排的基本思想后，我们可以知道，第一步和第三步都是比较简单的，重要的是如何优美地实现第二步，对此，这里介绍两种实现方法。

第一种，我们在原来数组Q的基础上，再创建两个额外的数组A和B，之后遍历数组Q，把所有小于等于x的数放到A中，所有大于x的数放到B中，遍历完之后，再把A和B写入Q中。这样的方法是很容易想到的，但有一个很明显的缺点，那就是创建数组需要内存空间，加上递归，需要的空间会很大，这样暴力的做法显然不能成为最优解，于是，我们来看看第二种。

第二种做法，我们不创建新的数组，而是用两个指针a和b分别指向数组的最左端和最右端，然后让指针a开始向右移动，如果a指向的数是小于等于分界点x的，那么a++，直到a指向的数大于x，a停止移动，接着移动b，同理，如果b指向的数大于等于x的，那么b–，直到b指向的数小于等于x，b停止，然后我们交换a和b所指向的数，并继续上述操作，直到两指针相遇。通过这种方法，我们能够不占用任何额外空间，同时快速的完成区间的调整。

代码模板

#include <iostream>

using namespace std;

void quick_sort(int q[], int l, int r)
{
	if (l >= r) return;

	int x = q[l + r >> 1], i = l - 1, j = r + 1; //选取分界点x， 并定义i和j
	while (i < j)
	{
		while (q[++i] < x); //移动i直至q[i]>=x
		while (q[--j] > x); //移动j直至q[j]<=x
		if (i < j)
		{	//交换两个数
			int temp = q[i];
			q[i] = q[j];
			q[j] = temp;
		}
	}
	//递归处理左右两段
	quick_sort(q, l, j);
	quick_sort(q, j + 1, r);
}

归并排序

归并排序（merge sort）也是一种比较常见的排序方法，这里可以说是把递归运用到了极致，一开始我还有点晕，之后看了关于归并操作的图解之后就清晰多了。

基本思想

这里归并排序也是采用了分治的策略，具体实现方法如下：

选取分界点，和快排一样，我们需要选择一个分界点，但是，我们这里一般是选择中间点。
递归排序，这一部分是比较难理解的，这样说，如果要完成后面的归并，我们合并的这两个区间首先必须得是有序的，但是我们选取完分界点后，显然两个区间不会是完全有序的，这样我们就需要进行递归，一直递归到几乎每个区间都只剩一个数，这样我们能说每个区间都是有序的，然后再来进行下面的操作。
归并——合二为一，在递归操作后，我们能保证要合并的两个区间是有序的，接下来我们需要做的就是把那两个区间里的数合并起来，是两个区间合并成一个有序的大区间。

实现方法

第二步比较难理解，但是不难实现，这里我们重点介绍第三步，也就是归并的实现方法。像上面快排一样，我们可以用两个指针a和b，分别指向两个区间的起点，然后新建一个数组arr存放两个区间合并之后的结果，我们比较a和b指向的数，较小的一个数存入arr中，指向较小的数的指针向前移动一格，这样重复操作，直至有一个指针走到了末尾，接下来由于两个区间都是有序的，我们可以直接将另一个指针指向的区间剩余部分直接存入arr中，这样两个有序区间就能合并成一个更大的有序区间。

代码模板

#include <iostream>

void merge_sort(int q[], int l, int r)
{
	if (l >= r) return;
	int mid = l + r >> 1;

    //递归至底端
	merge_sort(q, l, mid);
	merge_sort(q, mid + 1, r);

	int k = 0, i = l, j = mid + 1;
    //对两区间中的数进行比较并合并
	while (i <= mid && j <= r)
	{
		if (q[i] < q[j]) temp[k++] = q[i++];
		else temp[k++] = q[j++];
	}

    //如果一段走到末尾，则将另一段剩下所有数存入temp
	while (i <= mid) temp[k++] = q[i++];
	while (j <= r) temp[k++] = q[j++];

	for (int i = l, j = 0; i <= r; ++i, ++j)
	{
		q[i] = temp[j];
	}
}