本文是之前寫的一篇js版的算法介紹。

插入排序

將一個記錄插入到已排序好的有序表中，從而得到一個新，記錄數(shù)增1的有序表。

function insertionSort(arr) {
    let len = arr.length;
    for(let i = 1; i < len; i++) {
        let temp = arr[i];
        for(var j = i; j > 0 && arr[j-1] > temp; j--) {
            arr[j] = arr[j-1];
        }
        arr[j] = temp;
    }
}

希爾排序

縮小增量的插入排序，先將整個待排序的記錄序列分割成為若干子序列分別進(jìn)行直接插入排序，待整個序列中的記錄“基本有序”時，再對全體記錄進(jìn)行依次直接插入排序。

function shellSort(arr) {
    let len = arr.length;
    let inc = parseInt(len / 2);
    while(inc > 0){
        for(let i = inc; i < len; i++) {
            let temp =  arr[i];
            for(var j = i; j >= inc && arr[j-inc] > temp; j -= inc) {
                arr[j] = arr[j-inc];
            }
            arr[j] = temp;
        }
        inc = parseInt(inc / 2);
    }
}

選擇排序

在要排序的一組數(shù)中，選出最?。ɑ蛘咦畲螅┑囊粋€數(shù)與第1個位置的數(shù)交換；然后在剩下的數(shù)當(dāng)中再找最?。ɑ蛘咦畲螅┑呐c第2個位置的數(shù)交換，依次類推，直到第n-1個元素（倒數(shù)第二個數(shù)）和第n個元素（最后一個數(shù)）比較為止。

function selectSort(arr) {
    let len = arr.length;
    for(let i = 0; i < len-1; i++) {
        let minIdx = i;
        for(let j = i+1; j < len; j++) {
            if(arr[j] < arr[minIdx]) minIdx = j;
        }
        [arr[i], arr[minIdx]] = [arr[minIdx], arr[i]];
    }
}

堆排序

堆排序是一種樹形選擇排序，是對直接選擇排序的有效改進(jìn)

function heapSort(arr) {
    buildHeap(arr);
    console.log(arr);
    for(let i = arr.length - 1; i >= 0; i--) {
        [arr[i], arr[0]] = [arr[0], arr[i]];
        AdjustHeap(arr, 0, i);
    }
}

function buildHeap(arr) {
    let len = arr.length;
    for(let i = Math.floor(len / 2) - 1; i >= 0; i--) {
        AdjustHeap(arr, i, len);
    }
}

function AdjustHeap(arr, idx, len) {
    // let len = arr.length;
    let left = 2 * idx + 1;
    while(left < len) {
        if(left+1 < len && arr[left] < arr[left+1]) {
            left++;
        }
        if(arr[idx] < arr[left]) {
            [arr[idx], arr[left]] = [arr[left], arr[idx]];
            idx = left;
            left = idx * 2 + 1;
        } else {
            break;
        }
    }
}

冒泡排序

每當(dāng)兩相鄰的數(shù)比較后發(fā)現(xiàn)它們的排序與排序要求相反時，就將它們互換。

function bubleSort(arr) {
    let len = arr.length;
    for(let i = 0; i < len - 1; i++) {
        for(let j = 0; j < len - 1- i; j++) {
            if(arr[j] > arr[j+1]) {
                [arr[j], arr[j+1]] = [arr[j+1], arr[j]];
            }
        }
    }
}

設(shè)置標(biāo)志位，對冒泡排序進(jìn)行改進(jìn)。

function bubleSort2(arr) {
    let i = arr.length - 1;
    while(i > 0) {
        let pos = 0;
        for(let j = 0; j < i; j++) {
            if(arr[j] > arr[j+1]) {
                [arr[j], arr[j+1]] = [arr[j+1], arr[j]];
                pos = j;
            }
        }
        i  = pos;
        console.log(pos);
    }
}

快速排序

選擇一個基準(zhǔn)元素,通常選擇第一個元素或者最后一個元素；通過一趟排序講待排序的記錄分割成獨立的兩部分，其中一部分記錄的元素值均比基準(zhǔn)元素值小，另一部分記錄的 元素值比基準(zhǔn)值大；此時基準(zhǔn)元素在其排好序后的正確位置；然后分別對這兩部分記錄用同樣的方法繼續(xù)進(jìn)行排序，直到整個序列有序。

function quickSort(arr, start, end) {
    if(start < end) {
        let left = start, right = end;
        let mid = arr[left];
        while(left < right) {
            while(left < right && arr[right] >= mid) right--;
            [arr[left], arr[right]] = [arr[right], arr[left]];
            while(left < right && arr[left] <= mid) left++;
            [arr[left], arr[right]] = [arr[right], arr[left]]; 
        }
        quickSort(arr, start, left-1);
        quickSort(arr, left+1, end);
    }
}

歸并排序

歸并（Merge）排序法是將兩個（或兩個以上）有序表合并成一個新的有序表，即把待排序序列分為若干個子序列，每個子序列是有序的。然后再把有序子序列合并為整體有序序列。

function mergeSort(arr, start, end) {
    if(start < end) {
        let mid = Math.floor((start + end) / 2);
        mergeSort(arr, start, mid);
        mergeSort(arr, mid + 1, end)；
        if(arr[mid] > arr[mid+1]) { //如果兩部分已經(jīng)有序，不再進(jìn)行歸并操作
          merge(arr, start, mid, end); 
        }
    }
}

function merge(arr, start, mid, end) {
    let i = start, j = mid+1;
    let temp = new Array(end - start + 1);
    let k = 0;
    for(; i <= mid && j <= end; ) {
        if(arr[i] <= arr[j]) {
            temp[k++] = arr[i++];
        } else {
            temp[k++] = arr[j++];
        }
    }
    while(i<=mid) temp[k++] = arr[i++];
    while(j<=end) temp[k++] = arr[j++];
    for(let item of temp) {
        arr[start++] = item;
    }
}

歸并排序的非遞歸做法

歸并排序的非遞歸做法好像是面試時常遇到的問題，實現(xiàn)如下：

function mergeSort2(arr) {
    let step = 1;
    let temp = new Array(arr.length);
    for(; step < arr.length ; step = step*2) {
        let ls, le, rs, re;
        for(let ls = 0; ls < arr.length - step; ls = re) {
            rs = le = ls + step;
            re = rs + step;
            if(re > arr.length) {
                re = arr.length;
            }
            let k = 0;
            while(ls < le && rs < re) {
                temp[k++] = arr[ls] > arr[rs] ? arr[rs++] : arr[ls++];
            }
            while(ls < le) {
                temp[k++] = arr[ls++];
            }
            while(k > 0) {
                arr[--rs] = temp[--k];
            }
        }
    }
}

自底向上的歸并排序

自底向上的歸并排序也是非遞歸的，實現(xiàn)如下：

template<typename T>
void mergeSortBU(T a[], int n) {
  for(int size = 1; size <= n; size += size) {
    for(int i = 0; i+size < n; i += size + size) {
      merge(a, i, i+size-1, min(i+2*size-1, n-1));
    }
  }
}