导图社区 数据结构排序算法
数据结构常考排序算法，包括插入排序，希尔排序冒泡排序等几乎所有排序算法，排序是 重新排列表中的元素，使表中的元素满足按关键字递增或递减的过程。
这是一篇关于操作系统概论的思维导图，OS是指控制和管理整个计算机系统的硬件与软件资源合理的组织、调度计算机的工作与资源分配，进而为用户和其他软件提供方便接口与环境的程序集合。是计算机系统中最基本的系统软件。
一篇关于计算机操作系统IO的一些基本概念，介绍详细、描述全面、希望能对感兴趣的小伙伴学习提供帮助。
社区模板帮助中心，点此进入>>
互联网9大思维
组织架构-单商户商城webAPP 思维导图。
域控上线
python思维导图
中国特色社会主义
css
CSS
马克思主义原理
计算机操作系统思维导图
计算机组成原理
排序
排序的基本概念
重新排列表中的元素，使表中的元素满足按关键字递增或递减的过程
算法的稳定性
若排序算法中有两个元素Ri和Rj，其对应的关键字keyi=keyj，且在排序前Ri在Rj前面，若排序后，Ri仍在Rj前面，在这个算法是稳定的。否则不稳定。
稳定性不能衡量算法的优劣
插入排序
直接插入排序
将序列分为有序和无序两个部分，后面的无序部分每次在有序中查找到合适的位子插入
原理
待排序表 L [1···n] 在某次排序过程中的某一时刻状态
1、查找出L(i) 在 L[1···i-1] 中的插入位置k
2、将L[ k ··· i-1] 中所有元素全部后移一个位置
3）将 L(i）复制到 L(k）
性能
空间复杂度O(1)
最好时间复杂度O(n)
最坏时间复杂度O(n^2)
平均时间复杂度O(n^2)
稳定
适用
顺序表、链表
折半插入排序
折半查找的直接插入排序
元素比较次数
最好时间复杂度
顺序表
希尔排序
排序表分成若干个子表，每个子表进行直接插入排序，最后再进行一次整个的插入排序
时间复杂度O(n^1.3)
估算
不稳定
交换排序
冒泡排序
从头开始，对每个两两相邻的元素比较，大就往后排，比较完后最大的元素将在末尾。 重复上述过程，不比已经排出来最大的那个，一直重复得到顺序序列
序列有序时，比较次数n-1，移动次数0，时间复杂度O(n)
序列逆序时
快速排序
1．先从数列中取出一个数作为基准数。 2．分区过程：将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。 3．再对左右区间重复第二步，直到各区间只有一个数。
最坏的情况是，每次所选的中间数是当前序列中的最大或最小元素. 长度为n的数据表的快速排序需要经过n趟划分，使得整个排序算法的时间复杂度为O(n^2)
空间
最坏空间复杂度O(n)
平均空间复杂度
时间
最坏时间复杂度
O(n^2)
平均时间复杂度
选择排序
简单选择排序
每次选出最小的与位指定置交换
比较次数 n(n-1)/2 时间复杂度O(n^2)
最好时间复杂度O(n^2)
堆排序
堆
n个关键字序列 L[1 ... n] 称为堆，当且仅当该序列满足：
小根堆
大根堆
先将待排序列构造为堆，选出堆中最大（或最小）元素即 堆顶元素输出 堆顶元素输出后，堆底元素送入堆顶，堆的性质被破坏，将堆顶元素向下调整使其再次成堆，反复输出堆顶元素
建堆
1、按序列顺序构造二叉树
{5, 2, 6, 0, 3, 9, 1, 7, 4, 8}
2、找到⌊n/2⌋处，以它为根结点的树进行调整
3、找到之前结点的前一个结点，继续调整，一直重复 调整过程中要保证已经调整过的堆还是符合规则的
插入
将结点加入到最后一个结点，自底向上依次调整
删除
只能删除根结点
将最后一个结点替换根结点，从上至下依次调整
归并排序
二路归并排序
待排序表含有n个记录，看成是n个有序的子表，每个子表长度为1， 然后两两归井 得到 ⌈n/2⌉ 个长度为2或1的有序表，再两两归井，如此重复，直到合并成一个长度为n的有序表 注意区分递归归并和非递归归并
空间复杂度O(n)
基数排序
基数排序是按照低位先排序,然后收集;再按照高位排序,然后再收集;依次类推,直到最高位.
