前端10大經(jīng)典算法

function bubbleSort(arr) {
    var len = arr.length;
    for (var i = 0; i < len - 1; i++) {
        for (var j = 0; j < len - 1 - i; j++) {
            if (arr[j] > arr[j+1]) {       // 相鄰元素兩兩對比
                var temp = arr[j+1];       // 元素交換
                arr[j+1] = arr[j];
                arr[j] = temp;
            }
        }
    }
    return arr;
}

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

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;
}

function shellSort(arr) {
    var len = arr.length,
        temp,
        gap = 1;
    while (gap < len / 3) {         // 動態(tài)定義間隔序列
        gap = gap * 3 + 1;
    }
    for (gap; gap > 0; gap = Math.floor(gap / 3)) {
        for (var i = gap; i < len; i++) {
            temp = arr[i];
            for (var j = i-gap; j > 0 && arr[j]> temp; j-=gap) {
                arr[j + gap] = arr[j];
            }
            arr[j + gap] = temp;
        }
    }
    return arr;
}

function mergeSort(arr) { // 采用自上而下的遞歸方法    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));}
function merge(left, right) {    var result = [];
    while (left.length>0 && right.length>0) {        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;}

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;}

var len;   // 因為聲明的多個函數(shù)都需要數(shù)據(jù)長度，所以把len設(shè)置成為全局變量
function buildMaxHeap(arr) {  // 建立大頂堆    len = arr.length;    for (var i = Math.floor(len/2); i >= 0; i--) {        heapify(arr, i);    }}
function heapify(arr, i) {    // 堆調(diào)整    var left = 2 * i + 1,        right = 2 * i + 2,        largest = i;
    if (left < len && arr[left] > arr[largest]) {        largest = left;    }
    if (right < len && arr[right] > arr[largest]) {        largest = right;    }
    if (largest != i) {        swap(arr, i, largest);        heapify(arr, largest);    }}
function swap(arr, i, j) {    var temp = arr[i];    arr[i] = arr[j];    arr[j] = temp;}
function heapSort(arr) {    buildMaxHeap(arr);
    for (var i = arr.length - 1; i > 0; i--) {        swap(arr, 0, i);        len--;        heapify(arr, 0);    }    return arr;}

function countingSort(arr, maxValue) {    var bucket =new Array(maxValue + 1),        sortedIndex = 0;        arrLen = arr.length,        bucketLen = maxValue + 1;
    for (var i = 0; i < arrLen; i++) {        if (!bucket[arr[i]]) {            bucket[arr[i]] = 0;        }        bucket[arr[i]]++;    }
    for (var j = 0; j < bucketLen; j++) {        while(bucket[j] > 0) {            arr[sortedIndex++] = j;            bucket[j]--;        }    }
    return arr;}

unction bucketSort(arr, bucketSize) {    if (arr.length === 0) {      return arr;    }
    var i;    var minValue = arr[0];    var maxValue = arr[0];    for (i = 1; i < arr.length; i++) {      if (arr[i] < minValue) {          minValue = arr[i];               // 輸入數(shù)據(jù)的最小值      }else if (arr[i] > maxValue) {          maxValue = arr[i];               // 輸入數(shù)據(jù)的最大值      }    }
    // 桶的初始化    var DEFAULT_BUCKET_SIZE = 5;           // 設(shè)置桶的默認(rèn)數(shù)量為5    bucketSize = bucketSize || DEFAULT_BUCKET_SIZE;    var bucketCount = Math.floor((maxValue - minValue) / bucketSize) + 1;      var buckets =new Array(bucketCount);    for (i = 0; i < buckets.length; i++) {        buckets[i] = [];    }
    // 利用映射函數(shù)將數(shù)據(jù)分配到各個桶中    for (i = 0; i < arr.length; i++) {        buckets[Math.floor((arr[i] - minValue) / bucketSize)].push(arr[i]);    }
    arr.length = 0;    for (i = 0; i < buckets.length; i++) {        insertionSort(buckets[i]);                     // 對每個桶進(jìn)行排序，這里使用了插入排序        for (var j = 0; j < buckets[i].length; j++) {            arr.push(buckets[i][j]);                             }    }
    return arr;}

/ LSD Radix Sortvar counter = [];function radixSort(arr, maxDigit) {    var mod = 10;    var dev = 1;    for (var i = 0; i < maxDigit; i++, dev *= 10, mod *= 10) {        for(var j = 0; j < arr.length; j++) {            var bucket = parseInt((arr[j] % mod) / dev);            if(counter[bucket]==null) {                counter[bucket] = [];            }            counter[bucket].push(arr[j]);        }        var pos = 0;        for(var j = 0; j < counter.length; j++) {            var value =null;            if(counter[j]!=null) {                while ((value = counter[j].shift()) !=null) {                      arr[pos++] = value;                }          }        }    }    return arr;}