关于算法:排序算法

排序算法

本文解说冒泡排序，疾速排序，归并排序 三种排序算法的思路和编码

冒泡排序

思路：顺次比拟相邻的两个数，将比拟小的数放在后面，比拟大的数放在前面。
直到跑完一次，这时候，最大的数就放在最初一个地位了，在了它排序后应该在的地位了。依此类推，再把第二大的数冒泡到倒数第二个地位, 跑 i 次，把 i 个数都放到它指定的地位，排序实现。

function bubbleSort(arr) {
  const len = arr.length;
  for (let i = 0; i < len; i++) {
    // 每次把最大值冒泡到最初
    for (let j = 1; j < len - i; j++) {if (arr[j - 1] > arr[j]) {[arr[j - 1], arr[j]] = [arr[j], arr[j - 1]];
      }
    }
  }
  return arr;
}

疾速排序

思路：设定一个分界值，通过该分界值将数组分成左右两局部，把小于它的，放在右边，大于它的，放在左边。
跑完一次，那么分界值就在了它本人应该在的地位（因为右边的都小于它，左边的都大于它），宰割的两端持续依照这个逻辑去跑（递归）。

function quickSort(arr) {const sort = (L, R) => {if (L >= R) return;
    let l = L;
    let r = R;
    // 抉择一个基准值，把小于它的，放在右边，大于它的，放在左边
    // 拆分后的两端持续这样做
    const pivot = arr[l];
    while (l < r) {while (l < r && arr[r] > pivot) r--;
      if (l < r) {arr[l] = arr[r];
      }
      while (l < r && arr[l] < pivot) l++;
      if (l < r) {arr[r] = arr[l];
      }
    }
    arr[l] = pivot;
    sort(L, r - 1);
    sort(r + 1, R);
  };
  sort(0, arr.length - 1);
  return arr;
}

归并排序

思路：将数组拆分为两局部，别离对两个子数组进行递归拆分。直到无奈再分，这时候进行两两合并（归并），合并后的子序列是有序的，也就是合并两个有序的子序列。合并实现即为最初排序后的后果。

function mergeSort(arr) {const merge = (sortV1, sortV2) => {let sortValue = [];
    let i = 0,
      j = 0;
    while (i < sortV1.length && j < sortV2.length) {if (sortV1[i] > sortV2[j]) {sortValue.push(sortV2[j]);
        j++;
      } else {sortValue.push(sortV1[i]);
        i++;
      }
    }
    if (i < sortV1.length) {sortValue = sortValue.concat(sortV1.slice(i, sortV1.length));
    } else if (j < sortV2.length) {sortValue = sortValue.concat(sortV2.slice(j, sortV2.length));
    }
    return sortValue;
  };

  const sort = (arr) => {if (arr.length === 1) return arr;
    let mid = Math.floor(arr.length / 2);
    let v1 = arr.slice(0, mid);
    let v2 = arr.slice(mid, arr.length);
    const sortV1 = sort(v1);
    const sortV2 = sort(v2);
    return merge(sortV1, sortV2);
  };

  return sort(arr);
}