算法(五)--階段思考

這短時(shí)間學(xué)習(xí)了各種基本排序算法军熏。我們來捋一捋這些算法度硝。
選擇和冒泡排序:
大多數(shù)人最先接觸的排序凌简,因?yàn)楹美斫馍涎祝谔幚頂?shù)據(jù)量不大的情況也能很好的應(yīng)對(duì)。
插入排序
插入排序和選擇排序的區(qū)別就是插入排序可以提前結(jié)束雏搂。
執(zhí)行時(shí) 插入排序比選擇排序慢 因?yàn)椴煌5慕粨Q位置比較耗時(shí)藕施,可以優(yōu)化。
但是對(duì)于一個(gè)近乎有序的數(shù)組進(jìn)行排序凸郑,插入排序性能要遠(yuǎn)遠(yuǎn)優(yōu)于選擇排序
所以插入排序是很有實(shí)際意義的裳食。(例如我們?cè)诓槿罩镜臅r(shí)候,要按時(shí)間排序芙沥,因?yàn)榕紶柕膯栴}導(dǎo)致個(gè)別不是按時(shí)間的 這個(gè)時(shí)候插入排序的優(yōu)勢(shì)就能完全發(fā)揮出來了)
歸并和快速排序:
歸并算法和快速排序的算法都采用了分治算法的思想:
顧名思義诲祸。分而治之浊吏,就是將原有問題分割成同等結(jié)構(gòu)的子問題。之后將子問題逐一解決后救氯,原問題也就解決找田。
快排學(xué)習(xí)了之后我們能解決那些問題呢?
例如我們要知道一個(gè)值在數(shù)組排好序之后的位置径密。
我們只需要稍微改一下快速排序就可以很快的實(shí)現(xiàn):

/**
 * 查詢數(shù)組中排在第m位的值
 * @param {*查詢的數(shù)組} arr 
 * @param {* 數(shù)組長(zhǎng)度} n
 * @param {* 查詢的下標(biāo)+1} m //查詢數(shù)組的第多少位
 */
this.selectionOne = (arr, n, m) => {
    var _this = this
    __quickSort(arr, 0, n - 1, m)
    function __quickSort(arr, l, r, m) {
        if (l >= r) {
            return
        }
        //基本上所有的高級(jí)排序在底層都可以采用插入排序進(jìn)行優(yōu)化
        // if (r - l <= 10) {
        //     _this.insertionSort2(arr, l, r)
        //     return
        // }
        let p = __partition(arr, l, r)
        if (p > m) {
            __quickSort(arr, l, p - 1, m)
        } else if (p < m) {
            __quickSort(arr, p + 1, r, m)
        } else {
            log(arr[p])
        }

    }
    //對(duì)arr進(jìn)行partition操作返回一個(gè)索引下標(biāo) p
    //滿足 arr[l,p1]里面所有的值都小于 arr[p] , arr[p+1,r]里面所有的值都大于 arr[p]
    function __partition(arr, l, r) {
        let n = Math.floor(Math.random() * (r - l + 1) + l, 10)
        swap(arr, l, n)
        let v = arr[l]
        let i = l + 1, p = r
        while (true) {
            while (i <= r && arr[i] < v) {
                i++
            }
            while (p >= l + 1 && arr[p] > v) {
                p--
            }
            if (i > p) {
                break
            }
            swap(arr, i, p)
            i++
            p--
        }
        swap(arr, l, p)
        return p
    }
}

下面我們說一下數(shù)組打亂:
方法一:

[12,4,16,3].sort(function() {
        return .5 - Math.random();
});

該方法打亂數(shù)組不是完全的午阵,根據(jù)網(wǎng)上資料:
chrome v8引擎 在處理 sort 方法時(shí),使用了插入排序和快排兩種方案享扔。
當(dāng)目標(biāo)數(shù)組長(zhǎng)度小于10時(shí)底桂,使用插入排序;反之惧眠,使用快排

Math.random 的隨機(jī)數(shù)生成器和 java 一樣以當(dāng)前時(shí)間為隨機(jī)數(shù)種子
這樣在測(cè)試數(shù)據(jù)很大的時(shí)候會(huì)導(dǎo)致打亂的不是很均勻籽懦。
方法二:
稱之為洗牌算法:

this.shuffle = (arr, n) => {
    for (let i = 1; i < arr.length; i++) {
        const random = Math.floor(Math.random() * (i + 1));
        [arr[i], arr[random]] = [arr[random], arr[i]];
    }
    return arr;
};

順序拿到數(shù)組中的一位,和數(shù)組中隨機(jī)一位進(jìn)行換位氛魁,保證每個(gè)位置都被打亂過暮顺。

