Javascript 排序算法（转）

1.快速排序

class QuickSort {
  Sort(originalArray) {
    // 复制 originalArray 数组防止它被修改
    const array = [...originalArray];

    // 如果 originalArray 数组元素个数 <=1，就不需要排序了，直接返回
    if (array.length <= 1) {
      return array;
    }

    // 初始化左数组和右数组
    const leftArray = [];
    const rightArray = [];

    // 取出 originalArray 数组中的第一个元素作为中间比较值
    const pivotElement = array.shift();
    const centerArray = [pivotElement];

    // 把 originalArray 数组拆分成左、中、右三个数组
    while (array.length) {
      const currentElement = array.shift();

      if (currentElement == pivotElement) {
        centerArray.push(currentElement);
      } else if (currentElement < pivotElement) {
        leftArray.push(currentElement);
      } else {
        rightArray.push(currentElement);
      }
    }

    // 递归对左、右数组进行排序
    const leftArraySorted = this.Sort(leftArray);
    const rightArraySorted = this.Sort(rightArray);

    // 最后把排好序的左、中、右数组拼接起来，并返回
    return leftArraySorted.concat(centerArray, rightArraySorted);
  }
}

更多相关文章

随机推荐