导图社区 内部排序
计算机专业考研党看过来！本图是有关于数据结构内部排序的总结，归纳了极爱换排序、选择排序、技术排序等内容。
最近很多高考学生在申请高校专项计划，这是一份今年高校专项院校名单思维导图，希望能给到填选志愿的学生帮助。
专项计划是一个少数考生能够享受的机会点，希望家长一定要用好专项。专项计划和普通计划有所不同，具有较强的目的性、专业性和针对性，常由专业人士来完成，常常是业务主管，行政工作人员或者是科研学者主持制定。
离高考越来越近，专业有没有选好呢？这是一份高考热门专业的简介，主要包含大学学习的课程和以后的就业方向。
社区模板帮助中心，点此进入>>
安全教育的重要性
个人日常活动安排思维导图
西游记主要人物性格分析
17种头脑风暴法
如何令自己更快乐
头脑风暴法四个原则
思维导图
第二职业规划书
记一篇有颜又有料的笔记-by babe
伯赞学习技巧
数据结构排序方法总结
内部排序
插入排序
直接插入排序
思想:将给定序列中部分有序的或第一个元素看成一个排好序的子序列，然后将后面元素依次比较插入。（个人理解口述版）
空间效率:只需要常数个辅助空间，O（1）
时间效率
向有序子表中逐个地插入元素的操作进行了n-1趟，每趟操作都分为比较关键字和移动元素。
最好情况下，每插入一个元素都只需比较一次而不用移动元素（表中元素已经有序），时间复杂度为O（n）。
平均时间复杂度为O（n²）
稳定性:是一种稳定的排序方法
特点
比较次数和移动次数都取决于待排序表的初始状态
适用于顺序存储和链式存储的线性表
为链式存储时，可以从前往后查找指定元素的位置
折半插入排序
思想:将比较和移动操作分离，先折半查找元素的待插入位置，然后统一地移动待插入元素之后的所有元素。
空间效率:应该也是O（1）
时间效率:时间复杂度仍为O（n²）
特点:比较次数与待排序表的初始状态无关，仅取决于表中的元素个数n；元素的移动次数，仍然依赖于待排序表的初始状态。
希尔排序
思想:先把待排序表分割成若干个特殊子表，对各个子表分别进行直接插入排序，当整个表中的元素已呈“基本有序时”，再对全体进行一次直接插入排序。
因为直接插入排序更适合基本有序的排序表和数据量不大的排序表
空间效率:仅使用了常数个辅助单元，因而空间复杂度为O（1）
时间效率:最坏情况下时间复杂度为O（n²）
稳定性
是一种不稳定的排序方法
仅适用于顺序存储的线性表
交换排序
冒泡排序
思想:从后往前（或从前往后）两两比较相邻元素的值，若为逆序，则交换它们，直到序列比较完。
空间效率:仅使用了常数个辅助单元，空间复杂度为O（1）
时间效率:最好情况时间复杂度为O（n），最坏时间复杂度为O（n²），平均时间复杂度也为O（n²）
每一趟排序都会有一个元素放置到其最终位置上
快速排序
思想:在待排序表中任取一个元素（一般取第一个）作为枢轴，然后从后往前，然后找到第一个小于枢轴的元素，将其交换到枢轴的位置（此时枢轴还是原来的元素，第一趟结束之前不变），再从前往后，找到第一个大于枢轴的元素，将其交换到第一个小于枢轴的元素的空位置，以此交替进行，直到往前和往后重合，将枢轴元素填入空的位置。然后枢轴元素就到它的最终位置了，将它前后分为两个子表，继续同上排序。（个人理解口述版）
空间效率:最好情况下是O（log₂n），最坏的情况下是O（n），平均情况下是O（log₂n）
时间效率:最坏时间复杂度为O（n²）
稳定性:是一种不稳定的排序方法
快速排序是所有内部排序算法中平均性能最优的排序算法
选择排序
简单选择排序
思想:排序表的第i趟从第i位元素后面所有元素（包括它自己）中关键字最小的元素与第i位元素交换
空间效率:仅使用常数个辅助单元，故空间效率为O（1）
时间效率:时间复杂度O（n²）
每一趟排序可以确定一个元素的位置
堆排序
思想:将无序序列构造成初始堆，堆顶元素要么最大（大根堆），要么最小，输出堆顶后，继续调整成大或小根堆，继续输出堆顶元素，如此往复
时间效率:最好、最坏、平均情况下时间复杂度都是O（log₂n）
归并排序
思想:内部中一般采用2路归并，将待排序表每两个元素分成一组进行排序，排好的分组又每两个分组进行排序，如此往复，直到完全归并
空间效率:需要辅助空间刚好为n个单元，空间复杂度为O（n）
时间效率:O（nlog₂n）
基数排序
思想:对关键字各位数的大小进行排序，比如先个位，再十位，再百位
空间效率:一趟排序需要的辅助空间是r（r个队列:r个头指针和r个队尾指针），空间复杂度为O（r）
时间效率:需要进行d趟分配和收集，一趟分配需要O（n），一趟收集需要O（r），所以时间复杂度为O（d（n+r）
稳定性:是稳定的
基你太稳
