排序問題(默認(rèn)升序)
選擇排序
從第一個元素開始找最小的放在最前面,依次進(jìn)行 復(fù)雜度 n2
插入排序
從第二個開始開始到最后進(jìn)行遍歷,將需要比對的值先取出來,在和前面的值進(jìn)行比較,如果前面的值比他大,則前面的值后移一位,如果前面的值比他小,則停止向前遍歷,將需要排序的值插入進(jìn)去.
歸并排序
將一個數(shù)組一直兩兩平分
?然后創(chuàng)建一個相同得輔助數(shù)組設(shè)置三個下標(biāo) 分別是 i j k
?i:輔助數(shù)組左邊起始得位置
?j：輔助數(shù)組右邊起始得位置(就是mid+1)
?k:真實數(shù)組得下標(biāo)位置
?然后再進(jìn)行合并
快速排序
幫助第一個元素找出正確的位置,使讓他左邊的比他小 右邊的比他大,再通過遞歸一直排序
三路排序的思想:
分為三個區(qū)域 比他小 比他大 和相等,?
設(shè)置三個下標(biāo)lt(比他小的最后一個元素的下標(biāo)) gt(比他大的第一個元素下標(biāo)) i（當(dāng)前元素下標(biāo)）
lt初始化lt=l? gt=r+1 i=l+1?因為一開始不確定真實存在lt和gt 所以都設(shè)在邊界+1/-1
如果比他小則放在lt的區(qū)域??
如果比他大則放在gt的區(qū)域
如果相等則繼續(xù)遍歷
最大堆
所有的子節(jié)點都比父節(jié)點小則是最大堆
如何尋找自己的父節(jié)點 左兒子 右兒子
二叉搜索樹的前中后遍歷:
前序遍歷:先訪問當(dāng)前節(jié)點,再一次遞歸訪問左右子樹 (一直往左,沒有就回上一個點,然后往右)
中序遍歷:線遞歸訪問左子樹,再訪問自身,再遞歸訪問右子樹 (順便排隊)
后續(xù)遍歷:先遞歸訪問左右子樹,再訪問自身節(jié)點
三個點分別是前中后序
