排序算法

冒泡排序

相邻的两个元素依次比较,小的放在左边。

选择排序

从未排序序列中找到最大(小)值存放到已排序序列末尾。

插入排序

从已排序序列中找到小于或等于当前数的位置并插到其后。

希尔排序

归并排序

归并排序(merge sort)是创建在归并操作上的一种有效的排序算法。归并操作(merge),也叫归并算法,指的是将两个已经排序的序列合并成一个序列的操作。归并排序算法依赖归并操作。

排序算法 - 图1

递归方式

此方式不改变原数组。

  1. function merge( left, right ) {
  2. const arr = [];
  3. const ll = left.length;
  4. const rl = right.length;
  5. let li = 0;
  6. let ri = 0;
  7. while ( li < ll && ri < rl ) {
  8. if ( left[li] <= right[ri] ) {
  9. arr.push(left[li++]);
  10. }
  11. else {
  12. arr.push(right[ri++]);
  13. }
  14. }
  15. while ( li < ll ) {
  16. arr.push(left[li++]);
  17. }
  18. while ( ri < rl ) {
  19. arr.push(right[ri++]);
  20. }
  21. return arr;
  22. }
  23. function mergeSort( arr ) {
  24. const len = arr.length;
  25. if ( len < 2 ) {
  26. return arr;
  27. }
  28. const mid = Math.floor(len / 2);
  29. return merge(mergeSort(arr.slice(0, mid)), mergeSort(arr.slice(mid)));
  30. }

快速排序