这次我们介绍三种排序手写方法：Merge Sort、Quickly Sort 、Shell Sort.

本文排序都使用的字符串组。

Merge Sort

Merge Sort 也称为归并排序，算法如下：

归并排序是将两个已经处理好的上升序列整合在一起成为一个新的上升序列。

算法：将两个序列从左到右依次对比比较，分别设定两个序列的头尾指向，对比此时下标两个序列相对应的数字，小的则放入整合序列中，更新下标，若相等，则任意一个放入整合序列中，若其中一个序列已经放完，则按照顺序将另一个序列全部放入整合序列中。

1.基本思路

​ Binary tree calculator也就是使用二叉树实现计算器的功能，相信大家以前都使用栈实现过计算器功的能，使用两个栈分别存数字与字符，一边计算一边“pop”、“push”，或是先将输入的中缀表达式转为后缀表达式，之后运算。而我们的Binary tree calculator则也需要用到栈，先将中缀表达式转为后缀表达式，之后使用指针栈构建Expression tree，再利用二叉树节点之间的关系递推遍历计算即可。

2.中缀表达式转后缀表达式

那么怎么才能将中缀表达式转为后缀表达式呢？我们来看下面一个例子。

​ a+b*(c-d)/e

上述则为一个中缀表达式，它的后缀表达式如下：

​ abcd-*e/+

我们利用栈来实现这个过程：

(1)若遇到数字直接输出。

(2)若遇到字符(‘+’、’-‘、’*’、’/‘),对比栈顶元素的优先级，如果比栈顶元素优先级高，则直接入栈，否则将栈中元素不断出栈，直到出现优先级比存入字符低，则将字符入栈。

(3)若字符为’(‘,则直接入栈，若遇到‘)’，则将‘(’前的元素弹出。

(4)若扫描完成后栈中还有元素滞留，则将栈中元素全部弹出。

1.为什么要用链表

大家在存储多组数据时，会选用数组，但在数组中间删减或是增加数据时，需要将整个数组往前后“平移”。

增加：

1
2
3
4
5
6
7
8

void Add(int value, int index, int size)
{
	for(int i = index, i <= size; i++)
	{
		a[i+1] = a[i];
	}
	a[index] = value;
}

删减：

1
2
3
4
5
6
7

void Delete(int v, int size)
{
	for(int i = index, i <= size; i++)
	{
		a[i] = a[i+1];
	}
}

这样的时间复杂度会很高，也十分麻烦，需要遍历一遍才能完成操作，而链表可以之前在中间插入、删除。