1.1、相关概念
稳定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面。
不稳定：如果a原本在b的前面，而a=b，排序之后 a 可能会出现在 b 的后面。
时间复杂度：对排序数据的总的操作次数。反映当n变化时，操作次数呈现什么规律。
空间复杂度：是指算法在计算机内执行时所需存储空间的度量，它也是数据规模n的函数。
1.2、算法分类
1.3、各算法的时间复杂度
1.4、通用函数及其他
2.1、冒泡排序（Bubble Sort）
冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。
2.1.1 算法描述
比较相邻的元素。如果第一个比第二个大，就交换它们两个；
对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数；
针对所有的元素重复以上的步骤，除了最后一个；
重复步骤1~3，直到排序完成。
2.1.2 动图演示
2.2 快速排序
快速排序的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
快速排序是一种不稳定的排序算法，也就是说，多个相同的值的相对位置也许会在算法结束时产生变动
快速排序是C.R.A.Hoare于1962年提出的一种划分交换排序。它采用了一种分治的策略，通常称其为分治法(Divide-and-Conquer Method)。
2.2.1 排法一 ：
该方法的基本思想是：
1．先从数列中取出一个数作为基准数。
2．分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。
3．再对左右区间重复第二步，直到各区间只有一个数。
以一个数组作为示例，取区间第一个数为基准数。
初始时，i = 0; j = 9; X = a[i] = 72
由于已经将a[0]中的数保存到X中，可以理解成在数组a[0]上挖了个坑，可以将其它数据填充到这来。
从j开始向前找一个比X小或等于X的数。当j=8，符合条件，将a[8]挖出再填到上一个坑a[0]中。a[0]=a[8]; i++; 这样一个坑a[0]就被搞定了，但又形成了一个新坑a[8]，这怎么办了？简单，再找数字来填a[8]这个坑。这次从i开始向后找一个大于X的数，当i=3，符合条件，将a[3]挖出再填到上一个坑中a[8]=a[3]; j--;
数组变为：
i = 3; j = 7; X=72
再重复上面的步骤，先从后向前找，再从前向后找。
从j开始向前找，当j=5，符合条件，将a[5]挖出填到上一个坑中，a[3] = a[5]; i++;
从i开始向后找，当i=5时，由于i==j退出。
此时，i = j = 5，而a[5]刚好又是上次挖的坑，因此将X填入a[5]。
数组变为：
可以看出a[5]前面的数字都小于它，a[5]后面的数字都大于它。因此再对a[0…4]和a[6…9]这二个子区间重复上述步骤就可以了。
对挖坑填数进行总结
1．i =L; j = R; 将基准数挖出形成第一个坑a[i]。
2．j--由后向前找比它小的数，找到后挖出此数填前一个坑a[i]中。
3．i++由前向后找比它大的数，找到后也挖出此数填到前一个坑a[j]中。
4．再重复执行2，3二步，直到i==j，将基准数填入a[i]中。
2.2.2 排法二：(原文地址）
这里有一点疑问！假如3那个位置是12呐？
这种排法选择最左边的6作为了基准点，还有一个重要的前提是哨兵j先开始走，j--，直到找到比6小的数字停下来，然后哨兵i开始走，直到找到比6大的数字停下来，i++，所以二者一定会相遇（因为i=j的时候就停下来不走了）；所以假如3的位置是12，哨兵j就会跨过12，和i在4的位置相遇，同样4和6会交换，最终还是左边小于6，右边大于6。
上图中的流程走完之后（也就是i和j相遇后），接着就对6左边的和右边的数分别执行同样的操作。
2.2.3 随机快速排序
1）最坏情况下分析
当输入序列是正序或者是反序的时候，效率最坏，这时效率是Θ(n2)
2) 最优情况下分析
其他情况下的算法效率趋向于Θ（nlgn）
那么我们如何保证我们总是效率处于最优情况下的呢？这就是随机化快速排序需要解决的问题。
3）、随机化快速排序
我们已经知道，若输入本身已被排序，那么对于快排来说就糟了。那么如何避免这样的情况？一种方法时随机排列序列中的元素；另一种方法时随机地选基准。这便是随机化快速排序的思想，这种快排的好处是：其运行时间不依赖于输入序列的顺序。
经分析， 随机化快排的算法效率是Θ(nlgn)。
实现：我们只需在选取主元时加入随机因素即可。其他与快排一样
2.3 插入排序
直接插入排序（straight insertion sort），有时也简称为插入排序（insertion sort），是减治法的一种典型应用。其基本思想如下：
- 对于一个数组A[0,n]的排序问题，假设认为数组在A[0,n-1]排序的问题已经解决了。
- 考虑A[n]的值，从右向左扫描有序数组A[0,n-1]，直到第一个小于等于A[n]的元素，将A[n]插在这个元素的后面。
很显然，基于增量法的思想在解决这个问题上拥有更高的效率。
直接插入排序对于最坏情况（严格递减的数组），需要比较和移位的次数为n(n-1)/2；对于最好的情况（严格递增的数组），需要比较的次数是n-1，需要移位的次数是0。当然，对于最好和最坏的研究其实没有太大的意义，因为实际情况下，一般不会出现如此极端的情况。然而，直接插入排序对于基本有序的数组，会体现出良好的性能，这一特性，也给了它进一步优化的可能性。（希尔排序）。直接插入排序的时间复杂度是O(n^2)，空间复杂度是O(1)，同时也是稳定排序。
2.4 希尔排序（参考文章）
对中等规模的数据表现不错。
首先它把较大的数据集合分割成若干个小组（逻辑上分组），然后对每一个小组分别进行插入排序，此时，插入排序所作用的数据量比较小（每一个小组），插入的效率比较高
可以看出，他是按下标相隔距离为4分的组，也就是说把下标相差4的分到一组，比如这个例子中a[0]与a[4]是一组、a[1]与a[5]是一组...，这里的差值（距离）被称为增量。
每个分组进行插入排序后，各个分组就变成了有序的了（整体不一定有序）
此时，整个数组变的部分有序了（有序程度可能不是很高）
然后缩小增量为上个增量的一半:2，继续划分分组，此时，每个分组元素个数多了，但是，数组变的部分有序了，插入排序效率同样比高。
同理对每个分组进行排序（插入排序），使其每个分组各自有序
最后设置增量为上一个增量的一半：1，则整个数组被分为一组，此时，整个数组已经接近有序了，插入排序效率高
同理，对这仅有的一组数据进行排序，排序完成。
对各个组进行插入排序的时候并不是先对一个组排序完再对另一个组排序。如下图。
2.5 选择排序
选择排序是一种简单直观的排序算法，无论什么数据进去都是 O(n²) 的时间复杂度。所以用到它的时候，数据规模越小越好。唯一的好处可能就是不占用额外的内存空间了吧。
2.5. 1.算法步骤
首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。
再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
重复第二步，直到所有元素均排序完毕。
2.5.2 动图演示
2.6 堆排序
堆是一种特殊的树形数据结构，即完全二叉树。堆分为大根堆和小根堆，大根堆为根节点的值大于两个子节点的值；小根堆为根节点的值小于两个子节点的值，同时根节点的两个子树也分别是一个堆。
# 基本思路
- 步骤一：建立大根堆--将n个元素组成的无序序列构建一个大根堆，
- 步骤二：交换堆元素--交换堆尾元素和堆首元素，使堆尾元素为最大元素；
- 步骤三：重建大根堆--将前n-1个元素组成的无序序列调整为大根堆
重复执行步骤二和步骤三，直到整个序列有序。
# 图示说明
- 步骤一：建立大根堆
① 无序序列建立完全二叉树
② 从最后一个叶子节点开始，从左到右，从下到上调整，将完全二叉树调整为大根堆
a.找到第1个非叶子节点6，由于6的右子节点9比6大，所以交换6和9。交换后，符合大根堆的结构。
c.找到第2个非叶子节点4，由于的4左子节点9比4大，所以交换4和9。交换后不符合大根堆的结构，继续从右到左，从下到上调整。
- 步骤二：交换堆元素（交换堆首和堆尾元素--获得最大元素）
- 步骤三：重建大根堆（前n-1个元素）
- 重复执行步骤二和步骤三，直到整个序列有序
2.7 二路归并排序
二路归并排序主要运用了“分治算法”，分治算法就是将一个大的问题划分为n个规模较小而结构相似的子问题。
这些子问题解决的方法都是类似的，解决掉这些小的问题之后，归并子问题的结果，就得到了“大”问题的解。
二路归并排序主旨是“分解”与“归并”
分解：
1.将一个数组分成两个数组，分别对两个数组进行排序。
2.循环第一步，直到划分出来的“小数组”只包含一个元素，只有一个元素的数组默认为已经排好序。
归并：
1.将两个有序的数组合并到一个大的数组中。
2.从最小的只包含一个元素的数组开始两两合并。此时，合并好的数组也是有序的。
图1. 归并排序过程 图2. 合并两个有序数组
举例说明：
1.图中原始数组为{7,2,5,1,6,9,8,10,3,4}，数组中元素的个数为10个。首先将10个元素的数组二分，每次分解后，
数组中元素的数目为原数组的一半。直到分解为只含有一个元素的数组。
2.将小的数组按序合并，每次合并后数组的大小为上层数组的一倍。此时数组中的元素都是按序排列的。
3.在合并两个有序数组。如图2
下面的是自顶向下递归实现2路归并排序：
2.8 计数排序（原文）
计数排序是一种非比较排序：
利用一个 count 数组，统计每个元素 arr[i] 出现的次数 count[arr[i]]，count 数组的大小代表的是能排序的元素的最大的值；
然后让count数组中每一个元素 count[i] 等于其与他前面一项 count[i-1] 相加，这时候 count[arr[i]] 表示的值就是小于等于 arr[i] 的元素的个数，这时就找到了 arr[i] 在输出数组中的位置；
最后通过反向填充目标数组tmp，将数组元素arr[i] 放在数组tmp的第count[arr[i]]个位置(下标为count[arr[i]]-1)，每放一个元素就将count[arr[i]]递减，可以确保计数排序的稳定性；
看一个例子：
填充过程：
2.9 基数排序
基数排序图文说明
通过基数排序对数组{53, 3, 542, 748, 14, 214, 154, 63, 616}，它的示意图如下：
在上图中，首先将所有待比较树脂统一为统一位数长度，接着从最低位开始，依次进行排序。
1. 按照个位数进行排序。
2. 按照十位数进行排序。
3. 按照百位数进行排序。
排序后，数列就变成了一个有序序列。
从图中可以看出，排十位时，十位相同的情况下，个位也是有序的。