tiktok年代的简方达(抖音年代轻松学简单算法)

267 阅读 94 评论 922 点赞

什么是简单算法？

简单算法是指能够在计算机算力有限的情况下，通过有限的步骤得出解决问题的方法。它是计算机科学中最基础也是最重要的一部分。在抖音，我们常常使用简单算法来优化视频播放等各种体验。下面，我们来介绍几个常见的简单算法。

一、冒泡排序

冒泡排序是一种简单的排序算法。它的基本思想是：重复比较相邻的两个元素，如果前一个比后一个大，就交换它们的位置。通过多次循环比较，将最大值“冒泡”到数组的最后一个位置。以下是一个示例的代码：

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

冒泡排序的时间复杂度为O(n2)，适合于排序小数组。如果要排序大数组，冒泡排序会很慢。

二、快速排序

快速排序是一种比冒泡排序更快的排序算法。它的基本思想是：选择一个基准数，将小于它的数放在左边，大于它的数放在右边。然后，按照相同的规则对左右两个数组分别进行快速排序。以下是一个示例的代码：

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

快速排序的时间复杂度为O(nlog?n)，比冒泡排序快得多。但是，当数组已经排好序时，快速排序的效率会变得很慢。

三、二分查找

二分查找是一种常见的查找算法。它的基本思想是：对于有序数组，通过将数组不断二分，找到目标值所在的位置。以下是一个示例的代码：

function binarySearch(arr, target) {
  let left = 0;
  let right = arr.length - 1;
  while (left <= right) {
    let mid = Math.floor((left + right) / 2);
    if (arr[mid] === target) {
      return mid;
    } else if (arr[mid] < target) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }
  return -1;
}