本篇主要记录了排序算法，对于冒泡、选择、插入排序还是很好理解的，不过归并排序、堆排序、快速排序可能就不那么好理解好实现了。

归并排序

题目要求：使用归并排序算法将一个乱序数组进行排序
首先还是梳理一下归并排序是怎么回事，一句话先分再合，接下来看一个例子吧
mergesortimg
每次从中间分开数组，直到数组个数为1，然后进行合并。显然，这个过程是递归的思想,哈哈，也许这个显然很不容易（因为递归并不是一个好理解的东西）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include <iostream>
#include <vector>
using namespace std;
// 这是一个打印数组所有值的函数
void my_print(vector<int>& v)
{
	for (int i = 0; i < v.size(); ++i)
	{
		cout<<v[i]<<" ";
	}
	cout<<endl;
}
// 这是合并两个有序序列的算法
void MergeArray(vector<int>& v,int low,int mid,int high,vector<int>& temp)
{
	//v是一个数组，temp是一个临时数值
    //第一个有序序列指v[low]-v[mid]
    //第二个有序序列指v[mid+1]-v[high]
	int i=low;
	int j=mid+1;
	int k=0;
    //比较两个序列值的大小，然后将小的放到临时数值temp中
	while(i<=mid && j<=high)
	{
		if(v[i]<v[j])
			temp[k++]=v[i++];
		else
			temp[k++]=v[j++];
	}
	//将剩余的数也拷贝到临时数值temp中
	while(i<=mid)
		temp[k++]=v[i++];
	while(j<=high)
		temp[k++]=v[j++];
	// 将临时数组的值拷贝到原数组中。
	for (i = 0; i < k; i++)
	{
    	// 注意这里是low+i，很容易写成i的。
		v[low+i] = temp[i];
	}
}
int MergeSort(vector<int>& v,int low ,int high,vector<int>& temp)
{
	int mid=low+(high-low)/2;
	if(low<high)
	{
		MergeSort(v,low,mid,temp);
		MergeSort(v,mid+1,high,temp);
		MergeArray(v,low,mid,high,temp);
        // 算法到这其实已经结束，下面的代码其实是为了测试递归过程用的
		my_print(v);
	}
}
//这是测试的主函数
int main()
{
	int a[]={4,3,2,1,9,6,8,7};
	vector<int> v(a,a+sizeof(a)/sizeof(int));
	vector<int> temp(8);
	MergeSort(v,0,7,temp);
	return 0;
}

好了,代码也上了，我们还是来分析一下难搞的递归吧，下面是程序运行的结果。
3 4 9 6 2 1 8 7
3 4 6 9 2 1 8 7
3 4 6 9 2 1 8 7
3 4 6 9 1 2 8 7
3 4 6 9 1 2 7 8
3 4 6 9 1 2 7 8
1 2 3 4 6 7 8 9
其实每一次拆分对应了一次合并，这个递归过程其实就不断的拆分，然后将对应的拆分合并。

堆排序

题目要求：使用堆排序算法将一个乱序数组进行排序。
有如下一位数组，上方的数是数组的下标:

0 1 2 3 4 5 6 7 8 9
3 4 5 1 9 8 6 2 7 10

其实数组可以对应一个二叉树(也就是一个堆)：
heapsortimg1
众所周知，最大堆的堆顶一定是这个堆中最大的,那么算法思路如下：
①将数组调整为最大堆
②将堆顶元素（数组第一个值）和堆底元素（数值的最后一个值）交换（也就是把最大的数放到数组的最后一个位置），同时将数组的长度减1
③重复①②（每次都将当前数组最大值放到当前数组最后的位置），直到数值长度为0
这里列出第一次调整堆（也可以当成构建最大堆）的结果：
heapsortimg2 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include <iostream>
#include <vector>
using namespace std;
//调整堆
void HeapAdjust(vector<int>& array,int s,int length)
{
	int temp = array[s];//待调整的元素
	int child = 2*s+1;//待调整节点的左孩子的位置
	//开始调整
	while(child < length)
	{
		//如果右孩子大于左孩子，找到比当前待调整节点大的孩子节点 
		if(child+1 < length&& array[child] < array[child+1])
			child++;
		//如果较大的孩子大于待调整的节点 
		if(array[s] < array[child])
		{
			array[s] = array[child];//那么较大的节点向上移
			s = child;//更新待调整节点的位置
			child = 2*s+1;//更新待调整节点的左孩子 
		}
		else
			break;
		array[s] = temp;
	}
}
//堆排序
void HeapSort(vector<int>& array,int length)
{
	int i;
	//构造最大堆
	for(i=(length-1)/2;i>=0;i--)
	{
		HeapAdjust(array,i,length);
	}
	//从最后一个元素开始对序列进行调整
	for(i=length-1;i>0;i--)
	{
		//交换堆顶元素和堆中最后一个元素
		int tmp = array[i];
		array[i] = array[0];
		array[0] = tmp;
		//每次交换元素之后，就需要重新调整堆
		HeapAdjust(array,0,i);
	}
}
int main()
{
	int array[]={3,4,5,1,9,8,6,2,7,10};
	vector<int> v(array,array+sizeof(array)/sizeof(int));
	HeapSort(v,10);
	int i;
	for(i=0;i<10;i++)
		cout<<v[i]<<" ";
	cout<<endl;
	return 0;
}

快速排序

快排算法实现步骤：
第一步：选择数组首位为基准点
第二步：设立两个指针，一个用于遍历数组，另一个指针m用于指向比基准点小的值应该放的位置
第三步：遍历完数组后，将首位的基准点和最后m指向的值进行交换，返回m。这样一次快排就完成了
第四步：将m作为分界点，将原数组分成两个。重复第二步、第三步，直到数组大小为1，整个快排就结束了 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <iostream>
#include <vector>
using namespace std;
int Find_pos(vector<int>& v,int low,int high)
{
	//该函数的目的是找到基准点最终应该放在数组中的哪个位置。
	//这里选择数组的首位为基准点
	//比基准点小的值应该放的位置
	int m=low;
	for (int i = low+1; i <= high; ++i)
	{
		if(v[i]<v[low])
		{
			swap(v[++m],v[i]);
		}
	}
	//将基准点放到分界点
	//因为m始终指向比基准点大的值或者基准点本身
	swap(v[m],v[low]);
	return m;
}
void QuickSort(vector<int>& v,int low ,int high)
{
	if(low<high)
	{
		int pos=Find_pos(v,low,high);
		QuickSort(v,low,pos);
		QuickSort(v,pos+1,high);
	}
}
int main()
{
	int array[]={3,4,5,1,9,8,6,2,7,10};
	vector<int> v(array,array+sizeof(array)/sizeof(int));
	QuickSort(v,0,9);
	int i;
	for(i=0;i<10;i++)
		cout<<v[i]<<" ";
	cout<<endl;
	return 0;
}