十大排序算法JavaScript实现总结

前端开发作者： 2024-08-26 08:50:01

花费了几周的时间断断续续的练习和模仿与使用JavaScript代码实现了十大排序算法。里面有每种算法的动图和静态图片演示，看到图片可以自己先按照图片的思路实现一下。 github中正文链接，点击查看

1.排序的定义

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

3.排序算法图片总结

1.算法描述

2.算法描述和实现

function bubbleSort(arr) {
  let len = arr.length;

  for (let i = 0; i < len; i++) {
    for (let j = 0; j < len - i - 1; j++) {
      if (arr[j] > arr[j + 1]) {  // 相邻元素两两对比
        let tmp = arr[j];         // 元素交换
        arr[j] = arr[j + 1];
        arr[j + 1] = tmp;
      }
    }
  }

  return arr;
}

let arr = [3,44,38,5,47,15,36,26,27,2,46,4,19,50,48];
console.log(bubbleSort(arr));
// [2,3,48,50]

function bubbleSort2(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]) {
        pos = j; // 记录最后修改位置
        let tmp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = tmp;
      }
    }
    i = pos;
  }
  return arr;
}


let arr = [3,48];
// let arr = [10,9,8,7,6,1];
console.log(bubbleSort2(arr));

function bubbleSort3(arr) {
  var low = 0;
  var high = arr.length - 1;
  var tmp,j;
  console.time('2.改进后的冒泡排序耗时');
  while (low < high) {

    for (j = low; j < high; j++) {
      // 这里排序出最高的
      if (arr[j] > arr[j + 1]) { // 正向冒泡，找出最大者
        tmp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = tmp;
      }
    }
    high--;

    for (j = high; j > low; j--) { // 反向冒泡 找出最小者
      if (arr[j] < arr[j - 1]) {
        tmp = arr[j];
        arr[j] = arr[j - 1];
        arr[j - 1] = tmp;
      }
    }
    low++;
  }
  console.timeEnd('2.改进后的冒泡排序耗时');
  return arr;
}


var arr = [3,48];
console.log(bubbleSort3(arr));//[2,50]

3.冒泡排序动图演示

1.算法简介

2.算法描述和实现

// 选择排序
function selectionSort(arr) {
  var length = arr.length;
  var minIndex,tmp;
  console.time("选择排序耗时");
  for (var i = 0; i < length - 1; i++) {
    minIndex = i;
    for (var j = i + 1; j < length; j++) {
      if (arr[j] < arr[minIndex]) {
        minIndex = j;
      }
    }
    tmp = arr[minIndex];
    arr[minIndex] = arr[i];
    arr[i] = tmp;
  }
  console.timeEnd("选择排序耗时");
  return arr;
}

var arr = [3,48];
console.log(selectionSort(arr));//[2,50]

3.选择排序动图演示

1.算法简介

2.算法的描述和实现

// 这个是我的实现，感觉代码好长的样子...
// 插入排序
function insertionSort(arr) {

  console.log('打印这个东西',Object.prototype.toString.call(arr),Object.prototype.toString.call(arr).slice(8,-1) === 'Array');

  var length = arr.length;
  var tmp;
  console.time('选择排序耗时');
  for (var i = 0; i < length; i++) {
    let tmp = arr[i];
    for (var j = i; j >= 0; j--) {
      if (j === 0) {
        arr[0] = tmp;
        break;
      }

      if (tmp < arr[j - 1]) {
        arr[j] = arr[j - 1];
      } else {
        arr[j] = tmp;
        break;
      }
    }
  }
  console.timeEnd('选择排序耗时');
  return arr;
}
// 10 7 8

var arr = [3,48];
console.log(insertionSort(arr));//[2,50]

// 插入排序
function insertionSort(arr) {
  if (Object.prototype.toString.call(arr).slice(8,-1) === 'Array') {
    console.time('插入排序耗时');
    for (var i = 1,length = arr.length; i < length; i++) {
      var key = arr[i];
      var j = i - 1;
      while (j >= 0 && arr[j] > key) {
        arr[j + 1] = arr[j];
        j--;
      }
      arr[j + 1] = key;
    }
    console.timeEnd('插入排序耗时');
    return arr;
  } else {
    return `array is not an array`;
  }
}
var arr = [3,50]

