JS实现各种查找算法(不断更新)

单击下面的链接以帮助了解， 只是网页可能会慢慢打开。 我们得等一会儿。

[(click ->)各种排序算法的动画]](https://visualgo.net/zh/sorting)

在实践中， 前三种排序算法的性能太差，通常不使用。

1 . 冒泡排序(未改进) 复杂度O(N2)

function createNonSortedArray(size) {
  const array = [];
  for (let i = size; i > 0; i--) {
    array.push(i);
  }
  return array;
}
function bubbleSort(array) {
  const { length } = array;
  for (let i = 0; i < length; i++) {
    for (let j = 0; j < length - 1; j++) {
      if (array[j] > array[j + 1]) {
        [array[j], array[j + 1]] = [array[j + 1], array[j]];
      }
    }
  }
  return array;
}

let array = createNonSortedArray(7);
array = bubbleSort(array);
console.log(array);

2.气泡排序（改进） 减少外循环从内循环运行的循环数。

function createNonSortedArray(size) {
  const array = [];
  for (let i = size; i > 0; i--) {
    array.push(i);
  }
  return array;
}
function bubbleSort(array) {
  const { length } = array;
  for (let i = 0; i < length - 1; i++) {
    for (let j = 0; j < length - 1 - i; j++) {
      if (array[j] > array[j + 1]) {
        [array[j], array[j + 1]] = [array[j + 1], array[j]];
      }
    }
  }
  return array;
}

let array = createNonSortedArray(7);
array = bubbleSort(array);
console.log(array);

3. 选择排序 复杂度O(N2)

  function createNonSortedArray(size) {
        const array = [];
        for (let i = size; i > 0; i--) {
          array.push(i);
        }
        return array;
      }
      function selectionSort(array) {
        const { length } = array;

        for (let i = 0; i < length - 1; i++) {
          let indexMin = i;
          // 这里，与冒泡不同，是外循环。i array[j]) {
              indexMin = j;
            }

          }

          if (i !== indexMin) {
            [array[i], array[indexMin]] = [array[indexMin], array[i]];
            console.log(array);
          }
        }
        return array;
      }

      let array = createNonSortedArray(7);
      array = selectionSort(array);
      console.log(array);

4. 插入排序

      function createNonSortedArray(size) {
        const array = [];
        for (let i = size; i > 0; i--) {
          array.push(i);
        }
        return array;
      }
      function insertionSort(array) {
        const { length } = array;
        for (let i = 1; i < length; i++) {
          // 保存要插入的值
          let temp = array[i];
          let j = i;
          while (j > 0 && temp < array[j - 1]) {
            // 用前一项的值替换当前值， 为下面的 当前值 准备上一个
            array[j] = array[j - 1];
            j--;
          }
          // 用插入的数据替换他的最后一个号码， 实现换位
          array[j] = temp;
        }
        return array;
      }

      let array = createNonSortedArray(3);
      console.log(array);
      let arraySort = insertionSort(array);
      console.log(arraySort.join("|"));

5.归并排序 复杂度O(nlog(n)) 递归

function createNonSortedArray(size) {
        const array = [];
        for (let i = size; i > 0; i--) {
          array.push(i);
        }
        return array;
      }
      function mergeSort(array) {
        const { length } = array;
        if (length <= 1) {
          return array;
        }

        const middle = Math.floor(length / 2);
        // 使用递归完成较小数组的划分。
        let left = mergeSort(array.slice(0, middle));
        let right = mergeSort(array.slice(middle, length));
        array = merge(left, right);
        return array;
      }
      function merge(left, right) {
        let i = 0;
        let j = 0;
        let result = [];
        console.log("left :" + left + ",      right: " + right);
        while (i < left.length && j < right.length) {
          console.log(数组值left:${left[i]}, 数组值right: ${right[j]});
          result.push(left[i] < right[j] ? left[i++] : right[j++]);
          console.log(result);
        }
        console.log("i :" + i + ",      j: " + j);
        console.log(左半边: ${left.slice(i)} 和 右半边: ${right.slice(j)});
        return result.concat(i < left.length ? left.slice(i) : right.slice(j));
      }

      let array = createNonSortedArray(7);
      array = mergeSort(array);
      console.log(array);

6.快速排序 最常用的排序算法， 采用分而治之的方法
这里的主要元素最好是中间的或随机的， 如果您来自最左边，排序的数组将产生最差的排序效率。

 function createNonSortedArray(size) {
        const array = [];
        for (let i = size; i > 0; i--) {
          array.push(i);
        }
        return array;
      }
      function quickSort(array) {
        return quick(array, 0, array.length - 1);
      }
      function quick(array, left, right) {
        let index;
        console.log(当前观测阵列的长度：${array});
        if (array.length > 1) {
          index = partition(array, left, right);
          if (left < index - 1) {
            quick(array, left, index - 1);
          }
          if (index < right) {
            quick(array, index, right);
          }
        }
        return array;
      }
      function partition(array, left, right) {
        const pivot = array[Math.floor((right + left) / 2)];
        let i = left;
        let j = right;
        while (i <= j) {
          while (array[i] < pivot) {
            i++;
          }
          while (array[j] > pivot) {
            j--;
          }
          if (i <= j) {
            [array[i], array[j]] = [array[j], array[i]];
            i++;
            j--;
          }
        }
        return i;
      }

      let array = createNonSortedArray(7);
      array = quickSort([3, 5, 1, 6, 4, 7, 2]);
      console.log(array);

在互联网上找到的更简洁优雅的写作方法 作者：烂橙

const quickSort = (nums) => {
    if (nums.length < 2) {
        return nums;
    } else {
        var left = [];
        var right = [];
        var pivot = Math.floor(nums.length / 2); // Math.floor 向下取整
        var base = nums.splice(pivot, 1)[0];
        for (let i = 0; i < nums.length; i++) {
            if (nums[i] < base) {
                left.push(nums[i]);
            } else {
                right.push(nums[i]);
            }
        }
    }
    return quickSort(left).concat([base], quickSort(right));
}