前端常见排序

快速排序

var quickSort = function (arr) {
  if (arr.length <= 1) return arr;
  var pivotIndex = Math.floor(arr.length / 2);
  var pivot = arr.splice(pivotIndex, 1)[0];
  var left = [];
  var right = [];
  for (var i = 0; i < arr.length; i++) {
    if (arr[i] < pivot) {
      left.push(arr[i]);
    } else {
      right.push(arr[i]);
    }
  }
  return quickSort(left).concat([pivot], quickSort(right));
};

function quickSort(arr) {
  if (arr.length <= 1) return arr;
  const left = [];
  const right = [];
  const mid = arr.shift();

  arr.forEach((item) => {
    if (item <= mid) left.push(item);
    else right.push(item);
  });

  return quickSort(left).concat(mid).concat(quickSort(right));
}

二分查找是我们目前为止遇到的第一个时间复杂度为 O(logn) 的算法。

冒泡排序

var sort = (arr) => {
  for (let i = 0; i < arr.length - 1; i++) {
    for (let j = 0; j < arr.length - 1 - i; j++) {
      if (arr[j] > arr[j + 1]) {
        let swap = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = swap;
      }
    }
  }
  return arr;
};
var arr = [32, 12, 56, 78, 76, 45, 36];
sort(arr);
console.log(arr);

归并排序

// 归并排序算法, A是数组，n表示数组大小
merge_sort(A, n) {
  merge_sort_c(A, 0, n-1)
}

// 递归调用函数
merge_sort_c(A, p, r) {
  // 递归终止条件
  if p >= r  then return

  // 取p到r之间的中间位置q
  q = (p+r) / 2
  // 分治递归
  merge_sort_c(A, p, q)
  merge_sort_c(A, q+1, r)
  // 将A[p...q]和A[q+1...r]合并为A[p...r]
  merge(A[p...r], A[p...q], A[q+1...r])
}


merge(A[p...r], A[p...q], A[q+1...r]) {
  var i = p，j = q+1，k = 0 // 初始化变量i, j, k
  var tmp = new array[0...r-p] // 申请一个大小跟A[p...r]一样的临时数组
  while( i<=q  &&  j<=r  ){
    if A[i] <= A[j] {
      tmp[k++] = A[i++] // i++等于i=i+1
    } else {
      tmp[k++] = A[j++]
    }
  }

  // 判断哪个子数组中有剩余的数据
  var start = i，end = q
  if (j<=r) { start = j, end:=r}

  // 将剩余的数据拷贝到临时数组tmp
  while start <= end do {
    tmp[k++] = A[start++]
  }

  // 将tmp中的数组拷贝回A[p...r]
  for i:=0 to r-p do {
    A[p+i] = tmp[i]
  }
}

插入排序

function sort(elements) {
  for (var i = 1; i < elements.length; i++) {
    if (elements[i] < elements[i - 1]) {
      // 取出无序数列中第i个作为被插入元素
      var gurd = elements[i];
      //记住有序数列的最后一个位置，并且将有序数列位置扩大一个
      var j = i - 1;
      // 比大小， 找到被插入元素所在的位置
      while (j >= 0 && gurd < elements[j]) {
        elements[j + 1] = elements[j];
        j--;
      }
      elements[j + 1] = gurd;
    }
  }
}