2017-09-05學(xué)習(xí)記錄1

今天復(fù)習(xí)了五個(gè)排序硅则,分別是冒泡排序冒掌,選擇排序,插入排序蹲盘,哈希排序和快速排序股毫;

然后看了thinking in java的第一章和第二章;

下面就是今天學(xué)的所有知識(shí)


1.冒泡排序:冒泡排序主要是對(duì)鄰近的數(shù)據(jù)進(jìn)行比較召衔,根據(jù)結(jié)果判斷是否進(jìn)行交換铃诬,一輪一輪挑出其中比較大(小)的數(shù)據(jù)放到數(shù)組末尾薄嫡;在一輪一輪比較中氧急,需要比較的數(shù)據(jù)一次減少一個(gè)颗胡,直到最后下標(biāo)為0和1的進(jìn)行比較后毫深,則代表數(shù)組已經(jīng)有序了。

下面是實(shí)現(xiàn)代碼:

冒泡排序

在這里面毒姨,upper用來(lái)決定每一輪進(jìn)行排序的數(shù)據(jù)個(gè)數(shù)哑蔫,由于下標(biāo)可以為0且內(nèi)部有sc[i+1]代碼的存在,所以里層for循環(huán)的取值為:0~sc.length-2;

2.選擇排序:這個(gè)選擇排序和冒泡排序進(jìn)行比較的次數(shù)相等弧呐,不過(guò)這里是一次性找出一輪數(shù)據(jù)中最大(姓⒚浴)的數(shù)據(jù),放在數(shù)組末尾(開(kāi)頭)俘枫,然后下一輪取其他的數(shù)據(jù)再一次進(jìn)行選取最大(行裙痢)值;

下面是實(shí)現(xiàn)代碼:

選擇排序

這里實(shí)現(xiàn)的是一個(gè)從小到大的排序鸠蚪。首先upper和上面一樣取值:1~sc.length-1今阳,在表循環(huán)中,將sc[0]設(shè)置為最大值茅信,然后數(shù)據(jù)判斷從下標(biāo)1開(kāi)始盾舌,若有sc[n]<sc[0]則把最大值的下標(biāo)由0換成n,最后判斷一下最后的數(shù)據(jù)是否是下標(biāo)代表的最大值蘸鲸,不是則把下標(biāo)代表的最大值和最后面的值做一個(gè)交換妖谴,這樣就完成了一次排序;

這里的子循環(huán)中的i可以為1酌摇,這代表sc[0]和sc[1]進(jìn)行比較膝舅;


3.插入排序:插入排序是把一個(gè)數(shù)組分成了三個(gè)部分:有序部分,待插入值窑多,無(wú)序部分铸史;有序部分的個(gè)數(shù)由1~sc.length-1;當(dāng)最后一個(gè)數(shù)據(jù)也進(jìn)入了有序隊(duì)列怯伊,則排序完成琳轿;插入排比價(jià)序主要是將待插入值放入有序隊(duì)列中去判沟,通過(guò)比較,將它插入到隊(duì)列中形成一個(gè)有序的新隊(duì)列崭篡;

下面是插入排序的代碼:

插入排序

其中count代表待插入值的下標(biāo)挪哄,1~sc.length-1;然后子循環(huán)中用num來(lái)存儲(chǔ)待插入值琉闪,讓每一個(gè)值和他比較迹炼,若待插入值小于比較的值,則把比較的值直接后移一位颠毙;i=1時(shí)代表前面所有數(shù)據(jù)都大于待插入值斯入,所以就把該值放在0下標(biāo)處;


4.哈希排序:哈希排序是一個(gè)改良版的插入排序蛀蜜,它主要是通過(guò)選取一定的間隔刻两,在早期就把離正確位置很遠(yuǎn)的數(shù)據(jù)直接一次性轉(zhuǎn)移過(guò)去,而不需要插入排序一樣一次一次比較復(fù)制慢慢地轉(zhuǎn)移過(guò)去滴某。在大量數(shù)據(jù)中磅摹,他的速度要比插入排序好很多,而且它在數(shù)據(jù)逆行的情況下霎奢,速度比插入排序快了很多户誓;下面是哈希排序的代碼,這個(gè)我自己也不是很明白幕侠;

希爾排序

