數(shù)據(jù)結(jié)構(gòu)與算法面試題(一)

一秕硝、常見的排序算法

排序算法比較
基本思想:

1远豺、冒泡排序:兩兩比較相鄰數(shù)據(jù),逆序則交換惊来,如果有一趟沒有發(fā)生交換棺滞,說明排序完成内狸。
2昆淡、簡單選擇排序:每一趟(第i趟)通過n-i次數(shù)據(jù)比較昂灵,從n-i+1個(gè)數(shù)據(jù)中選擇最小的數(shù)據(jù)作為第i個(gè)數(shù)據(jù)舞萄。一共排n次。
3撑螺、直接插入排序:將待排序的數(shù)據(jù)分成有序序列和無序序列的兩部分崎弃,每次從無序序列取一個(gè)數(shù)據(jù)插入到已經(jīng)排好的有序序列中,直到無序序列中沒有數(shù)據(jù)线婚。
4盆均、希爾排序:先將整個(gè)待排序列分割成若干子序列分別進(jìn)行直接插入排序,然后依次縮減增量再進(jìn)行直接插入排序游沿,待整個(gè)序列中的數(shù)據(jù)基本有序時(shí)诀黍,再對全體序列進(jìn)行一次直接插入排序(增量為1)唇敞。
5、堆排序:將待排序數(shù)據(jù)構(gòu)造成一個(gè)大頂堆咒精。此時(shí)旷档,整個(gè)序列的最大值就是堆頂?shù)母Y(jié)點(diǎn)。將它與序列末尾元素交換范咨,然后將剩余n-1個(gè)數(shù)據(jù)重新構(gòu)造一個(gè)堆,這樣就會得到n個(gè)元素中的次小值渠啊,如此反復(fù)執(zhí)行,直到排序完成贯溅。
6它浅、歸并排序:假設(shè)初始序列有n個(gè)數(shù)據(jù)镣煮,可以看作n個(gè)有序的子序列,每個(gè)子序列長度為1镊折,首先進(jìn)行兩兩歸并蚓聘,然后四四歸并,然后八八歸并,一直下去侣签,直至得到一個(gè)長度為n的有序序列為止。
7蹦肴、快速排序:通過一趟排序?qū)⑿蛄袆澐殖蓛刹糠忠趸希渲幸徊糠炙袛?shù)據(jù)都小于另一部分的數(shù)據(jù)卷中,再按照此方法繼續(xù)對這兩部分分別進(jìn)行快速排序,整個(gè)排序過程可以遞歸進(jìn)行议忽,直到變成有序序列十减。

優(yōu)缺點(diǎn)比較:

1愤估、快排的效率最高玩焰。但其缺點(diǎn)十分明顯:在待排序列基本有序的情況下芍锚,會退化成冒泡排序,時(shí)間復(fù)雜度接近 O(N^2)蒿赢。
2羡棵、希爾排序?qū)υ隽康倪x擇標(biāo)準(zhǔn)仍然沒有較為滿意的答案嗅钻,而增量的選取直接影響排序的效率;
3秃流、在數(shù)據(jù)規(guī)模較大時(shí)柳弄,歸并排序比希爾排序、堆排序速度更快嚣伐;
4萍丐、堆排序在數(shù)據(jù)規(guī)模較小的情況下速度較快逝变,但是隨著規(guī)模的增大,時(shí)間代價(jià)也開始和希爾和歸并兩種排序拉開距離拱层。

