1. 排序算法介绍

排序也称之为排序算法(Sort Algorithm)，是讲一组数据以指定的顺序进行排列的过程。

1.1 排序分类

内部排序：

• 将所有的数据都加载到内部存储器上进行排序

外部排序：

• 数据量多大，无法全部加载到内存中，需要借助外部存储(文档)进行排序

算法分类图：

2. 算法时间效率

2.1 度量一个程序执行时间的两种方法

事后统计方法： 这种方法可行，但存在两个问题：

1. 要想对设计的算法运行性能进行评测就需要实际去运行该程序，
2. 所得时间统计量依赖于计算机硬件、软件等因素，这种方式要在同一台计算机的相同状态下运行，才能比较出哪一个算法速度更快，更好。

事前估算方法： 通过分析某一个算法的时间复杂度来判断哪个算法更优，更好。

2.2 时间频度

时间频度：一个算法花费的时间与算法中语句的执行次数成正比，哪一个算法中语句执行次数多，那么他所花费的时间就会多。一个算法中语句执行次数称之为语句频度或时间频，记为 T(n)。

计算要点：

• 忽略常数项
• 忽略低次项
• 忽略系数

2.3 时间复杂度

在计算机科学中，时间复杂性，又称时间复杂度，算法的时间复杂度是一个函数，它定性描述该算法的运行时间。这是一个代表算法输入值的字符串的长度的函数。时间复杂度常用大 O 符号表述， 不包括这个函数的低阶项和首项系数。使用这种方式时，时间复杂度可被称为是渐近的，渐近时间复杂度又称之为时间复杂度。

2.4 常见的时间复杂度

1. 常数时间

若对于一个算法的上界与输入大小无关，则称其具有常数时间，记作 O(1) 时间。

2. 对数时间

若算法的 T(n) = O(logn)，则称其具有对数时间。

3. 幂对数时间 对于某个常数 k，若算法的 T(n) = O(logn)，则称其具有幂对数时间。

4. 次线性时间

对于一个算法，若其匹配 T(n) = O(n)，则其时间复杂度为次线性时间(sub-linear time 或 sublinear time)。

5. 线性时间

如果一个算法的时间复杂度为 O(n)，则称这个算法具有线性时间，或 O(n) 时间。

6. 线性对数时间

若一个算法时间复杂度 T(n) = O(nlogn)，则称这个算法具有线性对数时间。

7. 指数时间

若 T(n) 是 2 为上界，起哄 poly(n) 是 n 的多项式，则算法被称为指数时间。

常见的时间复杂度对应图：

2.5 平均和最坏时间复杂度

平均时间复杂度是指所有可能的输入实例以等概率的出现情况下得到算法的运行时间。

最坏时间复杂度，一般讨论的时间复杂度是最坏情况下的时间复杂度，这样做的原因是最坏情况下的时间复杂度是算法在任何输入实例上运行的界限，这就 保证了算法的运行时间不会比最坏情况更长。

平均时间复杂度和最坏时间复杂度是否一样，这就需要根据算法不同而不同了。

常见排序算法复杂度:

3. 基数排序

3.1 介绍

基数排序(radix sort)属于“分配式排序”(distribution sort)，又称“桶子法”(bucket sort) 或 bin sort，顾名思义，它是透过键值的部分资讯，将要排序的 元素分配至某些“桶”中，藉以达到排序的作用，基数排序法是属于稳定性的排序，其时间复杂度为 O(nlog(r)m)。

基数排序是 1887 年赫尔曼、何乐礼发明的。思想是讲整数按位数切割成不同的数字，然后每个位数分别比较。

3.2 思想

讲所有的待比较数值统一设置为同样的数位长度，位数比较短的数前面补零，然后从最低位开始依次进行依次排序，这样从最低位排序一直到最高位排序完成以后，数列 就变成一个有序序列。

3.3 实现思路

1. 先获取原序列的最大位数，即长度(可以从最大值或最大长度考虑)。
2. 定义二维数组，大小为10，表示10个桶，每个桶则是一个数组，长度为原序列的长度，[[],[],[],[],[]...]。
3. 定义一个辅助数组，用于存储第几个桶包含的数据个数。
4. 按个十百千...位数，将数据存放到对应的二维数组的桶中，更新辅助数组对应桶中数字个数。
5. 每一轮中，根据辅助数组去二维数组中寻找数据，将数据存入原序列中，之后将辅助数组清空。

4. 冒泡排序

4.1 介绍

冒泡排序的思想是通过对待排序序列从前往后依次比较相邻元素值，如发现逆序列则交换，使值较大的元素从前逐步往后移动，就像水中气泡。

4.2 示意图

4.3 实现思路

1. 用两层循环
2. 第一层循环轮数，比较轮数等于：原序列长度-1
3. 第二层循环控制每一轮中比较的次数，比较次数等于 原序列长度-1-轮数

5. 快速排序

5.1 介绍

快速排序是对冒泡排序的一种改进。通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另一部分所有的数据都要小， 然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

5.2 示意图

5.3 实现思路

1. 先从序列中取出一个数作为基准数，一般去中间值。
2. 分区过程，将比这个基数大的数全放到它的右边，小于或等于的数全部放到它的左边。
3. 再对左右区间重复第二步，知道各个区间只有一个数

6. 插入排序

6.1 介绍

插入排序属于内部排序，是对于排序的元素以插入的方式寻找该元素的适当位置，已达到排序的目的。

6.2 示意图

6.3 实现思路

1. 2层循环
2. 第一层循环用于取出数据的次数，次数等于：原序列长度-1，for(int i=1;i<arr.length;i++)
3. 第二次循环用于与该数据之前的数据进行比较，次数等于：for(int j=i;j>=1;j--)

7. 选择排序

7.1 介绍

选择排序也属于内部排序法，是从待排序的数据中按指定的规则选择某一个元素，再以规则交换位置后达到的排序目的。

7.2 示意图

7.3 实现思路：

第一次从待排序的数据元素中选出最小(或最大)的一个元素，存放在序列的其实位置，然后再从剩余的未排序元素中寻找到最小(大)元素，然后放到 已排序的序列的末尾。以此类推，知道全部待排序的数据元素的个数为零。选择排序是不稳定的排序方法。

从无序的序列中找到最大或最小值，随着有序的序列变长，无序序列在缩短。

1. 两层循环
2. 第一层循环控制轮数：for(int i=1;i<arr.length;i++)
3. 第二层循环用于无序序列中比较的次数：for(int j=arr.length-1;j>i;j--)

8. 希尔排序

8.1 介绍

希尔排序(Shell's Sort)是插入排序的一种，又称“缩小增量排序”(Diminishing Increment Sort)，是插入排序算法的一种更高效的改进版本。 希尔排序是非稳定排序算法。该方法因 D.L.Shell 于 1959 年提出而得名。

希尔排序是把记录按下标的一定增量分组，对分组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至 1 时。 整个文件恰好被分成一组，算法便终止。

8.2 示意图

8.3 实现思路

1. 3层循环
2. 第一层实现增量变化：for(int gap=arr.length/2;gap>0;gap/2)
3. 第二层实现分组：for(int i=gap;i<arr.length;i++)
4. 第三层实现直接插入排序：for(int j=i-gap;j>0;j-=gap)

9. 归并排序

9.1 介绍

归并排序(Merge Sort)是建立在归并操作上的一种有效，稳定的排序算法，该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。 将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

9.2 示意图

分的阶段：

治的阶段：

9.3 实现思路

1. 递归
2. 求出中间值，左右递归分解
3. 合并元素，定义左右两个指针