這里的num就是選取的固定間隔帝美,num遵循一種算式,讓每一個(gè)num互成質(zhì)數(shù)晤硕,這樣的效率是最高的悼潭;第一次排序,對(duì)下標(biāo)為:num~sc.length-1的數(shù)據(jù)進(jìn)行了間隔為num的數(shù)組的排序窗骑,注意這里子循環(huán)判斷條件已經(jīng)發(fā)生改變了女责;然后按公式慢慢減小num,最后直到為1時(shí),代表數(shù)據(jù)已經(jīng)排序完成创译;

哈希排序和插入排序最大的不同之處在于 ?sc[i] = sc[i-1] ?和 ?sc[i] = sc[i-num]抵知;


5.快速排序:快速排序主要是應(yīng)用了一個(gè)遞歸和劃分的概念。劃分指的是取一個(gè)值软族,將數(shù)組中的數(shù)據(jù)分成兩部分刷喜,左邊的全部小于該數(shù)據(jù),右邊的全部大于等于該數(shù)據(jù)立砸;然后又把左邊和右邊兩個(gè)數(shù)組用這個(gè)方法掖疮,分到最后,所有數(shù)據(jù)已經(jīng)做到了有序狀態(tài)了颗祝;這個(gè)排序要分成兩個(gè)部分浊闪,一個(gè)是遞歸的部分恼布,另一個(gè)是劃分的部分;

劃分部分
遞歸部分


這個(gè)函數(shù)采用的是直接把數(shù)組最右邊的數(shù)據(jù)作為他的中間值(樞紐)搁宾,然后在劃分后折汞,把樞紐放在兩個(gè)部分中間,此時(shí)該數(shù)據(jù)已經(jīng)存在了正確排序的位置了盖腿,然后對(duì)兩邊兩組新數(shù)組進(jìn)行排序……

在劃分階段爽待,我們?cè)O(shè)置了一個(gè)左指針和右指針,分別判斷兩頭的數(shù)據(jù)和樞紐的關(guān)系翩腐,若左側(cè)存在大于樞紐的值并且右側(cè)存在小于樞紐的值鸟款,則將兩個(gè)值進(jìn)行交換,然后繼續(xù)判斷茂卦,直到兩個(gè)指針相等或擦肩而過(guò)何什,則代表該已經(jīng)劃分成功,這時(shí)候把最右端數(shù)據(jù)和右數(shù)組的第一個(gè)數(shù)據(jù)進(jìn)行交換疙筹,則完成了劃分的功能了富俄。返回的是中間樞紐的下標(biāo)值禁炒;


上面是今天所有的排序知識(shí)而咆,后面還有另外兩章;