function binaryInsertionSort(arr) {
  if (Object.prototype.toString.call(arr).slice(8,-1) === 'Array') {
    console.time('二分插入排序耗时');
    var length = arr.length;
    for (var i = 1; i < length; i++) {

      var left = 0;
      var key = arr[i];
      var right = i - 1;

      while (left <= right) {
        var middle = parseInt((left + right) / 2);
        if (key < arr[middle]) {
          right = middle - 1;
        } else {
          left = middle + 1;
        }
      }

      for (var j = i - 1; j >= left; j--) {
        arr[j + 1] = arr[j]
      }
      arr[left] = key;
    }
    console.timeEnd('二分插入排序耗时');
    return arr;
  } else {
    throw new Error('arr is not arr');
  }
}

3.插入排序动图演示

1.算法简介

2.算法描述和实现

function shellSort(arr) {
  console.log('调用了函数方法');

  var len = arr.length;
  var tmp;
  var gap = 1;
  console.time('希尔排序耗时');
  while (gap < len / 5) { // 动态定义间隔序列
    gap = gap * 5 + 1;
    console.log('gap -------- ',gap);
  }
    
  // 在这个里面其实是对每一组数据又进行了插入排序 真的是写不出来不知道，想通了写出来一次感觉就简单了
    
  for (gap; gap > 0; gap = Math.floor(gap / 5)) {
    console.log('gap ===== >',gap);
    for (var i = 0; i < len; i++) {
      tmp = arr[i];
      for (var j = i - gap; j >= 0 && tmp < arr[j]; j -= gap) {
        arr[j + gap] = arr[j];
      }
      arr[j + gap] = tmp;
    }
  }
  console.timeEnd('希尔排序耗时');
  return arr;
}

var arr = [3,48];
console.log(shellSort(arr));//[2,50]

3.希尔排序图示

1.算法简介

2.算法描述和实现

// 这个思想有点难啊，看起来和之前的二叉树的中序遍历差不多

function mergeSort(arr) { // 采用自上而下的递归方法
  // console.log('mergeSort',arr);
  var length = arr.length;
  if (length < 2) {
    return arr;
  }

  var middle = Math.floor(length / 2);
  var left = arr.slice(0,middle);
  var right = arr.slice(middle);
  // console.log('mergeSort','left',left,'right',right);

  return merge(mergeSort(left),mergeSort(right));
}