以上都是個(gè)人理解如有不對(duì)之處還望指正交流!

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
  • 序言:七十年代末秀存,一起剝皮案震驚了整個(gè)濱河市捶码,隨后出現(xiàn)的幾起案子,更是在濱河造成了極大的恐慌或链,老刑警劉巖惫恼,帶你破解...
    沈念sama閱讀 222,807評(píng)論 6 518
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件,死亡現(xiàn)場(chǎng)離奇詭異澳盐,居然都是意外死亡祈纯,警方通過查閱死者的電腦和手機(jī),發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 95,284評(píng)論 3 399
  • 文/潘曉璐 我一進(jìn)店門叼耙,熙熙樓的掌柜王于貴愁眉苦臉地迎上來腕窥,“玉大人,你說我怎么就攤上這事筛婉〈乇” “怎么了?”我有些...
    開封第一講書人閱讀 169,589評(píng)論 0 363
  • 文/不壞的土叔 我叫張陵爽撒,是天一觀的道長(zhǎng)冕碟。 經(jīng)常有香客問我,道長(zhǎng)匆浙,這世上最難降的妖魔是什么? 我笑而不...
    開封第一講書人閱讀 60,188評(píng)論 1 300
  • 正文 為了忘掉前任厕妖,我火速辦了婚禮首尼,結(jié)果婚禮上,老公的妹妹穿的比我還像新娘。我一直安慰自己软能,他們只是感情好迎捺,可當(dāng)我...
    茶點(diǎn)故事閱讀 69,185評(píng)論 6 398
  • 文/花漫 我一把揭開白布。 她就那樣靜靜地躺著查排,像睡著了一般凳枝。 火紅的嫁衣襯著肌膚如雪。 梳的紋絲不亂的頭發(fā)上跋核,一...
    開封第一講書人閱讀 52,785評(píng)論 1 314
  • 那天岖瑰,我揣著相機(jī)與錄音,去河邊找鬼砂代。 笑死蹋订,一個(gè)胖子當(dāng)著我的面吹牛,可吹牛的內(nèi)容都是我干的刻伊。 我是一名探鬼主播露戒,決...
    沈念sama閱讀 41,220評(píng)論 3 423
  • 文/蒼蘭香墨 我猛地睜開眼,長(zhǎng)吁一口氣:“原來是場(chǎng)噩夢(mèng)啊……” “哼捶箱!你這毒婦竟也來了智什?” 一聲冷哼從身側(cè)響起,我...
    開封第一講書人閱讀 40,167評(píng)論 0 277
  • 序言:老撾萬榮一對(duì)情侶失蹤丁屎,失蹤者是張志新(化名)和其女友劉穎荠锭,沒想到半個(gè)月后,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體悦屏,經(jīng)...
    沈念sama閱讀 46,698評(píng)論 1 320
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡节沦,尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 38,767評(píng)論 3 343
  • 正文 我和宋清朗相戀三年,在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了础爬。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片甫贯。...
    茶點(diǎn)故事閱讀 40,912評(píng)論 1 353
  • 序言:一個(gè)原本活蹦亂跳的男人離奇死亡,死狀恐怖看蚜,靈堂內(nèi)的尸體忽然破棺而出叫搁,到底是詐尸還是另有隱情,我是刑警寧澤供炎,帶...
    沈念sama閱讀 36,572評(píng)論 5 351
  • 正文 年R本政府宣布渴逻,位于F島的核電站,受9級(jí)特大地震影響音诫,放射性物質(zhì)發(fā)生泄漏惨奕。R本人自食惡果不足惜,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 42,254評(píng)論 3 336
  • 文/蒙蒙 一竭钝、第九天 我趴在偏房一處隱蔽的房頂上張望梨撞。 院中可真熱鬧雹洗,春花似錦、人聲如沸卧波。這莊子的主人今日做“春日...
    開封第一講書人閱讀 32,746評(píng)論 0 25
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽港粱。三九已至螃成,卻和暖如春,著一層夾襖步出監(jiān)牢的瞬間查坪,已是汗流浹背寸宏。 一陣腳步聲響...
    開封第一講書人閱讀 33,859評(píng)論 1 274
  • 我被黑心中介騙來泰國打工, 沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留咪惠,地道東北人击吱。 一個(gè)月前我還...
    沈念sama閱讀 49,359評(píng)論 3 379
  • 正文 我出身青樓,卻偏偏與公主長(zhǎng)得像遥昧,于是被迫代替她去往敵國和親覆醇。 傳聞我的和親對(duì)象是個(gè)殘疾皇子,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 45,922評(píng)論 2 361

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