算法学习（二）常用数据结构和算法
1. 常用数据结构
- 数据结构是指相互之间存在着一种或多种关系的数据元素的集合和该集合中数据元素之间的关系组成 。
-
常用的数据结构有：数组，栈，链表，队列，树，图，堆，散列表等，如图所示：
常用数据结构
数据的逻辑结构
1. 1 数组
- 数组是可以再内存中连续存储多个元素的结构，在内存中的分配也是连续的，数组中的元素通过数组下标进行访问，数组下标从0开始。例如下面这段代码就是将数组的第一个元素赋值为 1。
int[] data = new int[100]；data[0] = 1;
- 优点：
1、按照索引查询元素速度快
2、按照索引遍历数组方便
- 缺点：
1、数组的大小固定后就无法扩容了
2、数组只能存储一种类型的数据
3、添加，删除的操作慢，因为要移动其他的元素。
- 适用场景：
频繁查询，对存储空间要求不大，很少增加和删除的情况。
1. 2 字典
- 优点：
- 缺点：
- 适用场景：
1. 3 链表
-
链表是物理存储单元上非连续的、非顺序的存储结构，数据元素的逻辑顺序是通过链表的指针地址实现，每个元素包含两个结点，一个是存储元素的数据域 (内存空间)，另一个是指向下一个结点地址的指针域。根据指针的指向，链表能形成不同的结构，例如单链表，双向链表，循环链表等。
链表
- 优点：
链表是很常用的一种数据结构，不需要初始化容量，可以任意加减元素；
添加或者删除元素时只需要改变前后两个元素结点的指针域指向地址即可，所以添加，删除很快；
- 缺点：
因为含有大量的指针域，占用空间较大；
查找元素需要遍历链表来查找，非常耗时。
- 适用场景：
数据量较小，需要频繁增加，删除操作的场景
1. 4 堆栈
1.4.1 堆
- 堆是一种比较特殊的数据结构，可以被看做一棵树的数组对象，具有以下的性质：
- 堆中某个节点的值总是不大于或不小于其父节点的值；
- 堆总是一棵完全二叉树。
- 将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。常见的堆有二叉堆、斐波那契堆等。
- 堆的定义如下：n个元素的序列{k1,k2,ki,…,kn}当且仅当满足下关系时，称之为堆。
(ki <= k2i,ki <= k2i+1)或者(ki >= k2i,ki >= k2i+1), (i = 1,2,3,4…n/2)，满足前者的表达式的成为小顶堆，满足后者表达式的为大顶堆，这两者的结构图可以用完全二叉树排列出来，示例图如下：
堆
- 因为堆有序的特点，一般用来做数组中的排序，称为堆排序。
- 优点：
- 缺点：
- 适用场景：
1.4.2 栈
-
栈是一种特殊的线性表，仅能在线性表的一端操作，栈顶允许操作，栈底不允许操作。 栈的特点是：先进后出，或者说是后进先出，从栈顶放入元素的操作叫入栈，取出元素叫出栈。
栈
- 栈的结构就像一个集装箱，越先放进去的东西越晚才能拿出来，所以，栈常应用于实现递归功能方面的场景，例如斐波那契数列。
- 优点：
- 缺点：
- 适用场景：
1.4.2.1 栈的定义和基本运算
- 什么是栈：
栈是只能通过访问它的一端来实现数据存储和检索的一种线性数据结构。换句话说，栈的修改是按先进后出的原则进行的。因此，栈又称为先进后出（FILO）的线性表。在栈中进行插入和删除操作的一端称为栈顶（top），相应地，另一端称为栈底（bottom）。不含数据元素的栈称为空栈。
- 栈的基本运算
- 初始化栈InitStack(S):创建一个空栈S。
- 判断空栈StackEmpty（S）：当栈为空栈时返回“真”，否则返回“假”。
- 入栈Push（S，x）：将元素x加入栈顶，并更新栈顶指针。
- 出栈Pop（S）：将栈顶的元素从栈中删除，并且更新栈顶指针。
- 读栈顶元素Top（S）：返回栈顶元素的值，但不修改栈顶的指针。
1.4.2.2 栈的存储结构
- 栈的顺序存储
栈的顺序存储是指用一组地址连续的存储单元依次存储自栈顶到栈底的数据元素，同时附设指针top指示栈顶元素的位置。采用顺序存储结构的栈也称为顺序栈。在顺序存储方式下，需要预先定义或申请栈的存储空间，也就是说栈空间的容量是有限的。因此在顺序栈中，当一个元素入栈时，需要判断是否栈满（即栈空间中没有空闲单元），若栈满，则元素入栈会发生上溢现象。
- 栈的链式存储
栈的链式存储是为了克服顺序存储的栈可以存在上溢的不足，可以用链表存储栈中的元素。用链表作为存储结构的栈也称为链栈。由于栈中元素的插入和删除仅在栈顶一端进行，因此不必另外设置头指针，链表的头指针就是栈顶指针。
栈的链式存储
1.4.2.3 栈的应用
- 栈的典型应用包括表达式求值，括号匹配等。在计算机语言的实现以及将递归过程转变为非递归过程的处理中，栈有重要的作用。
- 栈的实例1423：
- 表达式求值
计算机在处理算术表达式时，可将表达式先转换为后缀形式，然后利用栈进行计算。例如，表达式“46+5 （120-37）”的后缀表达式为“46 5 120 37 - * +”。计算后缀表达式时，从左至右扫描表达式：若遇到运算对象，则压入栈中；遇到运算符，则从栈顶弹出运算对象进行计算，并将运算结果压入栈中。重复以上过程，直到后缀表达式扫描结束。例如“46 5 120 37 - * +”的计算过程为：
1、依次将46，5，120，37压入栈中；
2、遇到“-”取37，120，计算120-37，得83，将其压入栈中；
3、遇到“”取出83，5，计算83*5，得415，将其压入栈中；
4、遇到“+”，取出415，46，计算46+415，得461，将其压入栈中；
5、表达式结束，计算过程完成。
下面函数computing(char expr[],int result)的功能是基于栈计算后缀形式的表达式（以串形式存入字符数组expr）的值，并通过参数result带回该值。函数的返回值为-1/0，分别表示表达时有/无错误。假设表达式中仅包含数字,空格和算术运算符号，其中所有项均以空格分隔，且运算符仅包含（“+”）,（“-”）,（“”）,（“\”）。
void InitStack(STACK *s):初始化栈。
void Push(STACK *s, int e):将一个整数压入栈，栈中元素数目增加1。
void Pop(STACK *s);栈顶元素出栈，栈中元素数目减1。
int Top(STACK s):返回非空栈的栈顶元素值,栈中元素不变。
int IsEmpty(STACK s);若s是空 栈,则返回1；否则返回0。
实例1423实现代码：
int computing (char expr[], int * result)
{
STACK s; int tnum,a,b; char *ptr;
InitStack(&s);
ptr = expr; /*字符指针指向后缀表达式串的第一个字符*/
while (*ptr != '\0')
{
if ( *ptr == ' ') /*当前字符是空格，则取下一个字符*/
{
ptr++;
continue;
}
else if ( isdigit(*ptr)) /*当前字符是数字,则将数字串转化为数值*/
{
tmun = 0;
while(*ptr >= '0' && *ptr <= '9')
{
tnum = tnum *10 + *ptr - '0';
ptr++;
}
Push(&s,tnum);
}
else if ( *ptr == '+' || *ptr == '-' || *ptr == '*' || *ptr == '/') /*当前是运算符*/
{
if ( !IsEmpty(s)){
a = Top(s);Pop(&s); /*取运算符的第二个运算符，存入a*/
if ( IsEmpty(s)) {
b = Top(s); Pop(&s); /*取运算符的第一个运算符，存入b*/
}
else
{
return -1;
}
}
else
{
retun -1; /*栈空*/
}
switch ( *ptr) {
case '+' : Push(&s,b+a);break;
case '-': Push(&s,b-a);break;
case '*': Push(&s,b*a);break;
case '/': Push(&s,b/a);break;
}
}
else /*非法字符*/
{
return -1;
}
ptr++;
}/*while*/
if (IsEmpty(s))
return -1;
else
{
*result = Top(s);Pop(&s); /*得到运算结果*/
if (!IsEmpty(s)
return -1;
retrun 0;
}
}
1.5 队列
- 队列与栈一样，也是一种线性表，不同的是，队列可以在一端添加元素，在另一端取出元素，也就是：先进先出。从一端放入元素的操作称为入队，取出元素为出队，示例图如下：
顺序队列
- 使用场景：因为队列先进先出的特点，在多线程阻塞队列管理中非常适用
1.5.1 优先队列
- 优点：
- 缺点：
- 适用场景：
1.5.2 循环队列
- 优点：
- 缺点：
- 适用场景：
1.6 树
- 树是一种数据结构，它是由n（n>=1）个有限节点组成一个具有层次关系的集合。把它叫做 “树” 是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。它具有以下的特点：
- 每个节点有零个或多个子节点；
- 没有父节点的节点称为根节点；
- 每一个非根节点有且只有一个父节点；
- 除了根节点外，每个子节点可以分为多个不相交的子树；
1.6.1 二叉树
- 二叉树是树的特殊一种，具有如下特点：
1、每个结点最多有两颗子树，结点的度最大为2。
2、左子树和右子树是有顺序的，次序不能颠倒。
3、即使某结点只有一个子树，也要区分左右子树。
- 二叉树是一种比较有用的折中方案，它添加，删除元素都很快，并且在查找方面也有很多的算法优化，所以，二叉树既有链表的好处，也有数组的好处，是两者的优化方案，在处理大批量的动态数据方面非常有用。
- 二叉树有很多扩展的数据结构，包括平衡二叉树、红黑树、B+树等，这些数据结构二叉树的基础上衍生了很多的功能，在实际应用中广泛用到，例如mysql的数据库索引结构用的就是B+树，还有HashMap的底层源码中用到了红黑树。
- 优点：
二叉树既有链表的好处，也有数组的好处，是两者的优化方案
- 缺点：
- 适用场景：
在处理大批量的动态数据方面非常有用。
更多二叉树相关知识请参考这篇博客：二叉树总结创建，遍历
1.6.2 二叉搜索树
- 优点：
- 缺点：
- 适用场景：
1.6.3 平衡二叉树
- 优点：
- 缺点：
- 适用场景：
1.7 图
- 图是由结点的有穷集合V和边的集合E组成。其中，为了与树形结构加以区别，在图结构中常常将结点称为顶点，边是顶点的有序偶对，若两个顶点之间存在一条边，就表示这两个顶点具有相邻关系。
- 按照顶点指向的方向可分为无向图和有向图：
无向图
有向图
- 图是一种比较复杂的数据结构，在存储数据上有着比较复杂和高效的算法，分别有邻接矩阵 、邻接表、十字链表、邻接多重表、边集数组等存储结构。
- 优点：
- 缺点：
- 适用场景：
更多图相关知识可以参考这篇文章：数据结构—图
1.8 散列表
-
散列表，也叫哈希表，是根据关键码和值 (key和value) 直接进行访问的数据结构，通过key和value来映射到集合中的一个位置，这样就可以很快找到集合中的对应元素。
-
记录的存储位置=f(key)
-
这里的对应关系 f 成为散列函数，又称为哈希 (hash函数)，而散列表就是把Key通过一个固定的算法函数既所谓的哈希函数转换成一个整型数字，然后就将该数字对数组长度进行取余，取余结果就当作数组的下标，将value存储在以该数字为下标的数组空间里，这种存储空间可以充分利用数组的查找优势来查找元素，所以查找的速度很快。
-
哈希表在应用中也是比较常见的，就如Java中有些集合类就是借鉴了哈希原理构造的，例如HashMap，HashTable等，利用hash表的优势，对于集合的查找元素时非常方便的，然而，因为哈希表是基于数组衍生的数据结构，在添加删除元素方面是比较慢的，所以很多时候需要用到一种数组链表来做，也就是拉链法。拉链法是数组结合链表的一种结构，较早前的hashMap底层的存储就是采用这种结构，直到jdk1.8之后才换成了数组加红黑树的结构，其示例图如下：
散列表
-
从图中可以看出，左边很明显是个数组，数组的每个成员包括一个指针，指向一个链表的头，当然这个链表可能为空，也可能元素很多。我们根据元素的一些特征把元素分配到不同的链表中去，也是根据这些特征，找到正确的链表，再从链表中找出这个元素。
-
哈希表的应用场景很多，当然也有很多问题要考虑，比如哈希冲突的问题，如果处理的不好会浪费大量的时间，导致应用崩溃。
- 优点：
- 缺点：
- 适用场景：
更多散列表相关知识参考这篇博客：数据结构—散列表
2. 常用算法
2.1 查找算法
2.1.1 二分查找
2.1.2 广度优先搜索算法
2.1.3 深度优先搜索算法
2.2 排序算法
- 相关术语解释
| 术语 | 含义 |
|---|---|
| 稳定 | 如果a原本在b前面，而a=b，排序之后a仍然在b的前面； |
| 不稳定 | 如果a原本在b的前面，而a=b，排序之后a可能会出现在b的后面； |
| 内排序 | 所有排序操作都在内存中完成； |
| 外排序 | 由于数据太大，因此把数据放在磁盘中，而排序通过磁盘和内存的数据传输才能进行； |
| 时间复杂度 | 一个算法执行所耗费的时间。 |
| 空间复杂度 | 运行完一个程序所需内存的大小。 |
2.2.1 排序算法简介
排序算法分类
- 排序算法可以说是一项基本功，解决实际问题中经常遇到，针对实际数据的特点选择合适的排序算法可以使程序获得更高的效率，有时候排序的稳定性还是实际问题中必须考虑的，这篇博客对常见的排序算法进行整理，包括：插入排序、选择排序、冒泡排序、快速排序、堆排序、归并排序、希尔排序、二叉树排序、计数排序、桶排序、基数排序。
- 按大的方向区分分为：比较排序和非比较排序。
- 常见的排序算法都是比较排序，非比较排序包括计数排序、桶排序和基数排序，非比较排序对数据有要求，因为数据本身包含了定位特征，所有才能不通过比较来确定元素的位置。
- 比较排序的时间复杂度通常为O(n2)或者O(nlogn)，比较排序的时间复杂度下界就是O(nlogn)，而非比较排序的时间复杂度可以达到O(n)，但是都需要额外的空间开销。
- 比较排序时间复杂度为O(nlogn)的证明：
a1,a2,a3……an序列的所有排序有n!种，所以满足要求的排序a1',a2',a3'……an'（其中a1'<=a2'<=a3'……<=an'）的概率为1/n!。基于输入元素的比较排序，每一次比较的返回不是0就是1，这恰好可以作为决策树的一个决策将一个事件分成两个分支。比如冒泡排序时通过比较a1和a2两个数的大小可以把序列分成a1,a2……an与a2,a1……an（气泡a2上升一个身位）两种不同的结果，因此比较排序也可以构造决策树。根节点代表原始序列a1,a2,a3……an，所有叶子节点都是这个序列的重排（共有n!个，其中有一个就是我们排序的结果a1',a2',a3'……an'）。如果每次比较的结果都是等概率的话（恰好划分为概率空间相等的两个事件），那么二叉树就是高度平衡的，深度至少是log(n!)。
又因为 1. n! < nn ,两边取对数就得到log(n!)<nlog(n)，所以log(n!) = O(nlogn).
2. n!=n(n-1)(n-2)(n-3)…1 > (n/2)^(n/2) 两边取对数得到 log(n!) > (n/2)log(n/2) = Ω(nlogn)，所以 log(n!) = Ω(nlogn)。
因此log(n!)的增长速度与 nlogn 相同,即 log(n!)=Θ(nlogn)，这就是通用排序算法的最低时间复杂度O(nlogn)的依据。
2.2.2 排序算法比较
2.2.2.1 稳定性比较
-
插入排序、冒泡排序、二叉树排序、二路归并排序及其他线形排序是稳定的；
-
选择排序、希尔排序、快速排序、堆排序是不稳定的。
2.2.2.2 时间复杂度比较
| 对比项 | 平均情况 | 最好情况 | 最坏情况 | 是否稳定 | 空间 |
|---|---|---|---|---|---|
| 基数排序 | O(n) | O(n) | O(n) | 不稳定 | 需要 O(n) 额外存储空间 |
| 快速排序 | O(nlogn) | O(nlogn) | O(n2) | 不稳定 | |
| 希尔排序 | O(n1.5) | O(n) | O(n1.5) | 不稳定 | |
| 选择排序 | O(n2) | O(n2) | O(n2) | 不稳定 | |
| 堆排序 | O(nlogn) | O(nlogn)) | O(nlogn) | 不稳定 | |
| 插入排序 | O(n2) | O(n) | O(n2) | 稳定 | |
| 归并排序 | O(nlogn) | O(nlogn) | O(nlogn) | 稳定 | 需要 O(n) 额外存储空间 |
| 冒泡排序 | O(n2) | O(n2) | O(n2) | 稳定 | |
| 二叉树排序 | O(nlogn) | O(nlogn) | O(nlogn) | 稳定 | |
| 计数排序 | O(n+k) | O(n+k) | O(n+k) | 稳定 | 需要 O(n+k) 额外存储空间，k为序列中Max-Min+1 |
| 桶排序 | O(n) | O(n) | O(n) | 需要 O(k) 额外存储空间 |
2.2.2.3 辅助空间比较
- 线形排序、二路归并排序的辅助空间为O(n),其它排序的辅助空间为O(1)
2.2.2.4 其他比较
-
插入、冒泡排序的速度较慢，但参加排序的序列局部或整体有序时，这种排序能达到较快的速度。
-
反而在这种情况下，快速排序反而慢了。
-
当n较小时，对稳定性不作要求时宜用选择排序，对稳定性有要求时宜用插入或冒泡排序。
-
若待排序的记录的关键字在一个明显有限范围内时,且空间允许是用桶排序。
-
当n较大时，关键字元素比较随机，对稳定性没要求宜用快速排序。
-
当n较大时，关键字元素可能出现本身是有序的，对稳定性有要求时，空间允许的情况下。宜用归并排序。
-
当n较大时，关键字元素可能出现本身是有序的，对稳定性没有要求时宜用堆排序。
2.2.3 排序算法实现
2.2.3.1 插入排序
算法简介
- 插入排序（Insertion Sort）
插入排序（Insertion-Sort）的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。
- 算法描述
一般来说，插入排序都采用in-place在数组上实现。具体算法描述如下：
- 从第一个元素开始，该元素可以认为已经被排序；
- 取出下一个元素，在已经排序的元素序列中从后向前扫描；
- 如果该元素（已排序）大于新元素，将该元素移到下一位置；
重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；- 将新元素插入到该位置后；
- 重复步骤2~5。
- 动态图演示过程
插入排序
- 时间复杂度：最佳情况：T(n) = O(n) 最坏情况：T(n) = O(n2) 平均情况：T(n) = O(n2)
算法实现
- 数列前面部分看为有序，依次将后面的无序数列元素插入到前面的有序数列中，初始状态有序数列仅有一个元素，即首元素。在将无序数列元素插入有序数列的过程中，采用了逆序遍历有序数列，相较于顺序遍历会稍显繁琐，但当数列本身已近排序状态效率会更高。
- 时间复杂度：O(N2) 稳定性：稳定
- 遍历数组，遍历到i时，a0,a1...ai-1是已经排好序的，取出ai，从ai-1开始向前和每个比较大小，如果小于，则将此位置元素向后移动，继续先前比较，如果不小于，则放到正在比较的元素之后。可见相等元素比较是，原来靠后的还是拍在后边，所以插入排序是稳定的。
- 当待排序的数据基本有序时，插入排序的效率比较高，只需要进行很少的数据移动。
- C语言实现代码：
void insertion_sort (int a[], int n) {
int i,j,v;
for (i=1; i<n; i++) { //如果第i个元素小于第j个，则第j个向后移动
for (v=a[i], j=i-1; j>=0&&v<a[j]; j--)
a[j+1]=a[j];
a[j+1]=v;
}
}
- C++实现代码：
/*插入排序*/
void insertSort(vector<int> &arr, int bgn, int end)
{
for (int i = bgn + 1; i < end; ++i)
{
/*
* 分为1,2两部分处理，可以囊括j = beg - 1时的情况
* 即需要将arr[i]插入到首元素前的位置，若使用一个for
* 包括这两部分，则会在发生这种情况时退出
*/
/*1*/
int j = i - 1;
for ( ; j >= bgn; --j)
if (arr[j] <= arr[I])
break;
/*2*/
if (j != i - 1)
{
int temp = arr[i];
for (int k = i; k > j + 1; --k)
{
arr[k] = arr[k - 1];
}
arr[j + 1] = temp;
}
}
}
2.2.3.2 选择排序
算法简介
- 选择排序（Selection Sort）
表现最稳定的排序算法之一，因为无论什么数据进去都是O(n2)的时间复杂度，所以用到它的时候，数据规模越小越好。唯一的好处可能就是不占用额外的内存空间了吧。理论上讲，选择排序可能也是平时排序一般人想到的最多的排序方法了吧。
选择排序(Selection-sort)是一种简单直观的排序算法。它的工作原理：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
- 算法描述
n个记录的直接选择排序可经过n-1趟直接选择排序得到有序结果。具体算法描述如下：
- 初始状态：无序区为R[1..n]，有序区为空；
- 第i趟排序(i=1,2,3…n-1)开始时，当前有序区和无序区分别为R[1..i-1]和R(i..n）。该趟排序从当前无序区中-选出关键字最小的记录 R[k]，将它与无序区的第1个记录R交换，使R[1..i]和R[i+1..n)分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区；
- n-1趟结束，数组有序化了。
-
动态图演示过程
选择排序
-
时间复杂度：最佳情况：T(n) = O(n2) 最差情况：T(n) = O(n2) 平均情况：T(n) = O(n2)
算法实现
- 首先初始化最小元素索引值为首元素，依次遍历待排序数列，若遇到小于该最小索引位置处的元素则刷新最小索引为该较小元素的位置，直至遇到尾元素，结束一次遍历，并将最小索引处元素与首元素交换；然后，初始化最小索引值为第二个待排序数列元素位置，同样的操作，可得到数列第二个元素即为次小元素；以此类推。
- 时间复杂度：O(N2) 稳定性：不稳定
- 遍历数组，遍历到i时，a0,a1...ai-1是已经排好序的，然后从i到n选择出最小的，记录下位置，如果不是第i个，则和第i个元素交换。此时第i个元素可能会排到相等元素之后，造成排序的不稳定。
- C语言实现代码：
void selection_sort (int a[], int n) {
int i,j,pos,tmp;
for (i=0; i<n-1; i++) { //寻找最小值的下标
for (pos=i, j=i+1; j<n; j++)
if (a[pos]>a[j])
pos=j;
if (pos != i) {
tmp=a[I];
a[i]=a[pos];
a[pos]=tmp;
}
}
}
2.2.3.3 冒泡排序
算法简介
- 冒泡排序（Bubble Sort）
冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。
- 算法描述
- 比较相邻的元素。如果第一个比第二个大，就交换它们两个；
- 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数；
- 针对所有的元素重复以上的步骤，除了最后一个；
- 重复步骤1~3，直到排序完成。
-
动态图演示过程
冒泡排序
- 最佳情况：T(n) = O(n) 最差情况：T(n) = O(n2) 平均情况：T(n) = O(n2)
算法实现
- 依次比较相邻两元素，若前一元素大于后一元素则交换之，直至最后一个元素即为最大；然后重新从首元素开始重复同样的操作，直至倒数第二个元素即为次大元素；依次类推。如同水中的气泡，依次将最大或最小元素气泡浮出水面。
- 时间复杂度：O(N2) 稳定性：稳定
- 冒泡排序的名字很形象，实际实现是相邻两节点进行比较，大的向后移一个，经过第一轮两两比较和移动，最大的元素移动到了最后，第二轮次大的位于倒数第二个，依次进行。这是最基本的冒泡排序，还可以进行一些优化。
- 优化一：如果某一轮两两比较中没有任何元素交换，这说明已经都排好序了，算法结束，可以使用一个Flag做标记，默认为false，如果发生交互则置为true，每轮结束时检测Flag，如果为true则继续，如果为false则返回。
- 优化二：某一轮结束位置为j，但是这一轮的最后一次交换发生在lastSwap的位置，则lastSwap到j之间是排好序的，下一轮的结束点就不必是j--了，而直接到lastSwap即可，代
- C语言实现代码：
void bubble_sort (int a[], int n) {
int i, j, lastSwap, tmp;
for (j=n-1; j>0; j=lastSwap) { lastSwap=0; //每一轮要初始化为0，防止某一轮未发生交换，lastSwap保留上一轮的值进入死循环
for (i=0; i<j; i++) {
if (a[i] > a[i+1]) {
tmp=a[I];
a[i]=a[i+1];
a[i+1]=tmp;
//最后一次交换位置的坐标
lastSwap = I;
}
}
}
}
2.2.3.4 快速排序
算法简介
- 快速排序（Quick Sort）
快速排序的基本思想：通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。
- 算法描述
快速排序使用分治法来把一个串（list）分为两个子串（sub-lists）。
具体算法描述如下：
- 从数列中挑出一个元素，称为 “基准”（pivot）；
- 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
- 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。
- 动态图演示过程
快速排序
- 时间复杂度：最佳情况：T(n) = O(nlogn) 最差情况：T(n) = O(n2) 平均情况：T(n) = O(nlogn)
算法实现
-
类似于选择排序的定位思想）选一基准元素，依次将剩余元素中小于该基准元素的值放置其左侧，大于等于该基准元素的值放置其右侧；然后，取基准元素的前半部分和后半部分分别进行同样的处理；以此类推，直至各子序列剩余一个元素时，即排序完成（类比二叉树的思想，from up to down）.
-
时间复杂度：O(NlogN) 稳定性：不稳定
-
快速排序首先找到一个基准，下面程序以第一个元素作为基准（pivot），然后先从右向左搜索，如果发现比pivot小，则和pivot交换，然后从左向右搜索，如果发现比pivot大，则和pivot交换，一直到左边大于右边，此时pivot左边的都比它小，而右边的都比它大，此时pivot的位置就是排好序后应该在的位置，此时pivot将数组划分为左右两部分，可以递归采用该方法进行。快排的交换使排序成为不稳定的。
-
C语言实现代码：
int mpartition(int a[], int l, int r) {
int pivot = a[l];
while (l<r) {
while (l<r && pivot<=a[r]) r--;
if (l<r) a[l++]=a[r];
while (l<r && pivot>a[l]) l++;
if (l<r) a[r--]=a[l];
}
a[l]=pivot;
return l;
}
void quick_sort (int a[], int l, int r) {
if (l < r) {
int q = mpartition(a, l, r);
msort(a, l, q-1);
msort(a, q+1, r);
}
}
C++ 实现代码：
/*快排*/
void quickSort(vector<int> &arr, int bgn, int end) //arr must be the reference of real param
{
//数组arr空or仅有一个元素则退出
if (bgn >= end - 1)
return;
int lindex = bgn;
int rindex = end - 1;
int std = arr[lindex];
while (lindex < rindex)
{
while (lindex < rindex)
{
if (arr[rindex] < std)
{
arr[lindex++] = arr[rindex];
break;
}
--rindex;
}
while (lindex < rindex)
{
if (arr[lindex] >= std)
{
arr[rindex--] = arr[lindex];
break;
}
++lindex;
}
}
arr[lindex] = std;
quickSort(arr, bgn, lindex);
quickSort(arr, rindex + 1, end);
}
2.2.3.5 堆排序
算法简介
- 堆排序（Heap Sort）
堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。
- 算法描述
- 将初始待排序关键字序列(R1,R2….Rn)构建成大顶堆，此堆为初始的无序区；
- 将堆顶元素R[1]与最后一个元素R[n]交换，此时得到新的无序区(R1,R2,……Rn-1)和新的有序区(Rn),且满足R[1,2…n-1]<=R[n]；
- 由于交换后新的堆顶R[1]可能违反堆的性质，因此需要对当前无序区(R1,R2,……Rn-1)调整为新堆，
- 然后再次将R[1]与无序区最后一个元素交换，得到新的无序区(R1,R2….Rn-2)和新的有序区(Rn-1,Rn)。
- 不断重复此过程直到有序区的元素个数为n-1，则整个排序过程完成。
- 动态图演示过程
堆排序-过程1
堆排序-过程2
- 时间复杂度：最佳情况：T(n) = O(nlogn) 最差情况：T(n) = O(nlogn) 平均情况：T(n) = O(nlogn)
算法实现
- 堆排序的思想借助于二叉堆中的最大堆得以实现。首先，将待排序数列抽象为二叉树，并构造出最大堆；然后，依次将最大元素（即根节点元素）与待排序数列的最后一个元素交换（即二叉树最深层最右边的叶子结点元素）；每次遍历，刷新最后一个元素的位置（自减1），直至其与首元素相交，即完成排序。
- 堆排序是把数组看作堆，第i个结点的孩子结点为第2i+1和2i+2个结点（不超出数组长度前提下），堆排序的第一步是建堆，然后是取堆顶元素然后调整堆。建堆的过程是自底向上不断调整达成的，这样当调整某个结点时，其左节点和右结点已经是满足条件的，此时如果两个子结点不需要动，则整个子树不需要动，如果调整，则父结点交换到子结点位置，再以此结点继续调整。
- 下述代码使用的大顶堆，建立好堆后堆顶元素为最大值，此时取堆顶元素即使堆顶元素和最后一个元素交换，最大的元素处于数组最后，此时调整小了一个长度的堆，然后再取堆顶和倒数第二个元素交换，依次类推，完成数据的非递减排序。
- 堆排序的主要时间花在初始建堆期间，建好堆后，堆这种数据结构以及它奇妙的特征，使得找到数列中最大的数字这样的操作只需要O(1)的时间复杂度，维护需要logn的时间复杂度。堆排序不适宜于记录数较少的文件.
- C语言实现代码：
void heapAdjust(int a[], int i, int nLength)
{
int nChild;
int nTemp;
for (nTemp = a[i]; 2 * i + 1 < nLength; i = nChild)
{
// 子结点的位置=2*（父结点位置）+ 1
nChild = 2 * i + 1;
// 得到子结点中较大的结点
if ( nChild < nLength-1 && a[nChild + 1] > a[nChild])
++nChild;
// 如果较大的子结点大于父结点那么把较大的子结点往上移动，替换它的父结点
if (nTemp < a[nChild])
{
a[i] = a[nChild];
a[nChild]= nTemp;
}
else
// 否则退出循环
break;
}
}
// 堆排序算法
void heap_sort(int a[],int length)
{
int tmp;
// 调整序列的前半部分元素，调整完之后第一个元素是序列的最大的元素
//length/2-1是第一个非叶节点，此处"/"为整除
for (int i = length / 2 - 1; i >= 0; --i)
heapAdjust(a, i, length);
// 从最后一个元素开始对序列进行调整，不断的缩小调整的范围直到第一个元素
for (int i = length - 1; i > 0; --i)
{
// 把第一个元素和当前的最后一个元素交换，
// 保证当前的最后一个位置的元素都是在现在的这个序列之中最大的
/// Swap(&a[0], &a[I]);
tmp = a[I];
a[i] = a[0];
a[0] = tmp;
// 不断缩小调整heap的范围，每一次调整完毕保证第一个元素是当前序列的最大值
heapAdjust(a, 0, i);
}
}
2.2.3.6 归并排序
算法简介
- 归并排序（Merge Sort）
和选择排序一样，归并排序的性能不受输入数据的影响，但表现比选择排序好的多，因为始终都是O(n log n）的时间复杂度。代价是需要额外的内存空间。
归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。归并排序是一种稳定的排序方法。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。
- 算法描述
- 把长度为n的输入序列分成两个长度为n/2的子序列；
- 对这两个子序列分别采用归并排序；
- 将两个排序好的子序列合并成一个最终的排序序列。
-
动态图演示过程
归并排序
- 时间复杂度：最佳情况：T(n) = O(n) 最差情况：T(n) = O(nlogn) 平均情况：T(n) = O(nlogn)
算法实现
- 归并排序是采用分治法（Divide and Conquer）的一个非常典型的应用。首先考虑下如何将将二个有序数列合并。这个非常简单，只要从比较二个数列的第一个数，谁小就先取谁，取了后就在对应数列中删除这个数。然后再进行比较，如果有数列为空，那直接将另一个数列的数据依次取出即可。这需要将待排序序列中的所有记录扫描一遍，因此耗费O(n)时间，而由完全二叉树的深度可知，整个归并排序需要进行.logn.次，因此，总的时间复杂度为O(nlogn)。
- 归并排序在归并过程中需 要与原始记录序列同样数量的存储空间存放归并结果，因此空间复杂度为O(n)。
- 归并算法需要两两比较，不存在跳跃，因此归并排序是一种稳定的排序算法。
- 有的地方看到在mergearray()合并有序数列时分配临时数组，即每一步mergearray的结果存放的一个新的临时数组里，这样会在递归中消耗大量的空间。因此做出小小的变化。只需要new一个临时数组。后面的操作都共用这一个临时数组。合并完后将临时数组中排好序的部分写回原数组。
- 归并排序计算时间复杂度时可以很容易的列出递归方程，也是计算时间复杂度的一种方法。
- C语言实现代码：
void mergearray(int a[], int first, int mid, int last, int temp[])
{
int i = first, j = mid + 1;
int m = mid, n = last;
int k = 0;
while (i <= m && j <= n)
{
if (a[i] <= a[j])
temp[k++] = a[i++];
else
temp[k++] = a[j++];
}
while (i <= m)
temp[k++] = a[i++];
while (j <= n)
temp[k++] = a[j++];
for (i = 0; i < k; I++)
a[first + i] = temp[I];
}
void merge_sort(int a[], int first, int last, int temp[])
{
if (first < last)
{
int mid = (first + last) / 2;
merge_sort(a, first, mid, temp); //左边有序
merge_sort(a, mid + 1, last, temp); //右边有序
mergearray(a, first, mid, last, temp); //再将二个有序数列合并
}
}
2.2.3.7 希尔排序
算法简介
- 希尔排序（Shell Sort）
希尔排序是希尔（Donald Shell）于1959年提出的一种排序算法。希尔排序也是一种插入排序，它是简单插入排序经过改进之后的一个更高效的版本，也称为缩小增量排序，同时该算法是冲破O(n2）的第一批算法之一。它与插入排序的不同之处在于，它会优先比较距离较远的元素。希尔排序又叫缩小增量排序。
希尔排序是把记录按下表的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。
- 算法描述
- 我们来看下希尔排序的基本步骤，在此我们选择增量gap=length/2，缩小增量继续以gap = gap/2的方式，这种增量选择我们可以用一个序列来表示，{n/2,(n/2)/2...1}，称为增量序列。希尔排序的增量序列的选择与证明是个数学难题，我们选择的这个增量序列是比较常用的，也是希尔建议的增量，称为希尔增量，但其实这个增量序列不是最优的。此处我们做示例使用希尔增量。
- 先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，
具体算法描述：- 选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1；
- 按增量序列个数k，对序列进行k 趟排序；
- 每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。
-
动态图演示过程
希尔排序
- 时间复杂度：最佳情况：T(n) = O(nlog2 n) 最坏情况：T(n) = O(nlog2 n) 平均情况：T(n) =O(nlog2n)
算法实现
- 希尔排序是插入排序的改进版。为了减少数据的移动次数，在初始序列较大时取较大的步长，通常取序列长度的一半，此时只有两个元素比较，交换一次；之后步长依次减半直至步长为1，即为插入排序，由于此时序列已接近有序，故插入元素时数据移动的次数会相对较少，效率得到了提高。
- 时间复杂度：通常认为是O(N3/2) ，稳定性：不稳定
- 希尔排序是对插入排序的优化，基于以下两个认识：1. 数据量较小时插入排序速度较快，因为n和n2差距很小；2. 数据基本有序时插入排序效率很高，因为比较和移动的数据量少。
- 因此，希尔排序的基本思想是将需要排序的序列划分成为若干个较小的子序列，对子序列进行插入排序，通过则插入排序能够使得原来序列成为基本有序。这样通过对较小的序列进行插入排序，然后对基本有序的数列进行插入排序，能够提高插入排序算法的效率。
- 希尔排序的划分子序列不是像归并排序那种的二分，而是采用的叫做增量的技术，例如有十个元素的数组进行希尔排序，首先选择增量为10/2=5，此时第1个元素和第（1+5）个元素配对成子序列使用插入排序进行排序，第2和（2+5）个元素组成子序列，完成后增量继续减半为2，此时第1个元素、第（1+2）、第（1+4）、第（1+6）、第（1+8）个元素组成子序列进行插入排序。这种增量选择方法的好处是可以使数组整体均匀有序，尽可能的减少比较和移动的次数，二分法中即使前一半数据有序，后一半中如果有比较小的数据，还是会造成大量的比较和移动，因此这种增量的方法和插入排序的配合更佳。
- 希尔排序的时间复杂度和增量的选择策略有关，上述增量方法造成希尔排序的不稳定性。
希尔排序
- C语言实现代码：
void shell_sort(int a[], int n)
{
int d, i, j, temp; //d为增量
for(d = n/2;d >= 1;d = d/2) //增量递减到1使完成排序
{
for(i = d; i < n;i++) //插入排序的一轮
{
temp = a[I];
for(j = i - d;(j >= 0) && (a[j] > temp);j = j-d)
{
a[j + d] = a[j];
}
a[j + d] = temp;
}
}
}
2.2.3.8 二叉树排序
算法简介
- 排序
- 算法描述
- 动态图演示过程
- 时间复杂度：
算法实现
- 二叉树排序法借助了数据结构二叉排序树，二叉排序数满足三个条件：（1）若左子树不空，则左子树上所有结点的值均小于它的根结点的值； （2）若右子树不空，则右子树上所有结点的值均大于它的根结点的值； （3）左、右子树也分别为二叉排序树。根据这三个特点，用中序遍历二叉树得到的结果就是排序的结果。
- 二叉树排序法需要首先根据数据构建二叉排序树，然后中序遍历，排序时间复杂度为O(nlogn)，构建二叉树需要额外的O(n)的存储空间，有相同的元素是可以设置排在后边的放在右子树，在中序变量的时候也会在后边，所以二叉树排序是稳定的。
- 在实现此算法的时候遇到不小的困难，指针参数在函数中无法通过new赋值，后来采用取指针地址，然后函数设置BST** tree的方式解决。
- C语言实现代码：
int arr[] = {7, 8, 8, 9, 5, 16, 5, 3,56,21,34,15,42};
struct BST{
int number; //保存数组元素的值
struct BST* left;
struct BST* right;
};
void insertBST(BST** tree, int v) {
if (*tree == NULL) {
*tree = new BST;
(*tree)->left=(*tree)->right=NULL;
(*tree)->number=v;
return;
}
if (v < (*tree)->number)
insertBST(&((*tree)->left), v);
else
insertBST(&((*tree)->right), v);
}
void printResult(BST* tree) {
if (tree == NULL)
return;
if (tree->left != NULL)
printResult(tree->left);
cout << tree->number << " ";
if (tree->right != NULL)
printResult(tree->right);
}
void createBST(BST** tree, int a[], int n) {
*tree = NULL;
for (int i=0; i<n; I++)
insertBST(tree, a[I]);
}
int main()
{
int n = sizeof(arr)/sizeof(int);
BST* root;
createBST(&root, arr, n);
printResult(root);
}
2.2.3.9 计数排序
算法简介
- 计数排序（Counting Sort）
计数排序的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。 作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。
计数排序(Counting sort)是一种稳定的排序算法。计数排序使用一个额外的数组C，其中第i个元素是待排序数组A中值等于i的元素的个数。然后根据数组C来将A中的元素排到正确的位置。它只能对整数进行排序。
- 算法描述
- 找出待排序的数组中最大和最小的元素；
- 统计数组中每个值为i的元素出现的次数，存入数组C的第i项；
- 对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）；
- 反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1。
- 动态图演示过程
计数排序-过程
- 时间复杂度：最佳情况：T(n) = O(n+k) 最差情况：T(n) = O(n+k) 平均情况：T(n) = O(n+k)
当输入的元素是n 个0到k之间的整数时，它的运行时间是 O(n + k)。计数排序不是比较排序，排序的速度快于任何比较排序算法。由于用来计数的数组C的长度取决于待排序数组中数据的范围（等于待排序数组的最大值与最小值的差加上1），这使得计数排序对于数据范围很大的数组，需要大量时间和内存。
算法实现
- 如果通过比较进行排序，那么复杂度的下界是O(nlogn)，但是如果数据本身有可以利用的特征，可以不通过比较进行排序，就能使时间复杂度降低到O(n)。
- 计数排序要求待排序的数组元素都是 整数，有很多地方都要去是0-K的正整数，其实负整数也可以通过都加一个偏移量解决的。
- 计数排序的思想是，考虑待排序数组中的某一个元素a，如果数组中比a小的元素有s个，那么a在最终排好序的数组中的位置将会是s+1，如何知道比a小的元素有多少个，肯定不是通过比较去觉得，而是通过数字本身的属性，即累加数组中最小值到a之间的每个数字出现的次数（未出现则为0），而每个数字出现的次数可以通过扫描一遍数组获得。
- 计数排序的步骤：
计数排序的步骤：
- 找出待排序的数组中最大和最小的元素（计数数组C的长度为max-min+1，其中位置0存放min，依次填充到最后一个位置存放max）
- 统计数组中每个值为i的元素出现的次数，存入数组C的第i项
- 对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）
- 反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1（反向填充是为了保证稳定性）
- C语言实现代码：
以下代码中寻找最大和最小元素参考编程之美，比较次数为1.5n次。
计数排序适合数据分布集中的排序，如果数据太分散，会造成空间的大量浪费，假设数据为（1,2,3,1000000），这就需要1000000的额外空间，并且有大量的空间浪费和时间浪费。
void findArrMaxMin(int a[], int size, int *min, int *max)
{
if(size == 0) {
return;
}
if(size == 1) {
*min = *max = a[0];
return;
}
*min = a[0] > a[1] ? a[1] : a[0];
*max = a[0] <= a[1] ? a[1] : a[0];
int i, j;
for(i = 2, j = 3; i < size, j < size; i += 2, j += 2) {
int tempmax = a[i] >= a[j] ? a[i] : a[j];
int tempmin = a[i] < a[j] ? a[i] : a[j];
if(tempmax > *max)
*max = tempmax;
if(tempmin < *min)
*min = tempmin;
}
//如果数组元素是奇数个，那么最后一个元素在分组的过程中没有包含其中，
//这里单独比较
if(size % 2 != 0) {
if(a[size -1] > *max)
*max = a[size - 1];
else if(a[size -1] < *min)
*min = a[size -1];
}
}
void count_sort(int a[], int b[], int n) {
int max, min;
findArrMaxMin(a, n, &min, &max);
int numRange = max-min+1;
int* counter = new int[numRange];
int i, j, k;
for (k=0; k<numRange; k++)
counter[k]=0;
for (i=0; i<n; I++)
counter[a[i]-min]++;
for (k=1; k<numRange; k++)
counter[k] += counter[k-1];
for (j=n-1; j>=0; j--) {
int v = a[j];
int index = counter[v-min]-1;
b[index]=v;
counter[v-min]--;
}
}
2.2.3.10 桶排序
算法简介
- 桶排序（Bucket Sort）
桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。
桶排序 (Bucket sort)的工作的原理：假设输入数据服从均匀分布，将数据分到有限数量的桶里，每个桶再分别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排.
- 算法描述
- 人为设置一个BucketSize，作为每个桶所能放置多少个不同数值（例如当BucketSize==5时，该桶可以存放｛1,2,3,4,5｝这几种数字，但是容量不限，即可以存放100个3）；
- 遍历输入数据，并且把数据一个一个放到对应的桶里去；
- 对每个不是空的桶进行排序，可以使用其它排序方法，也可以递归使用桶排序；
- 从不是空的桶里把排好序的数据拼接起来。
- 注意，如果递归使用桶排序为各个桶排序，则当桶数量为1时要手动减小BucketSize增加下一循环桶的数量，否则会陷入死循环，导致内存溢出。
-
动态图演示过程
桶排序1
桶排序2
-
时间复杂度：最佳情况：T(n) = O(n+k) 最差情况：T(n) = O(n+k) 平均情况：T(n) = O(n2)
桶排序最好情况下使用线性时间O(n)，桶排序的时间复杂度，取决与对各个桶之间数据进行排序的时间复杂度，因为其它部分的时间复杂度都为O(n)。很显然，桶划分的越小，各个桶之间的数据越少，排序所用的时间也会越少。但相应的空间消耗就会增大。
算法实现
- 实现线性排序，但当元素间值得大小有较大差距时会带来内存空间的较大浪费。首先，找出待排序列中得最大元素max，申请内存大小为max + 1的桶（数组）并初始化为0；然后，遍历排序数列，并依次将每个元素作为下标的桶元素值自增1；最后，遍历桶元素，并依次将值非0的元素下标值载入排序数列（桶元素>1表明有值大小相等的元素，此时依次将他们载入排序数列），遍历完成，排序数列便为有序数列。
- 时间复杂度：O(x*N) 稳定性：稳定
- 假设有一组长度为N的待排关键字序列K[1....n]。首先将这个序列划分成M个的子区间(桶) 。然后基于某种映射函数 ，将待排序列的关键字k映射到第i个桶中(即桶数组B的下标 i) ，那么该关键字k就作为B[i]中的元素(每个桶B[i]都是一组大小为N/M的序列)。接着对每个桶B[i]中的所有元素进行比较排序(可以使用快排)。然后依次枚举输出B[0]....B[M]中的全部内容即是一个有序序列。
- 桶排序利用函数的映射关系，减少了计划所有的比较操作，是一种Hash的思想，可以用在海量数据处理中。
- 我觉得计数排序也可以看作是桶排序的特例，数组关键字范围为N，划分为N个桶
- C语言实现代码：
/*桶排序*/
void bucketSort(vector<int> &arr)
{
int max = getMaxValue(arr);
int *pBuf = new int[max + 1];
memset(pBuf, 0, (max + 1)*sizeof(int));
for (auto const i : arr)
++pBuf[I];
for (int i = 0, j = 0; i <= max; ++i)
{
while (pBuf[i]--)
arr[j++] = i;
}
delete []pBuf;
}
2.2.3.11 基数排序
算法简介
- 基数排序（Radix Sort）
基数排序也是非比较的排序算法，对每一位进行排序，从最低位开始排序，复杂度为O(kn),为数组长度，k为数组中的数的最大的位数；
基数排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序。最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。基数排序基于分别排序，分别收集，所以是稳定的。
- 算法描述
- 取得数组中的最大数，并取得位数；
- arr为原始数组，从最低位开始取每个位组成radix数组；
- 对radix进行计数排序（利用计数排序适用于小范围数的特点）；
- 动态图演示过程
基数排序
- 时间复杂度：最佳情况：T(n) = O(n * k) 最差情况：T(n) = O(n * k) 平均情况：T(n) = O(n * k)
基数排序有两种方法：
MSD 从高位开始进行排序 LSD 从低位开始进行排序
基数排序 vs 计数排序 vs 桶排序
这三种排序算法都利用了桶的概念，但对桶的使用方法上有明显差异：
基数排序：根据键值的每位数字来分配桶
计数排序：每个桶只存储单一键值
桶排序：每个桶存储一定范围的数值
算法实现
- 桶排序的改进版，桶的大小固定为10，减少了内存空间的开销。首先，找出待排序列中得最大元素max，并依次按max的低位到高位对所有元素排序；桶元素10个元素的大小即为待排序数列元素对应数值为相等元素的个数，即每次遍历待排序数列，桶将其按对应数值位大小分为了10个层级，桶内元素值得和为待排序数列元素个数。
- 时间复杂度：O(x*N) 稳定性：稳定
- 基数排序也可以看作一种桶排序，不断的使用不同的标准对数据划分到桶中，最终实现有序。基数排序的思想是对数据选择多种基数，对每一种基数依次使用桶排序。
- 基数排序的步骤：以整数为例，将整数按十进制位划分，从低位到高位执行以下过程。
- 从个位开始，根据0~9的值将数据分到10个桶桶，例如12会划分到2号桶中。
- 将0~9的10个桶中的数据顺序放回到数组中。
- 重复上述过程，一直到最高位。
- C语言实现代码：
int getNumInPos(int num,int pos) //获得某个数字的第pos位的值
{
int temp = 1;
for (int i = 0; i < pos - 1; I++)
temp *= 10;
return (num / temp) % 10;
}
#define RADIX_10 10 //十个桶，表示每一位的十个数字
#define KEYNUM 5 //整数位数
void radix_sort(int* pDataArray, int iDataNum)
{
int *radixArrays[RADIX_10]; //分别为0~9的序列空间
for (int i = 0; i < RADIX_10; I++)
{
radixArrays[i] = new int[iDataNum];
radixArrays[i][0] = 0; //index为0处记录这组数据的个数
}
for (int pos = 1; pos <= KEYNUM; pos++) //从个位开始到31位
{
for (int i = 0; i < iDataNum; i++) //分配过程
{
int num = getNumInPos(pDataArray[i], pos);
int index = ++radixArrays[num][0];
radixArrays[num][index] = pDataArray[I];
}
for (int i = 0, j =0; i < RADIX_10; i++) //写回到原数组中，复位radixArrays
{
for (int k = 1; k <= radixArrays[i][0]; k++)
pDataArray[j++] = radixArrays[i][k];
radixArrays[i][0] = 0;
}
}
}
- C++实现代码：
/*基数排序*/
//1. 计数排序，按整形数值单位进行排序
void countSort(vector<int> &arr, int exp)
{
int bucket[10] = { 0 };
int arrSize = arr.size();
int *pTemp = new int[arrSize];
memset(pTemp, 0, arrSize * sizeof(int));
//统计单位exp各数值计数值
for (auto const val : arr)
++bucket[(val / exp) % 10];
//计数分层
for (int i = 1; i < 10; ++i)
bucket[i] += bucket[i - 1];
//按exp位大小用数组arr元素填充pTemp
for (int i = arrSize - 1; i >= 0; --i)
pTemp[ --bucket[(arr[i] / exp) % 10] ] = arr[i];
/*bugs*/
#if 0
//bug1: bucket各层次的计数值没遍历一次相应自减1
for (auto const val : arr)
pTemp[bucket[(val / exp) % 10] - 1] = val;
//bug2: arr数组元素每次排序时，下标应从大到小遍历，否则无法实现排序
for (auto const val : arr)
pTemp[ --bucket[(val / exp) % 10] ] = val;
#endif
//pTemp -> arr
for (int i = 0; i < arrSize; ++i)
arr[i] = pTemp[i];
delete []pTemp;
}
//2. 合并各单位计数排序结果
void radixSort(vector<int> &arr)
{
int max = getMaxValue(arr);
for (int exp = 1; max / exp != 0; exp *= 10)
countSort(arr, exp);
}
2.2.3.12
Reference
