比较主流的排序算法以及其对应的一些优化想法，C++语言描述。涵盖了自己对排序算法的思考，代码中附有测试用例。
[TOC]
原理：从左至右，依次比较两个相邻的元素，将值大的元素交换到右边，以此类推；多轮比较，每轮最大的元素都会“冒泡”到最右边。
优化1：设置nSwappedFlag记录上一轮是否发生交换，如果没有则表示提前排序完成，结束排序；
优化2：记录上一轮最后交换的索引LastLoopIndex，表示局部有序的区域不需重复处理。
原理：从头至尾扫描序列，找出最小的一个元素，和(无序区间的)第一个元素交换，接着从剩下的元素中继续这种选择和交换方式，最终得到一个有序序列。
优化1：设置nTargetIndex记录当前轮次比较的最小值的索引，即依次比较但是不做交换，等到当前轮次确定了nTargetIndex的值，再执行swap(arr[ii], arr[nTargetIndex])，避免了许多重复无用的swap。
原理：将一个记录(当前轮次考察值)插入到已经排好序的有序表中，从而一个新的、记录数增1的有序表。
优化1：保存当前这轮循环的考察值arr[ii]，依次比较，用赋值代替交换操作（一次交换有3次赋值）。
原理：将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。常用的是两个有序表合并成一个有序表，称为二路归并。是分治算法的典型应用。
优化1：在merge过程中，比较中间Middle元素和Middle+1元素的大小，如果前者更小，可认为近乎有序，直接开始mergeOperation,避免把merge区间真的分割到2，带来不必要的计算；
优化2：当归并排序的排序片段短到一定长度时，转而用插入排序方法加速，默认长度阈值是16。
原理：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归]进行，以此达到整个数据变成有序序列。
优化1：为避免极端数据提升复杂度，先随机一个锚定值放到第一个元素的位置，然后再开始做partition;
优化2：当快速排序的排序片段短到一定长度时，转而用插入排序方法加速，默认长度阈值是16。
对比的测试数据有3组：一组是随机数；一组是近乎有序的数组；一组是有大量重复元素的数组
添加了经过优化的冒泡排序和选择排序算法
添加了插入排序算法，暂时还未对插入排序进行优化，目前是比选择排序性能要差的
优化了插入排序，目前当前三个测试项的表现，插入排序最优
-
加入了归并排序(暂未优化)，目前第一个nLogN的排序算法。
-
当前最优秀排序算法为归并排序，局限性是排序过程要格外开辟空间
吐槽：(O(N^2))冒泡排序是真的慢，后续考虑不将其加入对比测试了
- 优化了归并排序，速度有明显提升
- 优化点：当发现前后2段已经形成排序，则提前终止；当排序片段短到一定程度，切换成插入排序。
- 添加了优化后的快速排序代码
- 从排序效果上来看，快排比归并排序的优势在于完全随机杂乱的数据排序，劣势在于快排在处理有大量相同元素时会比归并要慢一点。