JS十大排序算法

排序算法说明

1.对于评述算法优劣术语的说明

• 稳定：如果a原本在b前面，而a=b，排序后a仍然在b的前面；
• 不稳定：如果a原本在b前面，a=b，排序后a可能会出现在b的后面；
• 内排序：所有排序操作都在内存中完成；
• 外排序：由于数据太大，因此把数据放在磁盘中，而排序通过磁盘和内存的数据传输才能进行；
• 时间复杂度：一个算法执行所耗费的时间；
• 空间复杂度：运行完成一个程序所需内存的大小。

2.排序算法图片总结

1.冒泡排序

1. 比较相邻两个元素，如果前一个比后一个大，则交换位置。
2. 第一轮的时候最后一个元素应该是最大的。
3. 按照步骤一的方法继续进行相邻两个元素的比较，这个时候由于最后的一个元素已经是最大的了，所以最后一个元素不用比较。

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.快速排序

快速排序是对冒泡排序的一种改进，第一趟排序时将数据分成两部分，一部分比另一部分的所有数据都要小，然后递归调用，在两边都实行快速排序。

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()方法用于连接两个或者多个数组；该方法不会改变现有的数组，而仅仅会返回被连接数组的一个副本。
};
var elements=[3,5,6,8,2,4,7,9,1,10];
document.write(quickSort(elements)); 

3.插入排序

1. 从第一个元素开始，该元素可以认为已经被排序；
2. 取下一个元素，在已排序的元素序列中从后向前扫描；
3. 如果该元素（已排序）大于新元素，将该元素移动到下一位置；
4. 重复步骤3，直接找打已排序的元素大小或者等于新元素的位置；
5. 将新元素插到下一位置；
6. 重复步骤2

3.1 正常的插入排序

function sort(elements){
    // 假设第0个元素是一个有序数列，第1个以后的是无序数列，
    // 所以从第1个元素开始将无序数列的元素插入到有序数列中去
    for (var i =1; i<=elements.length; i++) {
        // 升序
        if(elements[i] < elements[i-1]){
            // 取出无序数列中的第i个作为被插入元素
            var guard=elements[i];
            //记住有序数列的最后一个位置，并且将有序数列的位置扩大一个
            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('没调用之前：'+elements);
document.write('<br>');
sort(elements);
document.write('被调用之后：'+elements);

3.2 二分查找

二分查找，也为折半查找，首先要找到一个中间值，通过与中间值的比较，大的放右，小的放左。再向两边中寻找中间值，持续以上操作。直到找到左右位置为止。

3.2.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));

3.2.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. 选择排序

首先在未排序序列中找到最大（小）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最大（小）元素，放到已排序序列的末尾。以此类推，直到所有元素均排列完毕。

function selectionSort(arr){
        var len=arr.length;
    var minIndex,temp;
    console.time('选择排序耗时');
    for(var i=0;i<len-1;i++){
        minIndex=i;
        for(var j=i+1;j<len;j++){
            if(arr[j]<arr[minIndex]){ //寻找最小数
                minIndex=j; //将最小数的索引保存
            }
        }
        temp=arr[i];
        arr[i]=arr[minIndex];
        arr[minIndex]=temp;
    }
            console.timeEnd('选择排序耗时');
            return arr;
}
var arr=[1,2,3,4,5,6,7,8,9,10];
console.log(selectionSort(arr));

5. 希尔排序

先将这个待排序的记录序列分割成若干子序列分别进行直接插入排序

function shellSort(arr){
    var len=arr.length,temp,gap=1;
    console.time('希尔排序耗时：');
    while (gap<len/5) { //动态定义间隔序列
        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('希尔排序耗时：');
      return arr;
}
var arr=[1,2,3,4,5,6,7,8,9,10];
console.log(shellSort(arr));

6. 归并排序

归并排序是一种稳定的排序方法，将以有序的子序列合并，得到完全有序的序列，即先使每个子序列有序，再使子序列段有序。

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

7. 堆排序

堆排序（Heapsort）是指利用堆这种数据结构所设计的一种【】排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质，即子节点的键值或索引总是小于（或者大于）它的节点。

function heapSort(array){
    console.log('堆排序耗时：');
    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('堆排序耗时：');
        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. 计数排序

计数排序使用一种额外的数组C,其中第一个元素是待排序数组A中值等于i的元素的个数。然后根据数组C来将数组A中的元素排序到正确的位置。它只能对整数进行排序。

function countingSort(array){
    var len = array.length, B = [],C = [],
         min = max =array[0];
    console.time('计数排序耗时：');
    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('计数排序耗时：');
    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. 桶排序

假设输入数据服从均匀分布,将数据分到有限数量的桶里，每个桶再分别排序（有可能再使用别的排序算法或是yidigui以递归的方式继续使用桶排序进行排）。

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. 基数排序

基数排序是按照低位先排序，然后收集；再按照高位排序，然后再收集，以此类推，直到最高位，有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序，最后的次序就是高优先级高的在前，高优先级相同的低优先级高的排在前面，基数排序基于分别排序，分别收集，所以是稳定的。

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