問(wèn)題7 排序

?很多時(shí)候，如果集合中的數(shù)據(jù)是有序的，處理效率會(huì)比無(wú)序時(shí)高得多，所以排序（就是讓數(shù)據(jù)集有序排列的過(guò)程）的重要性不容置疑，因?yàn)榕判蚴褂妙H為頻繁，同事數(shù)據(jù)集的規(guī)模越來(lái)越大，因此排序過(guò)程的效率尤為重要。

?

對(duì)排序的研究，在計(jì)算機(jī)出現(xiàn)以前就頗有研究。隨著計(jì)算機(jī)應(yīng)用領(lǐng)域的廣泛，排序算法在計(jì)算機(jī)實(shí)現(xiàn)也是最早被研究和實(shí)現(xiàn)的一類(lèi)算法。

?

排序問(wèn)題是一個(gè)非數(shù)值問(wèn)題（查找也是一個(gè)非數(shù)值問(wèn)題），排序的邏輯（排序的實(shí)現(xiàn)方法）不是一個(gè)數(shù)值過(guò)程，或者說(shuō)不是一個(gè)數(shù)學(xué)方法，無(wú)需什么數(shù)學(xué)基礎(chǔ)或數(shù)學(xué)思維。

?

排序算法和程序，更多的是涉及算法邏輯、程序和數(shù)據(jù)結(jié)構(gòu)的知識(shí)。當(dāng)然，一個(gè)正常的人類(lèi)，只有有一定的經(jīng)驗(yàn)和能力，在日常的生活中都會(huì)排序，不過(guò)要能夠理解和掌握高效的排序算法，實(shí)現(xiàn)高效的排序程序還是需要專(zhuān)門(mén)的學(xué)習(xí)和實(shí)踐的。實(shí)話(huà)實(shí)說(shuō)，很多先進(jìn)的排序算法不是一般人能夠想出來(lái)的。當(dāng)然，學(xué)習(xí)先進(jìn)的排序算法，一般人都可以。

?

本章首先介紹了一個(gè)來(lái)源于生活的冒泡排序算法，這個(gè)算法的邏輯其實(shí)不用學(xué)，很多人都會(huì)。如果真的學(xué)習(xí)排序，就會(huì)知道這個(gè)算法本身是沒(méi)有什么實(shí)用價(jià)值的，因?yàn)樗且环N最沒(méi)有效率的方法。書(shū)中給了一個(gè)簡(jiǎn)要的說(shuō)明，如果在特定計(jì)算環(huán)境下對(duì)100萬(wàn)個(gè)數(shù)據(jù)排序，某個(gè)先進(jìn)的算法（比如書(shū)中介紹的另一個(gè)算法）需要1S，那冒泡排序算法可能需要10h以上，我以前上課時(shí)，講排序，就是一開(kāi)始運(yùn)行兩個(gè)程序（一個(gè)是冒泡，一個(gè)是快排），然后到了下課，快排程序早結(jié)束了，而冒泡排序程序還在執(zhí)行中。

?

本章還介紹了經(jīng)典的先進(jìn)排序—快速排序和合并排序（也叫歸并排序）。

以及簡(jiǎn)要介紹了排序問(wèn)題的下界（或者稱(chēng)為下限，這是一個(gè)計(jì)算機(jī)領(lǐng)域的專(zhuān)有名詞）

?

【作者感受】

排序問(wèn)題和排序算法研究和使用的歷史悠久，現(xiàn)在還有人再研究和設(shè)計(jì)新的排序算法，但是對(duì)一般人來(lái)說(shuō)，更多的使用排序。因?yàn)闅v史上，已經(jīng)有很多先進(jìn)高效的排序算法被發(fā)明和設(shè)計(jì)出來(lái)了。

現(xiàn)在，學(xué)習(xí)排序算法，我個(gè)人覺(jué)得更多的是訓(xùn)練計(jì)算思維。通過(guò)學(xué)習(xí)各種排序算法，設(shè)計(jì)的邏輯，在程序和數(shù)據(jù)結(jié)構(gòu)方面設(shè)計(jì)的技巧，分析排序方法的性能，都是很好的訓(xùn)練計(jì)算思維的教學(xué)素材。