有序度: 是数组中具有有序关系的元素对的个数
有序元素对:a[i] <= a[j], 如果 i < j。
逆序度: 与有序度刚好相反
满有序度:对于一组完全有序的数组来说
有序度 = 满有序度 + 逆序度 $$ n*(n-1)/2 $$
原理:将一个数组中的数据划分为已排序的区间和未排序的区间。初始时,数组的第一个元素作为已排序区间中的数,核心细想就是每一次从未排序区间开头取一个数,和已排序区间的数做比较,找到合适的位置插入。
- 插入排序属于原地排序和稳定排序
- 最好的时候时间复杂度:O(n)
- 最坏的时候时间复杂度:O(n^2)
- 平均时间复杂度:O(n^2)
虽然两者的时间复杂度同为O(n^2),但是对于实际操作来说,冒泡排序赋值需要3步,而插入排序只是需要一步就搞定了。
树中任意节点的值,左子树中每个节点的值都要小于这个节点,右子树中每个节点的值都要大于这个节点。
二叉树中任意一个节点的左右子树的高度相差不能大于 1。