JavaScript 数据结构与算法 之 排序算法

排序算法

冒泡排序

function bubbleSort(array, compareFn = defaultCompare) {
  const { length } = array;
  for (let i = 0; i < length; i++) {
    for( let j = 0; j < length - 1; j++) {
      if (compareFn(array[j], array[j + 1]) === Compare.BIGGER_THAN) {
        swap(array, j, j + 1);
      }
    }
  }
  return array;
}
function swap(array, a, b) {
  [array[a], array[b]] = [array[b], array[a]];
}

优化，从内循环中减去外循环中已跑过的轮数

function modifiedBubbleSort(array, compareFn = defaultCompare) {
  const { length } = array;
  for (let i = 0; i < array.length; i++) {
    for (let j = 0; j < array.length - 1 - i; j++) {
      if (compareFn(array[j], array[j + 1]) === Compare.BIGGER_THAN) {
        swap(array, j, j + 1);
      }
    }
  }
  return array;
}

优化，设置标志性变量 pos，隐喻记录每趟排序中最后一次进行交换的位置，由于 pos 位置之后的记录均已狡猾到位，所以下一趟排序时，只要扫描到 pos 位置即可

function bubbleSort2(array, compareFn = defaultCompare) {
  let i = array.length - 1; // 初始时，最后位置保持不变
  while (i > 0) {
    let pos = 0; // 每趟开始时，无交换记录
    for (let j = 0; j < i; j++) {
      if (compareFn(array[j], array[j + 1]) === Compare.BIGGER_THAN) {
        pos = j; // 记录交换的位置
        swap(array, j, j + 1);
      }
    }
    i = pos; // 为下一趟排序做准备
  }
  return array;
}

优化，传统冒泡排序中每一趟排序操作只能找到一个最大值或最小值，我们考虑利用在每趟排序中进行正向和反向两遍冒泡的方法一次可以得到两个最终值，从而使排序趟数几乎少了一半。

function bubbleSort3(array, compareFn = defaultCompare) {
  let low = 0;
  let high = array.length - 1;
  let tmp, j;
  while (low < high) {
    for (j = low; j < high; ++j) { // 正向冒泡找到最大者
      if (compareFn(array[j], array[j + 1]) === Compare.BIGGER_THAN) {
        swap(array, j, j + 1);
      }
    }
    --high; // 修改 high 值，前移一位
    for (j = high; j > low; --j) { // 反向冒泡，找到最小者
      if (compareFn(array[j], array[j - 1]) === Compare.LESS_THAN) {
        swap(array, j, j - 1);
      }
    }
    --low;
  }
  return array;
}

选择排序

找到数据结构的最小值并将其放置在第一位，接着找到第二小的并将其放置在第二位，以此类推

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

插入排序

插入排序每次排一个数组项，以此方式构建最后的排序数组。假定第一项已经排序，接着，它和第二项进行比较——第二项是应该待在原位还是插到第一项之前呢？这样，头两项就已正确排序，接着和第三项比较，以此类推

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

• 希尔排序

简单插入排序的改进版，优先比较较远距离的元素，也叫缩小增量排序
实现：
先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序

1. 选择一个增量序列t₁, t₂,...,t_k,其中 t_i > t_j,t_k = 1
2. 按增量序列个数 k，对序列进行 k 趟排序
3. 每趟排序，根据对应的增量 t_i，将待排序列分割成若干长度为 m 的子序列，分别对各子表进行直接插入排序。仅增量因子为 1 时，整个序列作为一个表来处理，表长度即为整个序列的长度

function shellSort(arr) {
  var len = arr.length,
      temp,
      gap = 1;
  // 动态定义间隔序列
  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;
    }
  }
  return arr;
}

归并排序

归并排序是一种分而治之算法。思想是将原始数据切分成较小的数组，直到每个小数组只有一个位置，接着将 小数组归并成较大的数组，直到最后只有一个排序完毕的大数组。

function mergeSort(array, compareFn = defaultCompare) {
  if (array.length > 1) {
    const { length } = array
    const middle = Math.floor(length / 2);
    const left = mergeSort(array.slice(0, middle), compareFn);
    const right = mergeSort(array.slice(middle, length), compareFn);
    array = merge(left, right, compareFn);
  }
  return array;
}
function merge(left, right, compareFn) {
  let i = 0;
  let j = 0;
  const result = [];
  while (i < left.length && j < right.length) {
    if (compareFn(left[i], right[j]) === Compare.LESS_THAN) {
      result.push(left[i++]);
    } else {
      result.push(right[j++]);
    }
  }
  if (i < left.length) {
    result.concat(left.slice(i));
  } else {
    result.concat(right.slice(j));
  }
  return result;
}

快速排序

步骤

1. 首先，从数组中选择一个值作为主元，即数组中间那个值
2. 划分：创建两个指针（引用），左边一个指向数组的第一个值，右边指向数组最后一个值。移动左指针，直到我们找到一个比主元大的值，接着移动右指针直到找到一个比主元小的值，然后交换他们，重复这个过程，直到左指针超过了右指针。这个过程将使得比主元小的值都排在主元之前，比主元大的值都排在主元之后
3. 算法对划分后的小数组（较主元小的值组成的子数组，以及较主元大的值组成的子数组）重复之前的两个步骤，直至数组已经完全排序。

function quicksort(array, compareFn = defaultCompare) {
  return quick(array, 0, array.length - 1, compareFn);
}