成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

基本算法學(xué)習(xí)之(二)快速排序與歸并排序

Songlcy / 425人閱讀

摘要：快速排序看名字知特點(diǎn)就是快效率高它是處理大數(shù)據(jù)最快的排序算法之一奇妙的記憶點(diǎn)內(nèi)排序不穩(wěn)定基本思想通過一趟排序把待排序記錄分為獨(dú)立的兩部分其中一部分記錄的關(guān)鍵字都比另一部分的關(guān)鍵字笑則分別對(duì)兩部分繼續(xù)進(jìn)行排序以達(dá)到整個(gè)序列有序自己的理解其實(shí)就

快速排序(Quick Sort)

看名字知特點(diǎn),就是快,效率高.它是處理大數(shù)據(jù)最快的排序算法之一.
奇妙的記憶點(diǎn):

內(nèi)排序

不穩(wěn)定

基本思想

通過一趟排序把待排序記錄分為獨(dú)立的兩部分,其中一部分記錄的關(guān)鍵字都比另一部分的關(guān)鍵字笑,則分別對(duì)兩部分繼續(xù)進(jìn)行排序,以達(dá)到整個(gè)序列有序.
自己的理解:
其實(shí)就是用分治法的思路,將一個(gè)數(shù)組分為兩半,進(jìn)行無(wú)線分割排序.
首先在數(shù)列中取一個(gè)值,成為"關(guān)鍵字/基準(zhǔn)"(pivot);
然后比它小的放前面,大的放后面,相同的話隨便放.
遞歸的把我們分為兩半的數(shù)組再次分半排序.

快速排序(代碼) 
//方法一
function quickSort(array, left, right) {//傳入?yún)?shù)為數(shù)組,left,right為排序區(qū)域下標(biāo)
    console.time("1.快速排序耗時(shí)");
    if (Object.prototype.toString.call(array).slice(8, -1) === "Array" && typeof left === "number" && typeof right === "number") {//判斷傳入?yún)?shù)的正確性
        if (left < right) { //正確性判斷
            var x = array[right], i = left - 1, temp;//x變量為待排序數(shù)組末尾
            for (var j = left; j <= right; j++) {    //從左到右
                if (array[j] <= x) {
                    i++;//注意i先增在交換
                    temp = array[i];
                    array[i] = array[j];
                    array[j] = temp;
                }
            }
            quickSort(array, left, i - 1);
            quickSort(array, i + 1, right);
        }
        console.timeEnd("1.快速排序耗時(shí)");
        return array;
    } else {
        return "array is not an Array or left or right is not a number!";
    }
}

//方法二
var quickSort2 = function(arr) {
    console.time("2.快速排序耗時(shí)");
　　if (arr.length <= 1) { return arr; }
　　var pivotIndex = Math.floor(arr.length / 2);
　　var pivot = arr.splice(pivotIndex, 1)[0];
　　var left = [];
　　var right = [];
　　for (var i = 0; i < arr.length; i++){
　　　　if (arr[i] < pivot) {
　　　　　　left.push(arr[i]);
　　　　} else {
　　　　　　right.push(arr[i]);
　　　　}
　　}
console.timeEnd("2.快速排序耗時(shí)");
　　return quickSort2(left).concat([pivot], quickSort2(right));
};

var arr=[3,49,38,5,47,15,36,26,27,2,46,4,19,50,48];
console.log(quickSort(arr,0,arr.length-1));//[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]
console.log(quickSort2(arr));//[2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]
記憶點(diǎn)

best condition: T(n) = O(nlog n)

baddest condition: T(n) = O(n^2)

average condition: T(n) = O(nlog n)

歸并排序(Merge Sort)

不受輸入數(shù)據(jù)影響,但是表現(xiàn)比選擇排序好.代價(jià)是需要額外的內(nèi)存空間.
奇妙的記憶點(diǎn):

外排序(需要額外的內(nèi)存空間)

穩(wěn)定的排序算法(排序后元素原始順序不會(huì)變化)

基本思想:

分治法(Divide and Conquer)

將已有序的子序列合并,從而得到完全有序的序列.也稱為2-路歸并.

歸并排序:代碼 
function mergeSort(arr) {  //采用自上而下的遞歸方法
    var len = arr.length; //獲取傳入數(shù)組的長(zhǎng)度
    if(len < 2) {   //如果為單個(gè)元素則直接返回
        return arr;
    }
    var middle = Math.floor(len / 2),//取中點(diǎn)
        left = arr.slice(0, middle), //取左邊區(qū)間
        right = arr.slice(middle);   //取右邊區(qū)間
    return merge(mergeSort(left), mergeSort(right));//調(diào)用歸并函數(shù)
}

