接下來(lái)就讓我們來(lái)一起學(xué)習(xí)如何實(shí)現(xiàn)幾個(gè)常用排序和搜索算法吧.

冒泡排序及其優(yōu)化

我們?cè)趯W(xué)排序算法時(shí), 最容易掌握的就是冒泡排序, 因?yàn)槠鋵?shí)現(xiàn)起來(lái)非常簡(jiǎn)單,但是從運(yùn)行性能的角度來(lái)看, 它卻是性能最差的一個(gè).

冒泡排序的實(shí)現(xiàn)思路是比較任何兩個(gè)相鄰的項(xiàng), 如果前者比后者大, 則將它們互換位置.

為了更方便的展示冒泡排序的過(guò)程和性能測(cè)試,筆者先寫(xiě)幾個(gè)工具方法,分別為動(dòng)態(tài)生成指定個(gè)數(shù)的隨機(jī)數(shù)組, 生成元素位置序列的方法,代碼如下:

有了以上兩個(gè)方法,我們就可以生成任意個(gè)數(shù)的數(shù)組以及數(shù)組項(xiàng)坐標(biāo)了,這兩個(gè)方法接下來(lái)我們會(huì)用到.

我們來(lái)直接寫(xiě)個(gè)乞丐版的冒泡排序算法:

接下來(lái)我們來(lái)測(cè)試一下, 我們用generateArr方法生成60個(gè)數(shù)組項(xiàng)的數(shù)組, 并動(dòng)態(tài)生成元素坐標(biāo):

接下來(lái)我們就可以測(cè)試我們上面寫(xiě)的冒泡排序了

可以看到數(shù)組已按照順序排好了,我們可以使用console.time來(lái)測(cè)量代碼執(zhí)行所用的時(shí)間,上面"乞丐版"冒泡排序耗時(shí)為0.2890625ms.

我們深入分析代碼就可以知道兩層for循環(huán)排序?qū)е铝撕芏喽嘤嗟呐判?如果我們從內(nèi)循環(huán)減去外循環(huán)中已跑過(guò)的輪數(shù),就可以避免內(nèi)循環(huán)中不必要的比較,所以我們代碼優(yōu)化如下:

經(jīng)過(guò)優(yōu)化的冒泡排序耗時(shí):0.279052734375ms, 比之前稍微好了一丟丟, 但仍然不是推薦的排序算法.

選擇排序

選擇排序的思路是找到數(shù)據(jù)結(jié)構(gòu)中的最小值并將其放置在第一位,接著找到第二個(gè)最小值并將其放到第二位,依次類(lèi)推.

我們還是按照之前的模式,生成一個(gè)60項(xiàng)的數(shù)組,

選擇排序代碼如下:

點(diǎn)擊排序時(shí), 代碼運(yùn)行正常, 可以實(shí)現(xiàn)排序, 控制臺(tái)耗時(shí)為: 0.13720703125ms, 明顯比冒泡排序性能要好.

插入排序

插入排序 的思路是每次排一個(gè)數(shù)組項(xiàng),假定第一項(xiàng)已經(jīng)排序,接著它和第二項(xiàng)比較, 決定第二項(xiàng)的位置, 然后接著用同樣的方式?jīng)Q定第三項(xiàng)的位置, 依次類(lèi)推, 最終將整個(gè)數(shù)組從小到大依次排序.

代碼如下:

執(zhí)行結(jié)果如下:

控制臺(tái)打印耗時(shí)為:0.09912109375ms.

歸并排序

歸并排序算法性能比以上三者都好, 可以在實(shí)際項(xiàng)目中投入使用,但實(shí)現(xiàn)方式相對(duì)復(fù)雜.

歸并排序是一種分治算法,其思想是將原始數(shù)組切分成較小的數(shù)組，直到每個(gè)小數(shù)組只有一個(gè)元素，接著將小數(shù)組歸并成較大的數(shù)組，最后變成一個(gè)排序完成的大數(shù)組。

為了實(shí)現(xiàn)該方法我們需要準(zhǔn)備一個(gè)合并函數(shù)和一個(gè)遞歸函數(shù)，具體實(shí)現(xiàn)如下代碼：

