排序算法說(shuō)明：
（1）對(duì)于評(píng)述算法優(yōu)劣術(shù)語(yǔ)的說(shuō)明
穩(wěn)定：如果a原本在b前面，而a=b，排序后a仍然在b的前面；
不穩(wěn)定：如果a原本在b前面，a=b，排序后a可能會(huì)出現(xiàn)在b的后面；
內(nèi)排序：所有排序操作都在內(nèi)存中完成；
外排序：由于數(shù)據(jù)太大，因此把數(shù)據(jù)放在磁盤中，而排序通過(guò)磁盤和內(nèi)存的數(shù)據(jù)傳輸才能進(jìn)行；
時(shí)間復(fù)雜度：一個(gè)算法執(zhí)行所耗費(fèi)的時(shí)間；
空間復(fù)雜度：運(yùn)行完成一個(gè)程序所需內(nèi)存的大小。
（2）排序算法圖片總結(jié)：

image.png

1、冒泡排序：
解析：
1.比較相鄰兩個(gè)元素，如果前一個(gè)比后一個(gè)大，則交換位置；
2.第一輪的時(shí)候最后一個(gè)元素應(yīng)該是最大的；
3.按照步驟一的方法繼續(xù)進(jìn)行相鄰兩個(gè)元素的比較，這個(gè)時(shí)候由于最后的一個(gè)元素已經(jīng)是最大的了，所以最后一個(gè)元素不用比較。

function sort(elements){
    for(var i=0;i<elements.length;i++){
       for(var j=0;j<elements.length-1-i;j++){
          if(elements[j] > elements[j+1]){
               var  swap=elements[j];
               elements[j]=elements[j+1];
               elements[j+1]=swap;
          }
       }
    }
}
var elements=[3,5,6,8,2,4,7,9,1,10];
console.log('before'+elements);
sort(elements);
console.log('after'+elements);

2、快速排序：
解析：快速排序是對(duì)冒泡排序的一種改進(jìn)，第一趟排序時(shí)將數(shù)據(jù)分成兩部分，一部分比另一部分的所有數(shù)據(jù)都要小，然后遞歸調(diào)用，在兩邊都實(shí)行快速排序。

function quickSort(elements){
    if(elements.length <=1){
      return elements;  
    }
  var pivotIndex=Math.floor(elements.length / 2);
  var pivot=elements.splice(pivotIndex,1)[0];
  var left=[];
  var right=[];
  for(var i=0;i<elements.length;i++){
    if(elements[i] < pivot){
        left.push(elements[i]);
    }else{
       right.push(elements[i]);
    }
  } 
return  quickSort(left).concat([pivot],quickSort(right));
//concat()方法用于連接兩個(gè)或者多個(gè)數(shù)組；該方法不會(huì)改變現(xiàn)有的數(shù)組，而僅僅會(huì)返回被連接數(shù)組的一個(gè)副本。
};
var elements=[3,5,6,8,2,4,7,9,1,10];
document.write(quickSort(elements)); 

3、插入排序：
解析：
（1）從第一個(gè)元素開(kāi)始，該元素可以認(rèn)為已經(jīng)被排序；
（2）取下一個(gè)元素，在已排序的元素序列中從后向前掃描；
（3）如果該元素（已排序）大于新元素，將該元素移動(dòng)到下一位置；
（4）重復(fù)步驟3，直接找打已排序的元素大小或者等于新元素的位置；
（5）將新元素插到下一位置；
（6）重復(fù)步驟2

function sort(elements){
    // 假設(shè)第0個(gè)元素是一個(gè)有序數(shù)列，第1個(gè)以后的是無(wú)序數(shù)列，
    // 所以從第1個(gè)元素開(kāi)始將無(wú)序數(shù)列的元素插入到有序數(shù)列中去
    for (var i =1; i<=elements.length; i++) {
        // 升序
        if(elements[i] < elements[i-1]){
            // 取出無(wú)序數(shù)列中的第i個(gè)作為被插入元素
            var guard=elements[i];
            //記住有序數(shù)列的最后一個(gè)位置，并且將有序數(shù)列的位置擴(kuò)大一個(gè)
            var j=i-1;
            elements[i]=elements[j];
            // 比大小;找到被插入元素所在位置
            while (j>=0 && guard <elements[j]) {
                elements[j+1]=elements[j];
                j--;
            }
            elements[j+1]=guard; //插入
        }
    }
}
var elements=[3,5,6,8,2,4,7,9,1,10];
document.write('沒(méi)調(diào)用之前：'+elements);
document.write('<br>');
sort(elements);
document.write('被調(diào)用之后：'+elements);

