国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

學(xué)習(xí)經(jīng)典算法—JavaScript篇(一)排序算法

remcarpediem / 1619人閱讀

摘要:對每一對相鄰元素作同樣的工作,從開始第一對一直到結(jié)尾的最后一對,如此將最大的數(shù)放在后面。持續(xù)每次對元素重復(fù)上面的步驟,直到排序完成。排序步驟將第一待排序序列第一個元素看做一個有序序列,把第二個元素到最后一個元素當(dāng)成是未排序序。

前端攻城獅——學(xué)習(xí)常用的排序算法 一、冒泡排序

優(yōu)點(diǎn):

所有排序中最簡單的,易于理解;

缺點(diǎn):

時間復(fù)雜度O(n^2),平均來說是最差的一種排序方式;

因?yàn)樵谀J(rèn)情況下,對于已經(jīng)排好序的部分,此排序任然會進(jìn)行比較(當(dāng)然可以進(jìn)行改進(jìn)優(yōu)化)

算法步驟:

比較相鄰的元素,如果第一個比第二個大,就交換他們兩個。

對每一對相鄰元素作同樣的工作,從開始第一對一直到結(jié)尾的最后一對,如此將最大的數(shù)放在后面。

對所有的元素重復(fù)以上的步驟,除了最后一個。

持續(xù)每次對元素重復(fù)上面的步驟,直到排序完成。

原理分析:

通過比較兩個相鄰的項(xiàng),(由小到大排序)如果第一個比的二個大,則交換它們的位置元素項(xiàng)向上移動至正確的順序,就好像氣泡升至表面,冒泡也因此得名。

const bubbleSort = (arr) => {
    const length= arr.length;
    for (let i = 0; i arr[j+1]){
                let swap = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = swap;
            }
        }
    }
}

改進(jìn)優(yōu)化:

默認(rèn)上述代碼,對于第一輪之后的循環(huán)任然會進(jìn)行和全部元素的比較,但其實(shí)之前的循環(huán)已經(jīng)將器排序正確了,所以可以從內(nèi)循環(huán)中減去外循環(huán)已經(jīng)進(jìn)行過的輪數(shù),從而避免不必要的比較

const bubbleSort = (arr) => {
        const length= arr.length;
        for (let i = 0; i arr[j+1]){
                    let swap = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = swap;
                }
            }
        }
    }

二、選擇排序

原理:

進(jìn)行原地址比較,找到數(shù)據(jù)結(jié)構(gòu)中最小值并放在第一位,接著在剩下的中找到第二個最小值放在第二位,依次類推;

代碼實(shí)現(xiàn):

function selectionSort(arr) {
    var length= arr.length;
    var minIndex;
    for (var i = 0; i < length - 1; i++) {
        minIndex = i;
        for (var j = i + 1; j < length; j++) {
            if (arr[j] < arr[minIndex]) {     // 尋找最小的數(shù)
                minIndex = j;                 // 將最小數(shù)的索引保存
            }
        }
        if(i != minIndex){
            var temp = arr[i];
            arr[i] = arr[minIndex];
            arr[minIndex] = temp;  
        }
        
    }
    return arr;
}

三、插入排序

原理:

通過構(gòu)建有序序列,對于未排序數(shù)據(jù),在已排序序列中從后向前掃描,找到相應(yīng)位置并插入。

排序步驟:

將第一待排序序列第一個元素看做一個有序序列,把第二個元素到最后一個元素當(dāng)成是未排序序。

從頭到尾依次掃描未排序序列,將掃描到的每個元素插入有序序列的適當(dāng)位置。(如果待插入的元素與有序序列中的某個元素相等,則將待插入元素插入到相等元素的后面。)

代碼實(shí)現(xiàn)

function insertionSort(arr) {
    var len = arr.length;
    var preIndex, current;
    for (var i = 1; i < len; i++) {
        preIndex = i - 1;
        current = arr[i];
        while(preIndex >= 0 && arr[preIndex] > current) {
            arr[preIndex+1] = arr[preIndex];
            preIndex--;
        }
        arr[preIndex+1] = current;
    }
    return arr;
}

原理圖

四、歸并排序

原理:

歸并是一種分治算法,即將原始數(shù)組切分成較小的數(shù)組,直到每個小數(shù)組只有一個位置,接著將小數(shù)組歸并成較大的數(shù)組,每次歸并時進(jìn)行排序,直到最后只有一個排序完畢的大數(shù)組。

代碼實(shí)現(xiàn)(遞歸):

function mergeSort(arr) {  // 采用自上而下的遞歸方法,數(shù)組拆分
    var len = arr.length;
    if(len < 2) {
        return arr;
    }
    var middle = Math.floor(len / 2),
        left = arr.slice(0, middle),
        right = arr.slice(middle);
    return merge(mergeSort(left), mergeSort(right));
}
//合并數(shù)組,并進(jìn)行排序
function merge(left, right)
{
    var result = [];

    while (left.length && right.length) {
        if (left[0] <= right[0]) {
            result.push(left.shift());
        } else {
            result.push(right.shift());
        }
    }

    while (left.length)
        result.push(left.shift());

    while (right.length)
        result.push(right.shift());

    return result;
}

原理圖

五、快速排序

原理:

快速排序使用分治法(Divide and conquer)策略來把一個串行(list)分為兩個子串行(sub-lists)。

排序步驟:

首先,從數(shù)組中選擇中間一項(xiàng)作基數(shù);

然后,創(chuàng)建兩個指針,左邊一個指向數(shù)組的第一項(xiàng),右邊一個指向數(shù)組的最后一項(xiàng);