function merge(left,right) {
  var result = [];
  console.log('left',right);
  // 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,48];
console.log(mergeSort(arr));

3.归并排序动图演示

1.算法简介

2.算法描述和实现

// 这个里面的核心代码是我写的，比它的好像差一些 它的核心原理有点没看懂，和下面的那个动图演示有点不一样，他选择的基准是右侧的那个。
// 感觉不是这种排列方法

function quickSort(arr,right) {
  if (Object.prototype.toString.call(arr).slice(8,-1) === 'Array' && typeof length === 'number' && typeof right === 'number') {

    // console.log('进来的数组',JSON.stringify(arr),'left ==>','right===>',right);
    if (left < right) {
      var key = arr[left]; // 起始位置
      var setPos = left + 1; // 设置的位置
      var tmp;
      for (var i = left + 1; i <= right; i++) {
        if (arr[i] < key) {
          tmp = arr[i]; // 交换位置，并将下次小于的位置+1
          arr[i] = arr[setPos];
          arr[setPos] = tmp;
          setPos++;
        }
      }
      // 循环完成之后将key与 pos-1的位置交换
      arr[left] = arr[setPos - 1];
      arr[setPos - 1] = key;
      // console.log('每一次排序','当前key值===>',key,'排序完成当前数组===>',JSON.stringify(arr));

      quickSort(arr,setPos - 2);
      quickSort(arr,setPos,right);
      // console.log('arr=======>',arr);
    }
  } else {
    return 'array is not an Array or left or right is not a number!';
  }
  return arr;
}


var arr = [3,48];
// var arr = [7,10,13,5];
console.log(quickSort(arr,arr.length - 1));//[2,50]

function quickSort(array,right) {
    console.time('1.快速排序耗时');
    if (Object.prototype.toString.call(array).slice(8,-1) === 'Array' && typeof left === 'number' && typeof right === 'number') {
        
        if (left < right) {
            var x = array[right],i = left - 1,temp;
            for (var j = left; j <= right; j++) {
                if (array[j] <= x) {
                    i++;
                    temp = array[i];
                    array[i] = array[j];
                    array[j] = temp;
                }
            }
            quickSort(array,i - 1);
            quickSort(array,i + 1,right);
        }
        console.timeEnd('1.快速排序耗时');
        return array;
        
    } else {
        return 'array is not an Array or left or right is not a number!';
    }
}

3.快速排序动图演示

function quickSort(arr) {
  if (arr.length <= 1) { return arr };
  var pivoIndex = Math.floor(arr.length / 2);
  var pivot = arr.splice(pivoIndex,1)[0]; // 将要选择排序的那一位选举出来 摘出来
  var left = [];
  var right = [];

  // 小的放左边，大的放右边
  for (var i = 0,len = arr.length; i < len; i++) {
    if (arr[i] < pivot) {
      left.push(arr[i]);
    } else {
      right.push(arr[i]);
    }
  }
  console.log('left',right);
  return quickSort(left).concat([pivot],quickSort(right));
}

var arr = [3,5];
console.log(quickSort(arr));//[2,50]

1.算法简介

2.算法描述和实现

/*
  方法说明：堆排序
  @param {Array} arr 待排序数组
*/

function heapSort(arr) {
  console.log('堆排序');


  console.log();
  if (Object.prototype.toString.call(arr).slice(8,-1) === 'Array') {

    var heapSize = arr.length;
    var temp;

    console.log('待排序数组的长度===>',heapSize);


    console.log('建造之前的堆的样式',JSON.stringify(arr));
    // 建造堆
    for (var i = Math.floor(heapSize / 2) - 1; i >= 0; i--) {
      heapify(arr,i,heapSize);
    }
    console.log('堆初始化完成之后的样式',JSON.stringify(arr));

    // 现在要把最大的放到最后一个，最后一个放到第一个，把堆的大小减少一个，在慢慢的把最大的循环上去
    console.time('堆排序耗时');
    for (var j = heapSize - 1; j >= 1; j--) {
      temp = arr[0];
      arr[0] = arr[j];
      arr[j] = temp;
      heapify(arr,--heapSize);
    }
    console.timeEnd('堆排序耗时');
    return arr;
  } else {
    return 'array is not array';
  }
}

/*
  建堆：维护堆的性质
  @param {Array} arr 数组
  @param {Number} x 数组下标
  @param {Number} len 堆大小
*/
function heapify(arr,x,len) {
  if (Object.prototype.toString.call(arr).slice(8,-1) === 'Array' && typeof x === 'number') {
    var l = 2 * x + 1; // 左下标
    var r = 2 * x + 2; // 右下标
    var largest = x; // 默认最大的是父节点
    var 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 an array or x is not a number';
  }
}


var arr = [91,60,96,35,65,30,20,31,77,81,22];
console.log(heapSort(arr));//[10,22,91,96]

3.堆排序动图演示

1.算法简介

2.算法描述和实现

function countingSort(arr) {
  console.log('计数排序');

  var len = arr.length;
  var B = [];
  var C = [];
  var min = max = arr[0];

  console.time('计数排序耗时');
  // 初始化计数排序
  for (var i = 0; i < len; i++) {
    min = min <= arr[i] ? min : arr[i];
    max = max >= arr[i] ? max : arr[i];
    C[arr[i]] = C[arr[i]] ? C[arr[i]] + 1 : 1;
  }
  console.log('初始化结束之后',JSON.stringify(C));
  var k = 0;
  for (var j = min; j < max; j++) {
    C[j + 1] = (C[j + 1] || 0) + (C[j] || 0);
  }

  console.log('计算完成之后',JSON.stringify(C));
  console.log('计算完成之后arr',JSON.stringify(arr));
  // 现在C的下标就是这个值，C的内容就是这个值的个数
  debugger;
  for (var k = len - 1; k >= 0; k--) {
    console.log('C[arr[l] - 1]===>',C[arr[k]] - 1,'arrk===>',arr[k]);
    B[C[arr[k]] - 1] = arr[k];
    C[arr[k]]--;
  }
  console.timeEnd('计数排序耗时');
  return B;
}
var arr = [2,1,2];
console.log(countingSort(arr)); //[1,9]

3.计数排序动图演示

1.算法简介

2.算法描述和实现

/*
  方法说明：桶排序
  @param {Array} 数组
  @param {Number} 桶的数量
*/

function bucketSort(arr,num) {
  if (arr.length <= 1) {
    return arr;
  }
  var len = arr.length;
  var buckets = [];
  var result = [];
  var min = max = arr[0];
  var regex = '/^[1-9]+[0-9]*$/';
  var space,n = 0;

  console.log('排序长度 ===>',len);

  // 定义桶的数量
  num = num || (num > 1 && regex.test(num) ? num : 10);
  console.log('桶排序耗时');
  // 寻找到最大值和最小值
  for (var i = 0; i < len; i++) {
    min = (min <= arr[i]) ? min : arr[i];
    max = (max >= arr[i]) ? max : arr[i];
  }
  console.log('最大值===> max',max,'最小值===> min',min);

  space = (max - min + 1) / num;

  for (var j = 0; j < len; j++) {
    var index = Math.floor((arr[j] - min) / space);
    console.log(`第${j}项，值==> ${arr[j]} 桶的索引为 ${index},space ===> ${space}`);
    if (buckets[index]) { // 非空桶，插入排序
      var key = arr[j];
      var k = buckets[index].length - 1;
      while (k >= 0 && buckets[index][k] > key) {
        buckets[index][k + 1] = buckets[index][k];
        k--;
      }
      buckets[index][k + 1] = key;
    } else { // 空桶初始化
      buckets[index] = [];
      buckets[index].push(arr[j]);
    }
  }

  while (n < num) {
    result = result.concat(buckets[n]);
    n++;
  }
  console.log('桶排序完成===>',buckets);
  return result;
}



var arr = [3,48];
console.log(bucketSort(arr,4));//[2,50]

/*方法说明：桶排序
@param  array 数组
@param  num   桶的数量*/
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);
    console.time('桶排序耗时');
    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++;
    }
    console.timeEnd('桶排序耗时');
    return result;
}
var arr=[3,50]

