排序算法部分解析

排序算法部分解析(javascript)

时间复杂度

q7t8hT.png

选择排序

方法：遍历数组，找最小，放第一，找第二小，放第二......

实现：

<script>
    let arr = [9, 6, 11, 3, 5, 12, 8, 7, 10, 15, 14, 4, 1, 13, 2];
    for (i = 0; i < arr.length - 1; i++) {
      let min = i;
      for (j = i + 1; j < arr.length; j++) {
        if (arr[j] < arr[min]) {
          min = j;
        }
      }
      swap(arr, min, i);
    }
    function swap(arr, x, y) {
      let temp = arr[x];
      arr[x] = arr[y];
      arr[y] = temp;
    }
    console.log(arr);
</script>

冒泡排序

方法：通过指针不断后移，将大的数向后推

实现：

<script>
  let arr = [9, 6, 11, 3, 5, 12, 8, 7, 10, 15, 14, 4, 1, 13, 2];
  for (i = 0; i < arr.length - 1; i++) {
    for (j = 0; j < arr.length - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        swap(arr, j, j + 1);
      }
    }
  }
  function swap(arr, x, y) {
    let temp = arr[x];
    arr[x] = arr[y];
    arr[y] = temp;
  }
  console.log(arr);
</script>

插入排序

方法：扑克牌，从右向左插入一张牌，放至合适的位置(遇大交换)

实现：

<script>
  let arr = [9, 6, 11, 3, 5, 12, 8, 7, 10, 15, 14, 4, 1, 13, 2];
  for (i = 1; i < arr.length; i++) {
    for (j = i; j > 0; j--) {
      if (arr[j] < arr[j - 1]) {
        swap(arr, j, j - 1);
      } else break;
    }
  }
  function swap(arr, x, y) {
    let temp = arr[x];
    arr[x] = arr[y];
    arr[y] = temp;
  }
  console.log(arr);
</script>

希尔排序(插入排序添加gap间隔)

方法：通过隔位符gap(每隔gap个数)，对数组进行插入排序，然后不断修改间隔，直至为1，排序完成

实现：

<script>
  let arr = [9, 6, 11, 3, 5, 12, 8, 7, 10, 15, 14, 4, 1, 13, 2];
  for (let gap = 4; gap > 0; gap /= 2) {
    for (i = gap; i < arr.length; i++) {
      for (j = i; j > gap - 1; j -= gap) {
        if (arr[j] < arr[j - gap]) {
          swap(arr, j, j - gap);
        } else break;
      }
    }
  }
  function swap(arr, x, y) {
    let temp = arr[x];
    arr[x] = arr[y];
    arr[y] = temp;
  }
  console.log(arr);
</script>

归并排序

方法：将一个数组分成两个有序的部分，用两个指针合并成一个新的数组的过程

实现：(分成的两数组必须各自有序！)

<script>
  function mergeSort(arr) {
      if (arr.length === 1) {
        return arr;
      }
      let mid = Math.floor(arr.length / 2);
      let left = arr.slice(0, mid);
      let right = arr.slice(mid);
      return merge(mergeSort(left), mergeSort(right));
    }
    function merge(left, right) {
      let tmp = [];
      while (left.length && right.length) {
        if (left[0] < right[0]) {
          tmp.push(left.shift());
        } else {
          tmp.push(right.shift());
        }
      }
      return tmp.concat(left, right);
    }
    console.log(mergeSort(arr));
</script>

快速排序

方法：去数组中的一个头或为作为privot标杆，加上两个指针，一头一尾，以其为基准，根据大小将指针移动到合适位置，交换数组值进行排序。

快排算法原理同二叉搜索树

实现：

<script>
  function quickSort(arr) {
      if (arr.length <= 1) {
        return arr;
      }
      let pivotIndex = Math.floor(arr.length / 2);
      let pivot = arr.splice(pivotIndex, 1)[0];
      let left = [];
      let right = [];
      for (i = 0; i < arr.length; i++) {
        if (arr[i] < pivot) {
          left.push(arr[i]);
        } else {
          right.push(arr[i]);
        }
      }
      return quickSort(left).concat(pivot, quickSort(right));
    }
    console.log(quickSort(arr));
</script>