博客

一、快速排序


快速排序是对冒泡排序的一种改进，是目前已知最快的排序方法。



原理：

首先取一基准，第一趟排序时将数据分成两部分，然后递归调用，在两边都实行快速排序。


优点：

极快，数据移动少。


缺点：

不稳定。

function quickSort(arr) {
  if (arr.length <= 1) {
    return arr
  }
  var middle = Math.floor(arr.length / 2);
  var middleData = arr.splice(middle, 1)[0];//取一基数

  var left = [];
  var right = [];
  
  for (var i = 0; i < arr.length; i++) {
    if (arr[i] < middleData) {
      left.push(arr[i]);
    } else {
      right.push(arr[i]);
    }
  }

  return quickSort(left).concat([middleData], quickSort(right));
}
 
var Arr = [3, 5, 74, 64, 64, 3, 1, 8, 3, 49, 16, 161, 9, 4]
console.log( "快速排序前：", Arr);
var newArr = quickSort(Arr)
console.log("快速排序后：", newArr);

二、插入排序

function insertSort(arr) {
  var len = arr.length;
  for (var i = 1; i < len; i ++) {
      var temp = arr[i];
      var j = i - 1;//默认已排序的元素
      while (j >= 0 && arr[j] > temp) {  //在已排序好的队列中从后向前扫描
              arr[j+1] = arr[j]; //已排序的元素大于新元素，将该元素移到一下个位置
              j --;
          }
      arr[j+1] = temp;
      }
  return arr
}

var Arr = [3, 5, 74, 64, 64, 3, 1, 8, 3, 49, 16, 161, 9, 4]
console.log("插入排序前：", Arr);
insertSort(Arr);
console.log("插入排序后：", Arr);

三、冒泡排序

原理：

比较两个相邻的元素，将值大的元素交换到右边。


实现思路：

依次比较相邻的两个数，将比较小的数放在前面，比较大的数放在后面。


优点：

比较简单，空间复杂度较低，是稳定的。


缺点：

时间复杂度太高，效率不好。

function bubbleSort(arr) {
  for (var i = 0; i < arr.length; i++) {
    for (var j = 0; j < arr.length - i; j++) {
      if (arr[j] > arr[j + 1]) {
        var temp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
      }
    }
  }
}

var Arr = [3, 5, 74, 64, 64, 3, 1, 8, 3, 49, 16, 161, 9, 4];
console.log("冒泡排序前：", Arr);
bubbleSort(Arr)
console.log("冒泡排序后：", Arr );

四、选择排序

function selectionSort(arr) {
  if(arr.length <= 0) return arr;
  
  var minIndex;

  for(var i = 0; i < arr.length; i ++) {  //比较的次数
    minIndex = i;
    for(var j = i; j < arr.length; j ++) {//寻找最小值
      minIndex = j; //保存最小值的索引
    }
    [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
  } 
  return arr;
}

console.log(selectionSort([2, 3, 5, 7, 3, 32, 34, 56, 1]));

五、归并排序

function mergeSort (arr) {
  let len = arr.length;
  if (len < 2) {
      return arr;
  }
  let middle = Math.floor(len / 2);
  //拆分成两个子数组
  let left =  arr.slice(0, middle);
  let right = arr.slice(middle, len);
  //递归拆分
  let mergeSortLeft = mergeSort(left);
  let mergeSortRight = mergeSort(right);
  //合并
  return merge( mergeSortLeft,mergeSortRight);
}

function merge (left, right)  {
  const result = [];

  while (left.length && right.length) {
    // 注意: 判断的条件是小于或等于，如果只是小于，那么排序将不稳定
    if (left[0] <= right[0]) {
        result.push(left.shift()); //每次都要删除left或者right的第一个元素，将其加入result中
    } else {
        result.push(right.shift());
    }
  }

  //将剩下的元素加上
  while (left.length) result.push(left.shift());
  while (right.length) result.push(right.shift());

  return result;
};

let test = [1, 2, 45, 64, 4, 75, 3];
console.log(mergeSort(test));

六、算法复杂度