5
归并排序(Merge Sort)
小伙子，你造归并吗？
归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。效率为O(nlogn)，1945年由冯·诺伊曼首次提出。归并排序的实现分为递归实现与非递归(迭代)实现。这里我们讨论递归实现。归并排序依赖于归并操作。归并操作(merge)，也叫归并算法，指的是将两个顺序序列合并成一个顺序序列的方法。
基本原理：
1）申请内存空间A，大小为两个已排序列之和。
2）设定两个指针，分别指向两个已排序列的首元素。
3）比较两个指针指向的元素大小，将小的那个元素丢进内存空间A。同时指向该元素的指针向前移动一位。
4）不断重复步骤3），直到任何一个序列的元素全被丢进空间A。那么就把另外一个序列剩下的所有元素丢进空间A。
Understand？别说了，看图吧。
兄弟，来，干了这段代码。
归并排序是稳定的算法。
6
快速排序(Quick Sort)
1
终于说到这个大boss了。为什么叫快速排序呢？额，这个倒不是因为它很快。
快速排序由C. A. R. Hoare在1962年提出。它的基本思想是：开始选取一个基准数，通过一趟排序将基准数移到序列的合适位置，使得，左边的这部分都小于等于基准数，右边的部分都大于等于基准数，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
那么，对于一个序列，怎样才能使基准数移动到正确位置，以便能使左边的数都小于等于它，右边的数都大于等于它呢？还是以数组A[N]为例，为大家慢慢道来：
1）设置两个变量i、j，排序开始的时候：i=0，j=N；
2）以第一个数组元素作为关键数据，赋值给key，即key=A[0]；
3）从j开始向前搜索，即由后开始向前搜索(j--)，找到第一个小于key的值A[j]，将A[j]和A[i]互换；
4）从i开始向后搜索，即由前开始向后搜索(i++)，找到第一个大于key的A[i]，将A[i]和A[j]互换；
5）重复第3、4步，直到i=j；
6）3,4步中，没找到符合条件的值，即3中A[j]不小于key,4中A[i]不大于key的时候改变j、i的值，使得j=j-1，i=i+1，直至找到为止。找到符合条件的值，进行交换的时候i， j指针位置不变。另外，i==j这一过程一定正好是i+或j-完成的时候，此时令循环结束。
还是来看看图吧：
聪明的同学已经发现了，当序列中的每个元素都归位的时候，整个序列也就都变得有序了。
看完了图解是不是感觉贼得劲儿了呢？？
看代码：
快速排序是不稳定的排序算法。
OK自此，常用的排序算法已经介绍完毕，今天的表演到此结束，谢谢大家。
最后再多说两句
这次内容量有点大啊
小伙伴们要耐下心来多看几遍
不懂就再多看几遍
最后谢谢大家的支持，共勉共进。
祝大家早日练就大佬的姿态
