几种常用的排序—js实现

[ttop5]

时间复杂度

算法(用于数组)	时间复杂度
冒泡排序	O(n^2)
选择排序	O(n^2)
插入排序	O(n^2)
归并排序	O(n * log(n))
快速排序	O(n * log(n))

1. 冒泡排序

比较任何两个相邻的项，如果第一个比第二个大，则交换他们，最后得到一个升序数组。

function modifiedBubbleSort(array) {
  const len = array.length;
  for (let i=0; i<len; i++) {
    for (let j=0; j<len-1-i; j++) {
      if (array[j] > array[j+1]) {
        [array[j], array[j+1]] = [array[j+1], array[j]];
      }
    }
  }
  return array;
}

2. 选择排序

每次找出最小值，与最小索引进行交换，最终得到一个升序数组。

function selectionSort(array) {
  const len = array.length;
  let indexMin;
  for (let i=0; i<len-1; i++) {
    indexMin = i;
    for (let j=i; j<len; j++) {
      if (array[indexMin] > array[j]) {
        indexMin = j;
      }
    }
    if (i !== indexMin) {
      [array[i], array[indexMin]] = [array[indexMin], array[i]];
    }
  }
  return array;
}

3. 插入排序

每次排一个数组项，以此方式构建最后的排序数组，默认第一项已经排序了。

function insertionSort(array) {
  const len = array.length;
  for (let i=1; i<len; i++) {
    let j = i;
    const tmp = array[i];
    while (j>0 && array[j-1] > tmp) {
      array[j] = array[j-1];
      j--;
    }
    array[j] = tmp;
  }
  return array;
}

4. 归并排序

首先将原始数组分割直至只有一个元素的子数组，然后开始归并。归并过程也会完成排序，直至原始数组完全合并并完成排序。

/* 排序并合并 */
function merge(left, right) {
   const result = [];
   while (left.length > 0 && right.length > 0) {
       if (left[0] < right[0]) {
           result.push(left.shift());
       } else {
           result.push(right.shift());
       }
   }
   /* 当左右数组长度不等.将比较完后剩下的数组项链接起来即可 */
   return result.concat(left).concat(right);
}

function mergeSort(array) {
   if (array.length == 1) return array;
   /* 首先将无序数组划分为两个数组 */
   const mid = Math.floor(array.length / 2);
   const left = array.slice(0, mid);
   const right = array.slice(mid);
   /* 递归分别对左右两部分数组进行排序合并 */
   return merge(mergeSort(left), mergeSort(right));
}

5. 快速排序

和归并排序一样，快速排序也使用分治的方法，将原始数组分为较小的数组（但它没有像归并排序那样将它们分割开）。

function quickSort(array){
  //如果数组<=1,则直接返回
  if (array.length <= 1) {
    return array;
  }
  const pivotIndex = Math.floor(array.length / 2);
  //找基准，并把基准从原数组删除
  const pivot = array.splice(pivotIndex, 1)[0];
  const left = [];
  const right = [];

  //比基准小的放在left，比基准大的放在right
  for (let i=0; i<array.length; i++) {
    if (array[i] <= pivot) {
      left.push(array[i]);
    } else {
      right.push(array[i]);
    }
  }
  //递归
  return quickSort(left).concat([pivot],quickSort(right));
}