適用條件:
(1) n較小态贤,待排序列基本有序時(shí),選擇直接插入排序或冒泡排序箱吕;
(2)n較小,對穩(wěn)定性沒要求時(shí)兆旬,用選擇排序丽猬;
(3)n較大熏瞄,待排序列隨機(jī)分布,對穩(wěn)定性沒要求時(shí)由桌,用快速排序邮丰;
(4)n較大,待排序列基本有序娃循,對穩(wěn)定性有要求時(shí)斗蒋,在空間允許的情況下,用歸并排序骤星;
(5)n較大爆哑,待排序列基本有序揭朝,對穩(wěn)定性沒要求時(shí)潭袱,用堆排序锋恬;
(6)海量級別的數(shù)據(jù),必須按塊存放在外存(磁盤)中彤悔,用歸并排序;抑片;
(7)若待排序的記錄的關(guān)鍵字在一個(gè)明顯有限范圍內(nèi)時(shí),且空間允許是用桶排序杨赤。
上面的排序算法,當(dāng)記錄的規(guī)模較大時(shí)植捎,為避免耗費(fèi)大量的時(shí)間去移動記錄阳柔,可以用鏈表作為存儲結(jié)構(gòu)。譬如插入排序医咨、歸并排序拟淮、基數(shù)排序都易于在鏈表上實(shí)現(xiàn)谴忧,使之減少記錄的移動次數(shù)。但有的排序方法委造,如快速排序和堆排序均驶,在鏈表上卻難于實(shí)現(xiàn),在這種情況下爬虱,可以提取關(guān)鍵字建立索引表跑筝,然后對索引表進(jìn)行排序瞒滴。

二、查找算法性能總結(jié)

查找算法比較

三虏两、解釋平衡二叉樹,以及在數(shù)據(jù)結(jié)構(gòu)中的應(yīng)用(紅黑樹)

Q1:平衡二叉樹是一種二叉排序樹忘瓦,其中每個(gè)節(jié)點(diǎn)的左子樹和右子樹的高度差至多等于1.
Q2:可以用于查找數(shù)據(jù)引颈,時(shí)間復(fù)雜度為O(logN)。但是蝙场,由于插入或者刪除一個(gè)節(jié)點(diǎn)需要掃描兩趟樹,一次需要尋找插入點(diǎn)罚拟,一次需要向上平衡樹赐俗,效率不高(不如紅黑樹效率高)。
補(bǔ)充:
AVL樹阻逮,平衡二叉樹秩彤。適合增刪少,查找多的場景瓜富。
紅黑樹降盹,近似的平衡二叉樹,能夠以O(shè)(log2 n)的時(shí)間復(fù)雜度進(jìn)行搜索仅胞、插入剑辫、刪除操作妹蔽。此外,由于它的設(shè)計(jì)编整,任何不平衡都會在三次旋轉(zhuǎn)之內(nèi)解決乳丰。適合插入刪除次數(shù)多,查找次數(shù)也多的場景汞斧。
在數(shù)據(jù)結(jié)構(gòu)中的應(yīng)用:java中的TreeMap和TreeSet
1)插入刪除查找效率高:能夠以O(shè)(log2 N) 的時(shí)間復(fù)雜度進(jìn)行搜索什燕、插入、刪除操作
2)
有序
:TreeMap 中的所有元素總是按 key 根據(jù)指定排序規(guī)則保持有序狀態(tài)庙睡,TreeSet 中所有元素總是根據(jù)指定排序規(guī)則保持有序狀態(tài)(TreeSet 底層是通過 TreeMap 來實(shí)現(xiàn)的)乘陪。
B樹雕擂,B+樹:多路查找樹,一般用于磁盤存儲捂刺,分支多,層數(shù)少森缠,有效減少了磁盤的I/O操作次數(shù)贵涵,有效減少了數(shù)據(jù)查找的時(shí)間。
紅黑樹與AVL樹的比較

四宾茂、快排的時(shí)間復(fù)雜度和空間復(fù)雜度跨晴。

時(shí)間復(fù)雜度:
快速排序的平均時(shí)間復(fù)雜度也是:O(nlogn)片林。
最優(yōu)的情況下時(shí)間復(fù)雜度為:O( nlogn )怀骤。
最差的情況就是每一次取到的元素就是數(shù)組中最小/最大的蒋伦,這種情況其實(shí)就是冒泡排序了(每一次都排好一個(gè)元素的順序)焚鹊,時(shí)間復(fù)雜度為:O( n^2 )。
2)空間復(fù)雜度:
就地快速排序:O(1)
遞歸實(shí)現(xiàn)快速排序
因?yàn)槊看芜f歸就要保持一些數(shù)據(jù)研叫;
最優(yōu)的情況下空間復(fù)雜度為:O(logn) 阻塑;每一次都平分?jǐn)?shù)組的情況
最差的情況下空間復(fù)雜度為:O( n );退化為冒泡排序的情況渤昌。

五独柑、解釋深度優(yōu)先搜索和廣度優(yōu)先搜索