移動左指針直到找到一個比基數(shù)大的元素,移動右指針,直到找到一個比基數(shù)小的元素;然后交換它們;

重復(fù)以上步驟,直到左指針超過了右指針;(這個過程將使得比基數(shù)小的樹都在基數(shù)的前面,較大的數(shù)都在基數(shù)的后面)

最后,對劃分后的小數(shù)組(比基數(shù)小的值組成的子數(shù)組,以及比基數(shù)大的值組成是子數(shù)組)重復(fù)之前的兩個步驟,直到數(shù)組已經(jīng)完全排序。

代碼實(shí)現(xiàn)

function quickSort(arr, left, right) {
    var len = arr.length,
        partitionIndex,
        left = typeof left != "number" ? 0 : left,
        right = typeof right != "number" ? len - 1 : right;

    if (left < right) {
        partitionIndex = partition(arr, left, right);
        quickSort(arr, left, partitionIndex-1);
        quickSort(arr, partitionIndex+1, right);
    }
    return arr;
}

function partition(arr, left ,right) {     // 分區(qū)操作
    var pivot = left,                      // 設(shè)定基準(zhǔn)值(pivot)
        index = pivot + 1;
    for (var i = index; i <= right; i++) {
        if (arr[i] < arr[pivot]) {
            swap(arr, i, index);
            index++;
        }        
    }
    swap(arr, pivot, index - 1);
    return index-1;
}

function swap(arr, i, j) {
    var temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}
function partition2(arr, low, high) {
  let pivot = arr[low];
  while (low < high) {
    while (low < high && arr[high] > pivot) {
      --high;
    }
    arr[low] = arr[high];
    while (low < high && arr[low] <= pivot) {
      ++low;
    }
    arr[high] = arr[low];
  }
  arr[low] = pivot;
  return low;
}

function quickSort2(arr, low, high) {
  if (low < high) {
    let pivot = partition2(arr, low, high);
    quickSort2(arr, low, pivot - 1);
    quickSort2(arr, pivot + 1, high);
  }
  return arr;
}

原理圖

持續(xù)更新中~喜歡留下個贊哦!

往期經(jīng)典好文推薦——前端JavaScript面試寶典

我的成長日記——我的前端面試日記(1)

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

轉(zhuǎn)載請注明本文地址:http://specialneedsforspecialkids.com/yun/54548.html

相關(guān)文章

  • 學(xué)習(xí)經(jīng)典算法JavaScript排序算法

    摘要:對每一對相鄰元素作同樣的工作,從開始第一對一直到結(jié)尾的最后一對,如此將最大的數(shù)放在后面。持續(xù)每次對元素重復(fù)上面的步驟,直到排序完成。排序步驟將第一待排序序列第一個元素看做一個有序序列,把第二個元素到最后一個元素當(dāng)成是未排序序。 前端攻城獅——學(xué)習(xí)常用的排序算法 一、冒泡排序 優(yōu)點(diǎn): 所有排序中最簡單的,易于理解; 缺點(diǎn): 時間復(fù)雜度O(n^2),平均來說是最差的一種排序方式; 因?yàn)樵?..

    fireflow 評論0 收藏0
  • 學(xué)習(xí)經(jīng)典算法JavaScript排序算法

    摘要:對每一對相鄰元素作同樣的工作,從開始第一對一直到結(jié)尾的最后一對,如此將最大的數(shù)放在后面。持續(xù)每次對元素重復(fù)上面的步驟,直到排序完成。排序步驟將第一待排序序列第一個元素看做一個有序序列,把第二個元素到最后一個元素當(dāng)成是未排序序。 前端攻城獅——學(xué)習(xí)常用的排序算法 一、冒泡排序 優(yōu)點(diǎn): 所有排序中最簡單的,易于理解; 缺點(diǎn): 時間復(fù)雜度O(n^2),平均來說是最差的一種排序方式; 因?yàn)樵?..

    Rindia 評論0 收藏0
  • 十大經(jīng)典排序算法總結(jié)(Javascript描述)

    摘要:算法描述冒泡排序是一種簡單的排序算法。算法描述和實(shí)現(xiàn)一般來說,插入排序都采用在數(shù)組上實(shí)現(xiàn)。平均情況希爾排序年發(fā)明第一個突破的排序算法是簡單插入排序的改進(jìn)版它與插入排序的不同之處在于,它會優(yōu)先比較距離較遠(yuǎn)的元素。 前言 讀者自行嘗試可以想看源碼戳這,博主在github建了個庫,讀者可以Clone下來本地嘗試。此博文配合源碼體驗(yàn)更棒哦~~~ 個人博客:Damonare的個人博客 原文地址:...

    Binguner 評論0 收藏0
  • Nicolas講算法:Computer Science in JavaScript

    摘要:使用來描述算法和數(shù)據(jù)結(jié)構(gòu)的教程很少,目前市面上用描述算法和數(shù)據(jù)結(jié)構(gòu)的書屈指可數(shù),并且就我看過的那本而言我只看過數(shù)據(jù)結(jié)構(gòu)與算法語言描述質(zhì)量實(shí)在堪憂。 使用JavaScript來描述算法和數(shù)據(jù)結(jié)構(gòu)的教程很少, 目前市面上用JS描述算法和數(shù)據(jù)結(jié)構(gòu)的書屈指可數(shù),并且就我看過的那本而言(我只看過《數(shù)據(jù)結(jié)構(gòu)與算法 JavaScript 語言描述》)質(zhì)量實(shí)在堪憂。碰巧有次看到Nicolas博客中的C...

    codergarden 評論0 收藏0

發(fā)表評論

0條評論

最新活動
閱讀需要支付1元查看
<