前端的排序算法总结

参考 lianjie

冒泡排序

典型的排序方法，命名来自鱼呼吸时吹出的气泡，上层的气泡总是最大的。

思路：两层循环，内层循环对比相邻两个数据（j,j+1），假设 j > j + 1 则交换元素位置。
外层循环为长度限制，在内层第一次循环完成后减少长度 1（因为最后一个泡已经固定，为这个数组的最大值）

function bubbleSort(arr){for(let i = 0; i < arr.length - 1; i++){
    let flag = false;
    for(let j = 0; j < arr.length - i - 1; j++){if(arr[j] > arr[j + 1]){let temp = arr[j];
          arr[j] = arr[j+1];
          arr[j+1] = temp;;
          flag = true;
      }
    }
    if(!flag){break;}
  }
  return arr;
}

加一个标志位 flag，如果没有进行交换，将标志位置为 false，表示排序完成。

• 时间复杂度 O(n^2)，最优情况下是 O(n)
• 空间复杂度 O(1)

选择排序

顾名思义，每次都选择最小的，然后交换位置

思路：两层循环，内层循环为选取第一个位置的值，然后将它与剩下的值作对比，得到比它小的则交换位置。外层循环为控制第一位值的固定（一次循环后，第一位则为该数组最小的值，下一次循环不必带上）。

function selectionSort(arr){for(let i = 0; i < arr.length - 1; i++){
    let index = i;
    for(let j = i+1; j < arr.length; j++){
    // 判断是否有小于当前值，有则交换位置
      if(arr[index] > arr[j]){index = j;}
    }
      let temp = arr[i];
      arr[i] = arr[index];
      arr[index] = temp;
  }
  return arr;
}

• 时间复杂度：O(n^2)，属于不稳定的算法（每次交换之后，它都改变了后续数组的顺序）
• 空间复杂度：O(1)

快速排序

思路：二分法，先找一个基数，分隔出以基数为界的左右两个数组，然后递归重复这个步骤，直到分组剩余一个数，则我们认为已经排列完成。

function quickSort(arr){if(arr.length <= 1){return arr;}
  let temp = arr[0];
  const left = [];
  const right = [];
  for(var i = 1; i < arr.length; i++){if(arr[i] > temp){right.push(arr[i]);
    }else{left.push(arr[i]);
    }
  }
  return quickSort(left).concat([temp], quickSort(right));
}

• 时间复杂度：O(n*logn)，属于不稳定的算法, 特殊情况下会是 O(n^2)
• 空间复杂度：辅助空间是 logn，所以空间复杂度为 O(logn)