最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
  • 序言:七十年代末私植,一起剝皮案震驚了整個(gè)濱河市,隨后出現(xiàn)的幾起案子曲稼,更是在濱河造成了極大的恐慌贫悄,老刑警劉巖,帶你破解...
    沈念sama閱讀 216,843評論 6 502
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件唤反,死亡現(xiàn)場離奇詭異彤侍,居然都是意外死亡逆趋,警方通過查閱死者的電腦和手機(jī),發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 92,538評論 3 392
  • 文/潘曉璐 我一進(jìn)店門般哼,熙熙樓的掌柜王于貴愁眉苦臉地迎上來,“玉大人,你說我怎么就攤上這事楞卡。” “怎么了蒋腮?”我有些...
    開封第一講書人閱讀 163,187評論 0 353
  • 文/不壞的土叔 我叫張陵池摧,是天一觀的道長作彤。 經(jīng)常有香客問我乌逐,道長,這世上最難降的妖魔是什么绢慢? 我笑而不...
    開封第一講書人閱讀 58,264評論 1 292
  • 正文 為了忘掉前任胰舆,我火速辦了婚禮缚窿,結(jié)果婚禮上,老公的妹妹穿的比我還像新娘滨攻。我一直安慰自己光绕,他們只是感情好,可當(dāng)我...
    茶點(diǎn)故事閱讀 67,289評論 6 390
  • 文/花漫 我一把揭開白布。 她就那樣靜靜地躺著爆雹,像睡著了一般。 火紅的嫁衣襯著肌膚如雪慧起。 梳的紋絲不亂的頭發(fā)上菇晃,一...
    開封第一講書人閱讀 51,231評論 1 299
  • 那天,我揣著相機(jī)與錄音灿意,去河邊找鬼。 笑死馅袁,一個(gè)胖子當(dāng)著我的面吹牛荒辕,可吹牛的內(nèi)容都是我干的兄纺。 我是一名探鬼主播,決...
    沈念sama閱讀 40,116評論 3 418
  • 文/蒼蘭香墨 我猛地睜開眼钦奋,長吁一口氣:“原來是場噩夢啊……” “哼付材!你這毒婦竟也來了厌衔?” 一聲冷哼從身側(cè)響起捍岳,我...
    開封第一講書人閱讀 38,945評論 0 275
  • 序言:老撾萬榮一對情侶失蹤页徐,失蹤者是張志新(化名)和其女友劉穎变勇,沒想到半個(gè)月后贴唇,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體飞袋,經(jīng)...
    沈念sama閱讀 45,367評論 1 313
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡巧鸭,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 37,581評論 2 333
  • 正文 我和宋清朗相戀三年,在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了芯肤。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片。...
    茶點(diǎn)故事閱讀 39,754評論 1 348
  • 序言:一個(gè)原本活蹦亂跳的男人離奇死亡压鉴,死狀恐怖崖咨,靈堂內(nèi)的尸體忽然破棺而出,到底是詐尸還是另有隱情油吭,我是刑警寧澤击蹲,帶...
    沈念sama閱讀 35,458評論 5 344
  • 正文 年R本政府宣布,位于F島的核電站婉宰,受9級特大地震影響歌豺,放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜心包,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 41,068評論 3 327
  • 文/蒙蒙 一类咧、第九天 我趴在偏房一處隱蔽的房頂上張望。 院中可真熱鬧蟹腾,春花似錦痕惋、人聲如沸。這莊子的主人今日做“春日...
    開封第一講書人閱讀 31,692評論 0 22
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽。三九已至螟炫,卻和暖如春昼钻,著一層夾襖步出監(jiān)牢的瞬間然评,已是汗流浹背盏求。 一陣腳步聲響...
    開封第一講書人閱讀 32,842評論 1 269
  • 我被黑心中介騙來泰國打工, 沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留,地道東北人憔购。 一個(gè)月前我還...
    沈念sama閱讀 47,797評論 2 369
  • 正文 我出身青樓犀勒,卻偏偏與公主長得像账蓉,于是被迫代替她去往敵國和親肮雨。 傳聞我的和親對象是個(gè)殘疾皇子怨规,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 44,654評論 2 354

推薦閱讀更多精彩內(nèi)容