2、二分查找
解析：二分查找，也為折半查找，首先要找到一個(gè)中間值，通過(guò)與中間值的比較，大的放右，小的放左。再向兩邊中尋找中間值，持續(xù)以上操作。直到找到左右位置為止。
（1）遞歸方式

function binarySearch(data,dest,start,end){
    var end=end || data.length-1;
    var start=start || 0;
    var m=Math.floor((start + end)/2);
        if(data[m]==dest){
            return m;
        }
        if(dest < data[m]){
            return binarySearch(data,dest,0,m-1);
        }else{
            return binarySearch(data,dest,m+1,end);
        }
        return false;
    }
    var arr=[1,2,3,4,5,6,7,8,9,10];
    document.write(binarySearch(arr,4));

（2）非遞歸方法

function binarySearch(data,dest){
    var h=data.length-1;
    var l=0;
    while (l<=h) {
        var m=Math.floor((h+l)/2);
        if(data[m] ==dest){
            return m;
        }
        if(dest >data[m]){
            l=m+1;
        }else{
            h=m-1;
        }
    }
    return false;
}
var arr=[1,2,3,4,5,6,7,8,9,10];
document.write(binarySearch(arr,4));

4、選擇排序：
解析：首先在未排序序列中找到最大（?。┰?，存放到排序序列的起始位置，然后，再?gòu)氖Ｓ辔磁判蛟刂欣^續(xù)尋找最大（?。┰兀诺揭雅判蛐蛄械哪┪?。以此類推，直到所有元素均排列完畢。

function selectionSort(arr){
        var len=arr.length;
    var minIndex,temp;
    console.time('選擇排序耗時(shí)');
    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;
    }
            console.timeEnd('選擇排序耗時(shí)');
            return arr;
}
var arr=[1,2,3,4,5,6,7,8,9,10];
console.log(selectionSort(arr));

5、希爾排序：
解析:先將這個(gè)待排序的記錄序列分割成若干子序列分別進(jìn)行直接插入排序。

function shellSort(arr){
    var len=arr.length,temp,gap=1;
    console.time('希爾排序耗時(shí)：');
    while (gap<len/5) { //動(dòng)態(tài)定義間隔序列
        gap=gap*5+1;
    }
    for(gap;gap>0;gap=Math.floor(gap /5)){
        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;
        }
    }
      console.timeEnd('希爾排序耗時(shí)：');
      return arr;
}
var arr=[1,2,3,4,5,6,7,8,9,10];
console.log(shellSort(arr));

6、歸并排序：
解析：歸并排序是一種穩(wěn)定的排序方法，將以有序的子序列合并，得到完全有序的序列，即先使每個(gè)子序列有序，再使子序列段有序。

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=[];
    console.time('歸并排序耗時(shí)：');
    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());
    }
    console.timeEnd('歸并排序耗時(shí)：');
            return result;
    }
    var arr=[3,5,6,8,2,4,7,9,1,10];
    document.write(mergeSort(arr));

7、堆排序
解析:堆排序（Heapsort）是指利用堆這種數(shù)據(jù)結(jié)構(gòu)所設(shè)計(jì)的一種【】排序算法。堆積是一個(gè)近似完全二叉樹(shù)的結(jié)構(gòu)，并同時(shí)滿足堆積的性質(zhì)，即子節(jié)點(diǎn)的鍵值或索引總是小于（或者大于）它的節(jié)點(diǎn)。

function heapSort(array){
    console.log('堆排序耗時(shí)：');
    if(Object.prototype.toString.call(array).slice(8,-1)==='Array'){
        var heapSize=array.length,temp;//建堆
        for (var i=Math.floor(heapSize / 2) -1; i>=0; i--) {
            heapify(array,i,heapSize);
        }
        for(var j=heapSize-1;j>=1;j--){//堆排序
            temp=array[0];
            array[0]=array[j];
            array[j]=temp;
            heapify(array,0,--heapSize);
        }
        console.log('堆排序耗時(shí)：');
        return array;
    }else{
        return 'array is not an Array!';
    }
}

