排序算法

[wang1dot0]

1 冒泡排序

首先，最常见得排序

function bubbleSort(list) {
  const len = list.length;
  for (let i = 0; i < len; i ++) {
    for (let j = len - 1; j > i; j --) {
      if (list[j] > list[j - 1]) {
        let temp = list[j];
        list[j] = list[j - 1];
        list[j - 1] = temp; 
      }
    }
  }

  return list;
}

这种常见得冒泡排序算法是可以优化的，可能在循环结束前，排序已经实现了。下面是优化算法：

function bubbleSortOptimize(list) {
  const len = list.length;
  let flag = true;
  for (let i = 0; i < len && flag; i ++) {
    flag = false;
    for (let j = len - 1; j > i; j --) {
      if (list[j] > list[j - 1]) {
        let temp = list[j];
        list[j] = list[j - 1];
        list[j - 1] = temp; 
        flag = true;
      }
    }
  }

  return list;
}

时间复杂度：O(n2)

2 简单选择排序

核心思想：通过从n-1次关键字间作比较，从n-i+1个记录中选出关键字最小的记录

function simpleSelectSort(list) {
  const len = list.length;
  let min = 0;
  for (let i = 0; i < len; i ++) {
    min = i;
    for (let j = i + 1; j < len; j ++) {
      if (list[min] > list[j]) {
        min = j;
      }
    }
    if (i !== min) {
      let temp = list[min];
      list[min] = list[i];
      list[i] = temp;
    }
  }

  return list;
}

时间复杂度: O(n2)