Pengjielee's blog

算法度量

1、算法内存使用

原地排序（Sorted in place）算法，特指空间复杂度是 O(1) 的排序算法。

2、算法的稳定性

经过某种排序算法排序之后：

如果两个元素的前后顺序没有改变，那我们就把这种排序算法叫作稳定的排序算法；
如果前后顺序发生变化，那对应的排序算法就叫作不稳定的排序算法。

冒泡排序

var bubbleSort = (arr) => {
  const n = arr.length;

  if (n <= 1) {
    return;
  }

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

测试：

var arr = [4, 5, 6, 3, 2, 1];
bubbleSort(arr);
console.log(arr); //[1, 2, 3, 4, 5, 6]

优化：

var bubbleSort2 = (arr) => {
  const n = arr.length;

  if (n <= 1) {
    return;
  }

  for (let i = 0; i < n; i++) {
    // 提前退出的标志位
    let flag = false;
    for (let j = 0; j < n - i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        const temp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
        // 有数据交换
        flag = true;
      }
    }
    // 没有数据交换，提前退出
    if (!flag) {
      break;
    }
  }
};

测试：

var arr = [3, 5, 4, 1, 2, 6];
bubbleSort2(arr);
console.log(arr); //[1, 2, 3, 4, 5, 6]

插入排序

插入算法的核心思想是取未排序区间中的元素，在已排序区间中找到合适的插入位置将其插入，并保证已排序区间数据一直有序。

步骤：

从第一个元素开始，该元素可以认为已经被排序；
取出下一个元素，在已经排序的元素序列中从后向前扫描；
如果该元素（已排序）大于新元素，将该元素移到下一位置；
重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；
将新元素插入到该位置后；
重复步骤2 ~ 5；

代码：

var insertSort = (arr) => {
  const n = arr.length;
  if (n <= 1) {
    return;
  }

  // 从下标1开始，第一个元素认为已经被排序
  for (let i = 1; i < n; i++) {
    // 取出当前元素
    let value = arr[i];

    // 从已排序区间中查找插入位置（从后向前扫描）
    let j = i - 1;
    // 查找插入的位置
    for (; j >= 0; j--) {
      if (arr[j] > value) {
        // 移动数据
        arr[j + 1] = arr[j];
      } else {
        break;
      }
    }
    // 插入数据
    arr[j + 1] = value;
  }
};

选择排序

选择排序分已排序区间和未排序区间。选择排序每次会从未排序区间中找到最小的元素，将其放到已排序区间的末尾。

步骤：

在未排序序列中找到最小（大）元素，存放到排序序列的起始位置；
从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾；
重复第二步，直到所有元素均排序完毕；

代码：

var selectSort = (arr) => {
  // 最小元素下标
  let min;

  for (let i = 0; i < arr.length; i++) {
    // 临时设置最小元素下标为i
    min = i;

    // 从未排序区间找到最小的元素下标
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[j] < arr[min]) {
        min = j;
      }
    }

    // 如果当前元素下标与最小元素下标不相等，则交换
    if (i != min) {
      const temp = arr[i];
      arr[i] = arr[min];
      arr[min] = temp;
    }
  }
};

冒泡/插入/选择

	是原地排序？	是稳定排序?	最好	最坏	平均
冒泡排序	是	是	O(n)	O(n^2)	O(n^2)
插入排序	是	是	O(n)	O(n^2)	O(n^2)
选择排序	是	否	O(n^2)	O(n^2)	O(n^2)

归并排序

function mergeSort(arr) {
  // return once we hit an array with a single item
  if (arr.length === 1) {
    return arr;
  }
  // get the middle item of the array rounded down
  const middle = Math.floor(arr.length / 2); 
  // items on the left side
  const left = arr.slice(0, middle); 
  // items on the right side
  const right = arr.slice(middle); 

  var result = merge(mergeSort(left), mergeSort(right));
  return result;
}

// 归并操作
function merge(left, right) {
  let result = [];
  let indexLeft = 0;
  let indexRight = 0;
  let current = 0;

  while (current < left.length + right.length) {
    let isLeftEnd = indexLeft >= left.length;
    let isRightEnd = indexRight >= right.length;

    var flag =
      !isLeftEnd && (isRightEnd || left[indexLeft] < right[indexRight]);
    if (flag) {
      result[current] = left[indexLeft];
      indexLeft++;
    } else {
      result[current] = right[indexRight];
      indexRight++;
    }
    current++;
  }
  return result;
}

快速排序

快速排序使用分治法（Divide and conquer）策略来把一个序列（list）分为两个子序列（sub-lists）。

步骤：

从数列中挑出一个元素，称为”基准”（pivot），
重新排序数列，所有比基准值小的元素放在基准前面，所有比基准值大的元素放在基准后面（相同的数可以到任何一边）。在这个分区结束之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。
递归地（recursively）把小于基准值元素的子数列和大于基准值元素的子数列排序。
递归到最底部时，数列的大小是零或一，也就是已经排序好了。这个算法一定会结束，因为在每次的迭代（iteration）中，它至少会把一个元素摆到它最后的位置去。

代码：

// 交换函数
function swap(arr, a, b) {
  var temp = arr[a];
  arr[a] = arr[b];
  arr[b] = temp;
}

// 分区函数
function partition(arr, low, high) {
  var i = low;
  var j = high;

  // 取数组中间的数为基准数
  var pivot = arr[Math.floor((low + high) / 2)];

  // 这里是小于等于
  while (i <= j) {
    // 比基准数小，i++
    while (arr[i] < pivot) {
      i++;
    }
    // 比基准数大，j--
    while (arr[j] > pivot) {
      j--;
    }
    // 不太懂？
    if (i <= j) {
      swap(arr, i, j);
      i++;
      j--;
    }
  }
  return i;
}

// 递归排序函数
function sort(arr, low, high) {
  // 这里是绝对小于
  if (low < high) {
    var pivotIdx = partition(arr, low, high);
    sort(arr, low, pivotIdx - 1);
    sort(arr, pivotIdx, high);
  }
  return arr;
}

function quickSort(arr) {
  return sort(arr, 0, arr.length - 1);
}