function merge(left, right)//傳入兩個(gè)區(qū)間
{
    var result = [];//新建變量用于保存結(jié)果
    console.time("歸并排序耗時(shí)");
    while (left.length && right.length) { //當(dāng)左區(qū)間右區(qū)間存在時(shí)
        if (left[0] <= right[0]) {  //將區(qū)間中較小的一位從區(qū)間數(shù)組中放到結(jié)果數(shù)組中.
            result.push(left.shift());
        } else {
            result.push(right.shift());
        }
    }
    //下面兩個(gè)while是為了解決遺留元素問題
    while (left.length) 
        result.push(left.shift());

    while (right.length)
        result.push(right.shift());
    console.timeEnd("歸并排序耗時(shí)");
    return result;//返回結(jié)果
}
var arr=[3,44,38,5,47,15,36,26,27,2,46,4,19,50,48];
console.log(mergeSort(arr));
/*10次歸并
歸并排序耗時(shí): 0ms
歸并排序耗時(shí): 0ms
歸并排序耗時(shí): 0ms
歸并排序耗時(shí): 0ms
歸并排序耗時(shí): 0ms
歸并排序耗時(shí): 0ms
歸并排序耗時(shí): 0ms
歸并排序耗時(shí): 0ms
歸并排序耗時(shí): 0ms
歸并排序耗時(shí): 0ms
[ 2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50 ]      */
記憶點(diǎn)

best condition: T(n) = O(n)

baddest condition: T(n) = O(nlog n)

average condition: T(n) = O(nlog n)

文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/80445.html

相關(guān)文章

  • 基礎(chǔ)算法學(xué)習(xí)之(三):堆排序

    摘要：奇妙的記憶點(diǎn)不穩(wěn)定內(nèi)排序基本思想分為兩步建堆與維持堆的性質(zhì)首先我們要先理解堆是什么東西堆其實(shí)就是一個(gè)完全二叉樹我們可以使用順序表存儲(chǔ)一個(gè)二叉樹如下圖所示來(lái)存儲(chǔ)其中分為最大堆最小堆而最大堆就是上頭大下頭小最小堆則反之明白了堆的定義我們就可以開 奇妙的記憶點(diǎn): 不穩(wěn)定 內(nèi)排序 基本思想: 分為兩步,建堆與維持堆的性質(zhì),首先我們要先理解堆是什么東西.堆其實(shí)就是一個(gè)完全二叉樹,我們可以使用...

    mrli2016 評(píng)論0 收藏0

  • 排序算法（Java）——那些年面試常見的排序算法

    摘要：下面會(huì)介紹的一種排序算法快速排序甚至被譽(yù)為世紀(jì)科學(xué)和工程領(lǐng)域的十大算法之一。我們將討論比較排序算法的理論基礎(chǔ)并中借若干排序算法和優(yōu)先隊(duì)列的應(yīng)用。為了展示初級(jí)排序算法性質(zhì)的價(jià)值，我們來(lái)看一下基于插入排序的快速的排序算法希爾排序。 前言 　　排序就是將一組對(duì)象按照某種邏輯順序重新排列的過程。比如信用卡賬單中的交易是按照日期排序的——這種排序很可能使用了某種排序算法。在計(jì)算時(shí)代早期，大家普遍...

    Harpsichord1207 評(píng)論0 收藏0

  • 歸并排序 - Algorithms, Part I, week 3 MERGESORTS

    摘要：兩個(gè)單元素?cái)?shù)組的合并實(shí)際就是對(duì)這兩個(gè)數(shù)進(jìn)行了排序，即變?yōu)?，同樣再?duì)后一組的兩個(gè)數(shù)歸并排序，即變?yōu)?，再將兩單元?shù)組歸并成四單元數(shù)組即和歸并為。 前言 本周講解兩個(gè)50多年前發(fā)明，但今天仍然很重要的經(jīng)典算法 (歸并排序和快速排序) 之一 -- 歸并排序，幾乎每個(gè)軟件系統(tǒng)中都可以找到其中一個(gè)或兩個(gè)的實(shí)現(xiàn)，并研究這些經(jīng)典方法的新變革。我們的涉及范圍從數(shù)學(xué)模型中解釋為什么這些方法有效到使這些算法...

    Jokcy 評(píng)論0 收藏0

  • 各種排序算法總結(jié)

    摘要：排序算法是最基本最常用的算法，不同的排序算法在不同的場(chǎng)景或應(yīng)用中會(huì)有不同的表現(xiàn)，我們需要對(duì)各種排序算法熟練才能將它們應(yīng)用到實(shí)際當(dāng)中，才能更好地發(fā)揮它們的優(yōu)勢(shì)。今天，來(lái)總結(jié)下各種排序算法。 排序算法是最基本最常用的算法，不同的排序算法在不同的場(chǎng)景或應(yīng)用中會(huì)有不同的表現(xiàn)，我們需要對(duì)各種排序算法熟練才能將它們應(yīng)用到實(shí)際當(dāng)中，才能更好地發(fā)揮它們的優(yōu)勢(shì)。今天，來(lái)總結(jié)下各種排序算法。 下面這個(gè)表格...

    null1145 評(píng)論0 收藏0

發(fā)表評(píng)論

0條評(píng)論

閱讀需要支付1元查看
<