排序问题(默认升序)

选择排序

从第一个元素开始找最小的放在最前面,依次进行 复杂度 n²

插入排序

从第二个开始开始到最后进行遍历,将需要比对的值先取出来,在和前面的值进行比较,如果前面的值比他大,则前面的值后移一位,如果前面的值比他小,则停止向前遍历,将需要排序的值插入进去.

归并排序

将一个数组一直两两平分

 然后创建一个相同得辅助数组设置三个下标 分别是 i j k

 i:辅助数组左边起始得位置

 j：辅助数组右边起始得位置(就是mid+1)

 k:真实数组得下标位置

 然后再进行合并

快速排序

帮助第一个元素找出正确的位置,使让他左边的比他小 右边的比他大,再通过递归一直排序

三路排序的思想:

分为三个区域 比他小 比他大 和相等, 

设置三个下标lt(比他小的最后一个元素的下标) gt(比他大的第一个元素下标) i（当前元素下标）

lt初始化lt=l  gt=r+1 i=l+1 因为一开始不确定真实存在lt和gt 所以都设在边界+1/-1

如果比他小则放在lt的区域  

如果比他大则放在gt的区域

如果相等则继续遍历

最大堆

所有的子节点都比父节点小则是最大堆

如何寻找自己的父节点 左儿子 右儿子

二叉搜索树的前中后遍历:

前序遍历:先访问当前节点,再一次递归访问左右子树 (一直往左,没有就回上一个点,然后往右)

中序遍历:线递归访问左子树,再访问自身,再递归访问右子树 (顺便排队)

后续遍历:先递归访问左右子树,再访问自身节点

三个点分别是前中后序