最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
  • 序言:七十年代末幕袱,一起剝皮案震驚了整個(gè)濱河市暴备,隨后出現(xiàn)的幾起案子,更是在濱河造成了極大的恐慌们豌,老刑警劉巖涯捻,帶你破解...
    沈念sama閱讀 212,294評(píng)論 6 493
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件,死亡現(xiàn)場(chǎng)離奇詭異望迎,居然都是意外死亡障癌,警方通過(guò)查閱死者的電腦和手機(jī),發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 90,493評(píng)論 3 385
  • 文/潘曉璐 我一進(jìn)店門(mén)辩尊,熙熙樓的掌柜王于貴愁眉苦臉地迎上來(lái)涛浙,“玉大人,你說(shuō)我怎么就攤上這事摄欲〗瘟粒” “怎么了?”我有些...
    開(kāi)封第一講書(shū)人閱讀 157,790評(píng)論 0 348
  • 文/不壞的土叔 我叫張陵胸墙,是天一觀的道長(zhǎng)我注。 經(jīng)常有香客問(wèn)我,道長(zhǎng)迟隅,這世上最難降的妖魔是什么但骨? 我笑而不...
    開(kāi)封第一講書(shū)人閱讀 56,595評(píng)論 1 284
  • 正文 為了忘掉前任励七,我火速辦了婚禮,結(jié)果婚禮上奔缠,老公的妹妹穿的比我還像新娘呀伙。我一直安慰自己,他們只是感情好添坊,可當(dāng)我...
    茶點(diǎn)故事閱讀 65,718評(píng)論 6 386
  • 文/花漫 我一把揭開(kāi)白布剿另。 她就那樣靜靜地躺著,像睡著了一般贬蛙。 火紅的嫁衣襯著肌膚如雪雨女。 梳的紋絲不亂的頭發(fā)上,一...
    開(kāi)封第一講書(shū)人閱讀 49,906評(píng)論 1 290
  • 那天阳准,我揣著相機(jī)與錄音氛堕,去河邊找鬼。 笑死野蝇,一個(gè)胖子當(dāng)著我的面吹牛讼稚,可吹牛的內(nèi)容都是我干的。 我是一名探鬼主播绕沈,決...
    沈念sama閱讀 39,053評(píng)論 3 410
  • 文/蒼蘭香墨 我猛地睜開(kāi)眼锐想,長(zhǎng)吁一口氣:“原來(lái)是場(chǎng)噩夢(mèng)啊……” “哼!你這毒婦竟也來(lái)了乍狐?” 一聲冷哼從身側(cè)響起赠摇,我...
    開(kāi)封第一講書(shū)人閱讀 37,797評(píng)論 0 268
  • 序言:老撾萬(wàn)榮一對(duì)情侶失蹤,失蹤者是張志新(化名)和其女友劉穎浅蚪,沒(méi)想到半個(gè)月后藕帜,有當(dāng)?shù)厝嗽跇?shù)林里發(fā)現(xiàn)了一具尸體,經(jīng)...
    沈念sama閱讀 44,250評(píng)論 1 303
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡惜傲,尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 36,570評(píng)論 2 327
  • 正文 我和宋清朗相戀三年洽故,在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片盗誊。...
    茶點(diǎn)故事閱讀 38,711評(píng)論 1 341
  • 序言:一個(gè)原本活蹦亂跳的男人離奇死亡时甚,死狀恐怖,靈堂內(nèi)的尸體忽然破棺而出浊伙,到底是詐尸還是另有隱情撞秋,我是刑警寧澤,帶...
    沈念sama閱讀 34,388評(píng)論 4 332
  • 正文 年R本政府宣布嚣鄙,位于F島的核電站吻贿,受9級(jí)特大地震影響,放射性物質(zhì)發(fā)生泄漏哑子。R本人自食惡果不足惜舅列,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 40,018評(píng)論 3 316
  • 文/蒙蒙 一肌割、第九天 我趴在偏房一處隱蔽的房頂上張望。 院中可真熱鬧帐要,春花似錦把敞、人聲如沸。這莊子的主人今日做“春日...
    開(kāi)封第一講書(shū)人閱讀 30,796評(píng)論 0 21
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽(yáng)。三九已至赠橙,卻和暖如春耽装,著一層夾襖步出監(jiān)牢的瞬間,已是汗流浹背期揪。 一陣腳步聲響...
    開(kāi)封第一講書(shū)人閱讀 32,023評(píng)論 1 266
  • 我被黑心中介騙來(lái)泰國(guó)打工掉奄, 沒(méi)想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留,地道東北人凤薛。 一個(gè)月前我還...
    沈念sama閱讀 46,461評(píng)論 2 360
  • 正文 我出身青樓姓建,卻偏偏與公主長(zhǎng)得像,于是被迫代替她去往敵國(guó)和親缤苫。 傳聞我的和親對(duì)象是個(gè)殘疾皇子速兔,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 43,595評(píng)論 2 350

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

  • 最近嘗試使用pathForResource:ofType的方式去取Bundle里的資源發(fā)現(xiàn)沒(méi)有取到,打印出來(lái)的路徑...
    丶Destinyxl閱讀 649評(píng)論 0 0
  • 關(guān)于人對(duì)事物的認(rèn)知主要有三個(gè)方面 將若干簡(jiǎn)單認(rèn)識(shí)組合為一個(gè)復(fù)合知識(shí)榨馁,由此產(chǎn)生出各種復(fù)雜的認(rèn)識(shí)憨栽。 將兩個(gè)認(rèn)識(shí)放在一起...
    kisslight閱讀 215評(píng)論 0 0
  • 前段時(shí)間辭職了帜矾,多了很多時(shí)間胡思亂想翼虫。思考的范圍包括但不僅限于,宇宙洪荒混沌之光屡萤,前途渺茫有點(diǎn)心慌……當(dāng)然子曾經(jīng)曰...
    Sheepy閱讀 1,015評(píng)論 5 2
  • 你小跑著追上車(chē) 回頭看我一眼 頭發(fā)被纏在嘴邊 我還是看到了遮不住的那抹笑 于是我也放下緊蹙的眉 予你一笑 馬路上我...
    酒溪閱讀 237評(píng)論 0 5