排序算法

[OPY-bbt]

// 排序：基本思路一样，将原数组分为两块，已排序和未排序。每次从未排序块中取出数，
// 放入已排序块中合适位置，平均时间复杂度O(n2)
// 1. 冒泡排序
// 2. 插入排序
// 3. 选择排序
// 4. 插入排序优化版本，希尔排序，利用缩小增量的方法 增量一般取值为length/2、length/4 .... 1;
//    将列表中所有元素，已增量间隔相同的分为一组，使用插入排序，最后增量迭代到1。
//    解决了普通插入排序每次只能将数据移动一位的低效。
// 5. 归并排序
// 6. 快速排序-原理版
// 7. 快速排序-优化版
// 8. 桶排序：将数据放在不同的桶里，桶之间有顺序，每个桶内部使用快速排序，最后按次取出，
//    即完成排序。
//    适合外部排序中。数据量比较大，内存有限，无法一次读入内存中。
// 9. 计数排序：在一个数组中保存数据所在的序号，当存入结果数组中时，将序号减一。
//    适合数据范围比较小的情况
// 10. 基数排序：数据要有进位的特点，先从最低位开始排，然后遍历排序到高位。
//    比如说对大量电话号码排序，就可以用此方法

const data = [1, 4, 6, 2, 9, 2];

// 冒泡排序：每次循环都会确定一个数据的位置
function bubbleSort(arr) {
  const len = arr.length;

  for (let i = 0; i < len - 1; i++) {

    for (let j = 0; j < len - i - 1; j++) {
      if (arr[j] > arr[j+1]) {
        const tmp = arr[j];
        arr[j] = arr[j+1];
        arr[j+1] = tmp;
      }
    }
  }

  return arr;
}
// console.log(bubbleSort(data));

// 插入排序：从未排序块中取出一个数，插入到已排序块中的合适位置
function insertionSort(arr) {
  const len = arr.length;

  for(let i = 1; i < len; i++) {

    let num = arr[i];
    for (let j = i - 1; j >= 0; j--) {
      if (num < arr[j]) {
        arr[j+1] = arr[j];
      } else {
        arr[j+1] = num;
        break;
      }
    }
  }

  return arr;
}
// console.log(insertionSort(data));

// 选择排序：每次从未排序块中取出最小的数，放在已排序块末尾
function selectionSort(arr) {
  const len = arr.length;

  for(let i = 0; i < len; i++) {
    let min = arr[i];
    let minIndex = i;

    for(let j = i; j < len; j++) {
      if (arr[j] < min) {
        min = arr[j];
        minIndex = j;
      }
    }

    const tmp = arr[i];
    arr[i] = min;
    arr[minIndex] = tmp;
  }

  return arr;
}
// console.log(selectionSort(data));

[OPY-bbt]

// 归并排序：分组单独排序，然后合并
function mergeSort(arr) {
  const len = arr.length;

  if (len <= 1) {
    return arr;
  }

  const index = Math.floor(len / 2);

  return merge(mergeSort(arr.slice(0, index)), mergeSort(arr.slice(index)));
}

function merge(arr1, arr2) {
  let res = [];

  let i = 0;
  let j = 0;
  while(i < arr1.length && j < arr2.length) {
    if (arr1[i] <= arr2[j]) {
      res.push(arr1[i++]);
    } else {
      res.push(arr2[j++]);
    }
  }

  if (i !== arr1.length) {
    res = res.concat(arr1.slice(i));
  }

  if (j !== arr2.length){
    res = res.concat(arr2.slice(j));
  }

  return res;
}
// console.log(mergeSort(data));

// 快速排序：找一个基准数，左侧放小于其的数，右侧放大于的。直到需要排序的数量缩减为1
function quickSort(arr) {
  if (arr.length <= 1) { return arr; }

  const pivotIndex = Math.floor(arr.length / 2);
  const pivot = arr.splice(pivotIndex, 1)[0];

  const left = [];
  const right = [];

  for (let 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));
}
// console.log(quickSort(data));

[OPY-bbt]

// 快速排序：元素交换
function quickSort2(arr, p = 0, r = arr.length - 1) {
  if (p >= r) return arr;

  const q = partition(arr, p, r);
  quickSort2(arr, p, q - 1);
  quickSort2(arr, q + 1, r);

  return arr;
}

function partition(arr, p, r) {
  const pivot = arr[r];

  let anchor = p;
  for (let i = p; i <= r; i++) {
    if (arr[i] < pivot) {
      [arr[i], arr[anchor]] = [arr[anchor], arr[i]]

      anchor++;
    }
  }

  [arr[anchor], arr[r]] = [arr[r], arr[anchor]];

  return anchor;
}
console.log(quickSort2(data));