function heapify(arr,x,len){
    if(Object.prototype.toString.call(arr).slice(8,-1)==='Array' && typeof x==='number'){
        var l = 2 * x + 1,
            r = 2 * x + 2,
            largest = x,
            temp;
        if(l < len && arr[l] > arr[largest]){
            largest = l;
        }
        if(r < len && arr[r] > arr[largest]){
            largest = r;
        }
        if(largest != x){
            temp = arr[x];
            arr[x] = arr[largest];
            arr[largest] = temp;
            heapify(arr,largest,len);
        }
    }else{
        return 'arr is not Array or x is not a number!';
    }
}
var arr=[91,60,96,86,13,73,63,40,30,71,88];
document.write(heapSort(arr));

8、計(jì)數(shù)排序
解析：計(jì)數(shù)排序使用一種額外的數(shù)組C,其中第一個(gè)元素是待排序數(shù)組A中值等于i的元素的個(gè)數(shù)。然后根據(jù)數(shù)組C來(lái)將數(shù)組A中的元素排序到正確的位置。它只能對(duì)整數(shù)進(jìn)行排序。

function countingSort(array){
    var len = array.length, B = [],C = [],
         min = max =array[0];
    console.time('計(jì)數(shù)排序耗時(shí)：');
    for (var i = 0; i < len; i++) {
        min = min <= array[i] ? min : array[i];
        max = max >= array[i] ? max : array[i];
        C[array[i]] = C[array[i]] ? C[array[i]] + 1 : 1;
    }
    for (var j = min; j < max; j++) {
        C[j+1] = (C[j + 1] || 0) + (C[j] || 0);
    }
    for (var k = len - 1; k > 0; k--) {
        B[C[array[k]] - 1] =array[k];
        C[array[k]]--;
    }
    console.timeEnd('計(jì)數(shù)排序耗時(shí)：');
    return B;
}
var arr=[2,2,3,5,4,2,8,6,7,69,5,2,1,3,4,7,3,6];
document.write(countingSort(arr));

9、桶排序：
解析：假設(shè)輸入數(shù)據(jù)服從均勻分布,將數(shù)據(jù)分到有限數(shù)量的桶里，每個(gè)桶再分別排序（有可能再使用別的排序算法或是yidigui以遞歸的方式繼續(xù)使用桶排序進(jìn)行排）。

function bucketSort(array,num){
    if(array.length <= 1){
        return array;
    }
    var len = array.length,buckets = [],result = [],
    min = max =array[0],regex ='/^[1-9]+[0-9]*$/',space,n=0;
    num = num || ((num > 1 && regex.test(num))?num : 10);
    for(var i = 1; i < len; i++){
        min = min <= array[i] ? min :array[i];
        max = max >=array[i] ? max : array[i];
    }
    space = (max - min + 1) / num;
    for(var j =0; j < len; j++){
        var index = Math.floor((array[j] - min) / space);
        if(buckets[index]){//非空桶，插入排序
            var k = buckets[index].length - 1;
            while (k >= 0 && buckets[index][k] > array[j]) {
                buckets[index][k+1] = buckets[index][k];
                k--;
            }
            buckets[index][k+1]=array[j];
        }else{//空桶，初始化
            buckets[index] = [];
            buckets[index].push(array[j]);
        }
    }
    while (n < num) {
        result = result.concat(buckets[n]);
        n++;
    }
    return result;
}
var arr=[3,55,4,2,45,33,87,98,68,58,70,66];
document.write(bucketSort(arr,4));

10、基數(shù)排序：
解析：基數(shù)排序是按照低位先排序，然后收集；再按照高位排序，然后再收集，以此類推，直到最高位，有時(shí)候有些屬性是有優(yōu)先級(jí)順序的，先按低優(yōu)先級(jí)排序，再按高優(yōu)先級(jí)排序，最后的次序就是高優(yōu)先級(jí)高的在前，高優(yōu)先級(jí)相同的低優(yōu)先級(jí)高的排在前面，基數(shù)排序基于分別排序，分別收集，所以是穩(wěn)定的。

function radixSort(arr,maxDight){
    var mod = 10;
    var dev =1;
    var counter = [];
    console.time('基數(shù)排序耗時(shí)：');
    for (var i = 0; i < maxDight; 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;
                }
            }
        }
    }
    console.timeEnd('基數(shù)排序耗時(shí)：');
    return arr;
}
var arr=[3,55,4,2,45,33,87,98,68,58,70,66];
document.write(radixSort(arr,2));