Java語(yǔ)法 | 排序算法入門
前言
C： 在這個(gè)時(shí)代，算法，雖說(shuō)不是家喻戶曉吧，但也算是大多數(shù)人常掛在嘴上的新名詞。
諸如：美顏算法、人臉識(shí)別算法、推薦算法、壓縮算法 .... ，我們也會(huì)經(jīng)常聽(tīng)到有人在感嘆算法的強(qiáng)大。
"好厲害??！我就在x寶看了看書包，然后一大堆書包推薦就來(lái)了。"（推薦算法）
"拍照記得給我開(kāi)美顏?。?！"（美顏算法）
我們?cè)谇皟善腴T了數(shù)據(jù)結(jié)構(gòu)，數(shù)據(jù)結(jié)構(gòu)和算法不分家，本篇，查老師帶你入門一下算法。
算法簡(jiǎn)介
算法概述
那何謂算法呢？
算法（Algorithm）是指解題方案的準(zhǔn)確而完整的描述，是一系列解決問(wèn)題的清晰指令，算法代表著用系統(tǒng)的方法描述解決問(wèn)題的策略機(jī)制。也就是說(shuō)，能夠?qū)σ欢ㄒ?guī)范的輸入，在有限時(shí)間內(nèi)獲得所要求的輸出。不同的算法可能用不同的時(shí)間、空間或效率來(lái)完成同樣的任務(wù)。一個(gè)算法的優(yōu)劣可以用空間復(fù)雜度與時(shí)間復(fù)雜度來(lái)衡量 。 [1]
想理解什么是算法，我們要先設(shè)想一個(gè)場(chǎng)景。幾千年前，一位祖先憑著他對(duì)已故祖母如何做面包的記憶，嘗試自己做面包。但是，他真的不知道該怎么做。他猶豫著，一開(kāi)始先將麥仁放入沸水中，然后對(duì)自己說(shuō)，這也許是個(gè)糟糕的想法。這位祖先的困境，正是我們都會(huì)面臨的情況——遇到某一個(gè)問(wèn)題，卻又不知道該如何解決。我們想著解決方法，去嘗試，反復(fù)探索實(shí)驗(yàn)，順便有了一點(diǎn)點(diǎn)意外發(fā)現(xiàn)，直至成功……或者失敗。
然而，真正的面包師并不是這樣做的。他們不會(huì)給每爐面包都重制一個(gè)烘焙食譜，因?yàn)樗麄円呀?jīng)掌握并牢記了面包的烘焙方法。多虧了面包食譜，面包師可以每天給我們提供面包。事實(shí)上，人類文明的發(fā)展不僅源于有些人的發(fā)明創(chuàng)造，也因?yàn)榱碛腥恕皬?fù)制”了這些發(fā)明，才使其得以改進(jìn)。
但是，我們忘卻了面包食譜的寶貴之處。首先，食譜降低了不確定性：多虧了它，面包師知道，除非突遭一場(chǎng)災(zāi)難，否則面包將會(huì)在晚餐時(shí)準(zhǔn)備好。有了這個(gè)食譜，不需要什么想象力或是天賦，任何人都可以做面包。就拿兩位作者來(lái)說(shuō)，我們對(duì)面包烘焙沒(méi)有任何天賦，但仍可以從網(wǎng)頁(yè)上找到恰巴提的食譜，運(yùn)用適當(dāng)?shù)暮兔媪Χ?，借助更富有想象力和才華的面包師們寫下的方法，做出面包。最終，這個(gè)食譜成為了人類遺產(chǎn)中的一部分，在幾千年的歷史長(zhǎng)河中，代代相傳。
食譜就是一個(gè)算法，我們就此有了“算法”概念的初步定義：一個(gè)算法是解決一個(gè)問(wèn)題的進(jìn)程。我們并不需要每次都發(fā)明一個(gè)解決方案。
從這個(gè)定義不難看出，自人類歷史初期，我們就一直在發(fā)明、使用和傳播著各種各樣的“算法”，用來(lái)烹飪、雕琢石器、釣魚、種植扁豆及小麥，等等。[2]
查老師有話說(shuō)： 按照查老師來(lái)理解，算法就是為了解決某個(gè)具體需求而提供的解題方法。在之后學(xué)習(xí)工作中，用別人寫的算法，寫自己的業(yè)務(wù)算法都是家常便飯，不用把它理解的過(guò)于抽象和高大上。
了解更多，請(qǐng)點(diǎn)擊：https://www.bilibili.com/video/BV1az4y1S74b
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??https://www.bilibili.com/video/BV1NX4y1T71W
排序算法
排序算法無(wú)論是生活中，還是在算法啟蒙中都扮有非常重要的角色，而且在面試的時(shí)候，大廠最愛(ài)的就是各種排序算法的思想或代碼手寫。
所謂排序算法，即通過(guò)特定的算法因式將一組或多組數(shù)據(jù)按照既定模式進(jìn)行重新排序。這種新序列遵循著一定的規(guī)則，體現(xiàn)出一定的規(guī)律，因此，經(jīng)處理后的數(shù)據(jù)便于篩選和計(jì)算，大大提高了計(jì)算效率。對(duì)于排序，我們首先要求其具有一定的穩(wěn)定性，即當(dāng)兩個(gè)相同的元素同時(shí)出現(xiàn)于某個(gè)序列之中，則經(jīng)過(guò)一定的排序算法之后，兩者在排序前后的相對(duì)位置不發(fā)生變化。換言之，即便是兩個(gè)完全相同的元素，它們?cè)谂判蜻^(guò)程中也是各有區(qū)別的，不允許混淆不清。[3]
排序算法也有很多種解決思路，常見(jiàn)的有：冒泡排序、選擇排序、插入排序、快速排序、堆排序、歸并排序、希爾排序、基數(shù)排序等。
接下來(lái)，查老師將帶你入門三種排序算法，也算是對(duì)我們小白入門數(shù)據(jù)結(jié)構(gòu)的一個(gè)補(bǔ)充部分，不過(guò)在本篇查老師不會(huì)帶你去介紹算法的時(shí)間復(fù)雜度及空間復(fù)雜度等內(nèi)容，僅僅是對(duì)排序思想和基本實(shí)現(xiàn)做一個(gè)介紹。
了解更多，請(qǐng)點(diǎn)擊：https://www.bilibili.com/video/BV1az4y1S74b
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??https://www.bilibili.com/video/BV1NX4y1T71W
冒泡排序
概述
冒泡排序可以說(shuō)是排序算法中最為簡(jiǎn)單的一種。
它重復(fù)地走訪過(guò)要排序的元素列，依次比較兩個(gè)相鄰的元素，如果順序（如從大到小、首字母從Z到A）錯(cuò)誤就把他們交換過(guò)來(lái)。走訪元素的工作是重復(fù)地進(jìn)行直到?jīng)]有相鄰元素需要交換，也就是說(shuō)該元素列已經(jīng)排序完成。
這個(gè)算法的名字由來(lái)是因?yàn)樵叫〉脑貢?huì)經(jīng)由交換慢慢“浮”到數(shù)列的頂端（升序或降序排列），就如同碳酸飲料中二氧化碳的氣泡最終會(huì)上浮到頂端一樣（這是因?yàn)榻M成小氣泡的二氧化碳比水要輕，所以小氣泡可以一點(diǎn)一點(diǎn)向上浮動(dòng)。），故名“冒泡排序”。[4]
了解更多，請(qǐng)點(diǎn)擊：https://www.bilibili.com/video/BV1az4y1S74b
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??https://www.bilibili.com/video/BV1NX4y1T71W
排序思想
核心思想： 相鄰元素做比較，兩兩比較小靠前。
將相鄰的兩個(gè)元素進(jìn)行比較，比較完后，按照元素大小進(jìn)行移位，小的移動(dòng)到前面，大的移動(dòng)到后面。
每一輪比較完后，"最大的元素" 將被移位到最后。在下一輪比較的時(shí)候，這個(gè) "最大的元素" 就不需要再參與比較了。
重復(fù)進(jìn)行上述步驟，經(jīng)過(guò) N - 1 輪比較之后，排序完成。（N：代表的是要比較的元素個(gè)數(shù)）
代碼實(shí)現(xiàn)
了解更多，請(qǐng)點(diǎn)擊：https://www.bilibili.com/video/BV1az4y1S74b
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??https://www.bilibili.com/video/BV1NX4y1T71W
選擇排序
概述
它是一種簡(jiǎn)單直觀的排序算法。
它的工作原理是：第一次從待排序的數(shù)據(jù)元素中選出最小（或最大）的一個(gè)元素，存放在序列的起始位置，然后再?gòu)氖Ｓ嗟奈磁判蛟刂袑ふ业阶钚。ù螅┰?，然后放到已排序的序列的末尾?/p>
以此類推，直到全部待排序的數(shù)據(jù)元素的個(gè)數(shù)為零。選擇排序是不穩(wěn)定的排序方法。[5]
排序思想
核心思想： 打擂臺(tái)求最小值思路。
第一次比較的時(shí)候，先將 "第一個(gè)元素" 假定為最小元素值。
然后將第一個(gè)元素依次和后面的所有元素進(jìn)行比較大小，如果后面的元素比第一個(gè)元素小，則進(jìn)行交換。
每一輪比較完后，"最小的元素" 將被移位到 "第一個(gè)元素位置"。在下一輪比較的時(shí)候，這個(gè) "最小的元素" 就不需要再參與比較了。
重復(fù)的進(jìn)行上面步驟，經(jīng)過(guò) N - 1 輪比較之后，排序完成。（N：代表的是要比較的元素個(gè)數(shù)）
代碼實(shí)現(xiàn)
查老師有話說(shuō)： 在選擇排序中，包含了我們前面所學(xué)到的打擂臺(tái)求最大值、最小值思路，可以回顧一下。
了解更多，請(qǐng)點(diǎn)擊：https://www.bilibili.com/video/BV1az4y1S74b
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??https://www.bilibili.com/video/BV1NX4y1T71W
插入排序
概述
一般也被稱為直接插入排序。對(duì)于少量元素的排序，它是一個(gè)有效的算法 。
插入排序是一種最簡(jiǎn)單的排序方法，它的基本思想是將一個(gè)記錄插入到已經(jīng)排好序的有序表中，從而一個(gè)新的、記錄數(shù)增1的有序表。在其實(shí)現(xiàn)過(guò)程使用雙層循環(huán)，外層循環(huán)對(duì)除了第一個(gè)元素之外的所有元素，內(nèi)層循環(huán)對(duì)當(dāng)前元素前面有序表進(jìn)行待插入位置查找，并進(jìn)行移動(dòng)。[6]
排序思想
核心思想： 在有序數(shù)列中做插入，并保持住有序。
首先將第一個(gè)元素就看作是一個(gè)已經(jīng)排序好的數(shù)列，后面的其他元素則看作未排序數(shù)列。
{{a1}, {a2, a3, a4, ..., an}}然后將第二個(gè)元素在已經(jīng)排序好的數(shù)列中，做插入動(dòng)作。即在已經(jīng)排序好的數(shù)列中，從后向前依次查找符合升序規(guī)律的位置，并插入到該位置。
這樣新的已經(jīng)排序好的數(shù)列就變?yōu)榱耍?code>{{a1, a2}, {a3, a4, ..., an}}
重復(fù)這個(gè)步驟，直到排序結(jié)束。
代碼實(shí)現(xiàn)
后記
C： 好了，排序算法入門的介紹也就到這兒結(jié)束了，本篇的作業(yè)請(qǐng)微信搜索關(guān)注： 查老師的講義 ，然后回復(fù) 排序算法入門作業(yè) 即可。
我們?cè)诒酒醪街v解了目前這個(gè)階段你能學(xué)得會(huì)，且在算法基礎(chǔ)中最為熟知的三種排序算法，但僅僅上述這些排序算法，就已經(jīng)讓我們感受到了計(jì)算機(jī)科學(xué)家們的心血結(jié)晶。
它們各有各的特點(diǎn)，各有各的精妙之處，想要玩轉(zhuǎn)它們，還需要我們多多花費(fèi)一些時(shí)間。
查老師有話說(shuō)： 對(duì)于技術(shù)的學(xué)習(xí)，查老師一貫遵循的步驟是：先用最最簡(jiǎn)單的 demo 讓它跑起來(lái)，然后學(xué)學(xué)它的最最常用 API 和 配置讓自己能用起來(lái)，最后熟練使用的基礎(chǔ)上，在空閑時(shí)嘗試閱讀它的源碼讓自己能夠洞徹它的運(yùn)行機(jī)制，部分問(wèn)題出現(xiàn)的原因，同時(shí)借鑒這些技術(shù)實(shí)現(xiàn)來(lái)提升自己的代碼高度。
了解更多，請(qǐng)點(diǎn)擊：https://www.bilibili.com/video/BV1az4y1S74b
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??https://www.bilibili.com/video/BV1NX4y1T71W
作者：查老師
鏈接：https://juejin.cn/post/6919983151066382349
來(lái)源：掘金
著作權(quán)歸作者所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系作者獲得授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。