以上代碼中的遞歸作用是將一個(gè)大數(shù)組劃分為多個(gè)小數(shù)組直到只有一項(xiàng)，然后再逐層進(jìn)行合并排序。如果有不理解的可以和筆者交流或者結(jié)合筆者畫(huà)的草圖進(jìn)行理解。

快速排序

快速排序是目前比較常用的排序算法，它的復(fù)雜度為O(nlog^n),并且它的性能比其他復(fù)雜度為O(nlog^n)的好，也是采用分治的思想，將原始數(shù)組進(jìn)行劃分，由于快速排序?qū)崿F(xiàn)起來(lái)比較復(fù)雜，這里講一下思路： 1. 從數(shù)組中選擇中間項(xiàng)作為主元 2. 創(chuàng)建兩個(gè)指針，左邊一個(gè)指向數(shù)組第一項(xiàng)，右邊一個(gè)指向數(shù)組最后一項(xiàng)，移動(dòng)左指針直到我們找到一個(gè)比主元大的元素，移動(dòng)右指針直到找到一個(gè)比主元小的元素，然后交換它們的位置，重復(fù)此過(guò)程直到左指針超過(guò)了右指針 3. 算法對(duì)劃分后的小數(shù)組重復(fù)1，2步驟，直到數(shù)組完全排序完成。

代碼如下：

順序搜索

搜索算法也是我們經(jīng)常用到的算法之一，比如我們需要查找某個(gè)用戶(hù)或者某條數(shù)據(jù)，不管是在前端還是在后端，都會(huì)使用搜索算法。我們先來(lái)介紹最簡(jiǎn)單也是效率最低的順序搜索，其主要思想是將每一個(gè)數(shù)據(jù)結(jié)構(gòu)中的元素和我們要查詢(xún)的元素做比較，然后返回指定元素的索引。

之所以說(shuō)順序搜索效率低是因?yàn)槊看味家獜臄?shù)組的頭部開(kāi)始查詢(xún)，直到查找到要搜索的值，整體查詢(xún)不夠靈活和動(dòng)態(tài)性。順序搜索代碼實(shí)現(xiàn)如下：

接下來(lái)我們看下面一種比較常用和靈活的搜索算法——二分搜索。

二分搜索

二分搜索的思想有點(diǎn)“投機(jī)學(xué)”的意思，但是它是一種有理論依據(jù)的“投機(jī)學(xué)”。首先它要求被搜索的數(shù)據(jù)結(jié)構(gòu)已排序，其次進(jìn)行如下步驟： 1. 找出數(shù)組的中間值 2. 如果中間值是待搜索的值，那么直接返回中間值的索引 3. 如果待搜索的值比中間值小，則返回步驟1，將區(qū)間范圍縮小，在中間值左邊的子數(shù)組中繼續(xù)搜索 4. 如果待搜索的值比選中的值大，則返回步驟1，將區(qū)間范圍縮小，在中間值右邊的子數(shù)組中繼續(xù)搜索 5. 如果沒(méi)有搜到，則返回-1

由上圖大家可以很容易的理解二分搜索的實(shí)現(xiàn)過(guò)程，接下來(lái)我們看下代碼實(shí)現(xiàn)：

其實(shí)還有很多搜索算法，大家都可以自己去了解一下，最重要的就一定要記好咯！

寫(xiě)在最后：對(duì)于準(zhǔn)備學(xué)習(xí)C/C++編程的小伙伴，如果你想更好的提升你的編程核心能力（內(nèi)功）不妨從現(xiàn)在開(kāi)始！

微信公眾號(hào)：C語(yǔ)言編程學(xué)習(xí)基地

整理分享（多年學(xué)習(xí)的源碼、項(xiàng)目實(shí)戰(zhàn)視頻、項(xiàng)目筆記，基礎(chǔ)入門(mén)教程）

歡迎轉(zhuǎn)行和學(xué)習(xí)編程的伙伴，利用更多的資料學(xué)習(xí)成長(zhǎng)比自己琢磨更快哦！