一.时间复杂度和空间复杂度的概率
1.时间复杂度
一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数，用T(n)表示，若有某个辅助函数f(n),使得当n趋近于无穷大时，T（n)/f(n)的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数。记作T(n)=Ｏ(f(n)),称Ｏ(f(n)) 为算法的渐进时间复杂度，简称时间复杂度
2.空间复杂度
空间复杂度(Space )是对一个算法在运行过程中临时占用存储空间大小的量度。一个算法在计算机存储器上所占用的存储空间，包括存储算法本身所占用的存储空间，算法的输入输出数据所占用的存储空间和算法在运行过程中临时占用的存储空间这三个方面。算法的输入输出数据所占用的存储空间是由要解决的问题决定的，是通过参数表由调用函数传递而来的，它不随本算法的不同而改变。存储算法本身所占用的存储空间与算法书写的长短成正比，要压缩这方面的存储空间，就必须编写出较短的算法。算法在运行过程中临时占用的存储空间随算法的不同而异
二…排序算法的时间复杂度和空间复杂度对比
时间复杂度记忆
冒泡、选择、直接 排序需要两个for循环，每次只关注一个元素，平均时间复杂度为O(n2)（一遍找元素O(n)，一遍找位置O(n)）
快速、归并、希尔、堆基于二分思想，log以2为底，平均时间复杂度为O(nlogn)（一遍找元素O(n)，一遍找位置O(logn)）
稳定性记忆-“快希选堆”（不稳定）
三…排序算法代码部分()
1.插入排序：
[1]直接插入排序,for+while实现，外层的for循环表示从第一个元素到第N个元素要逐一插入，while表示的每次的插入过程
[2]希尔排序 :while+for+while循环，while用于控制步长，后面使用的是插入排序的思想
2.选择排序：
[1]简单选择排序： 两个for循环，每次每个元素和后面的所有元素比较，选出最小的放到前面，n个元素需要n-1轮，每轮都是i和i+1后面的所有元素比较
[2]堆排序：构建大根堆（用于升序排列），小根堆（用于降序排列），从底层向顶层构建大根堆或小根堆
3.交换排序：
[1]冒泡排序：两个for循环，每次相邻的两个元素进行比较,最大值向后移，n个元素需要冒泡n-1轮，每轮需要两两比较的元素个数为n-1-i
[2]快速排序: 递归实现，每次找一个基准值，使得基准值左边的都比他小，右边的都比他大
4.归并排序：分治法，先逐步分成小的分组，组内排序，然后组间合并
1.选择排序 每一轮用前面的一个数和后面所有的数进行比较，选出一个最小的放在前面，n个元素需要n-1轮，每轮都是i和i+1后面的所有元素比较
2.冒泡算法，每一轮是相邻两个元素进行比较，将较大的往后移，n个元素需要冒泡n-1轮，每轮需要两两比较的元素个数为n-1-i
3.插入排序 插入过程中将前面大于的数往后移,for+while 每次找到一个比前面小的数，将这个数和前面所有的进行比较，移到前面
4.快速排序(选择排序的改进版)每次选择一个基准数，实现左边的都比它小，右边的都比它大
5.堆排序(冒泡排序的改进版)大根堆，小根堆
常见的应用场景：找出最大的k个数，初始化一个k个节点的小根堆，然后将剩下的数据和堆顶元素比较，比堆顶大就替换，然后调整小根堆，迭代进行，最终树上剩下的节点就是最大的k个数
#6.希尔排序(插入排序的改进，也称增量排序),增量插入，按照一定的增量将数据分组进行组内排序，当增量为1时就变成一组数据进行排序了
#7.归并排序
相关文章