3.桶排序图示

1.算法简介

2.算法描述和实现

/*
  基数排序适用于：
    (1)数据范围比较小,建议小于1000
    (2)每个数值都要大于等于0
  
  @param {Array} arr 待排序数组
  @param {Number} 最大位数
*/
function radixSort(arr,maxDigit) {
  var mod = 10;
  var dev = 1;
  var counter = [];

  console.time('基数排序耗时');
  for (var i = 0; i < maxDigit; i++,mod *= 10,dev *= 10) {
    for (var j = 0,len = arr.length; j < len; j++) {
      var bucket = parseInt((arr[j] % mod) / dev);
      console.log('基数===>',bucket);
      if (counter[bucket] == null) {
        counter[bucket] = [];
      }
      counter[bucket].push(arr[j]);
    }

    console.log('第一次排序完成===>',counter);
    // 将排序好的再次重整排列
    var pos = 0;
    for (var j = 0; j < counter.length; j++) {
      console.log('counter[j] ===>','j===>',j,counter[j]);
      if (counter[j] != null) {
        while ((value = counter[j].shift()) != null) {
          arr[pos++] = value;
        }
      }
    }
    console.log('第一次排序完成 arr ===>',arr);
  }

  console.timeEnd('基数排序耗时');
  return arr;
}

var arr = [3,48];
console.log(radixSort(arr,2)); //[2,50]