JS에서 정렬 및 검색 알고리즘을 구현하는 방법

이 기사의 내용은 JS를 사용하여 정렬 및 검색 알고리즘을 구현하는 방법을 소개하는 것입니다. 이는 특정 참조 가치가 있으므로 도움이 될 수 있습니다.

1. 준비

본론에 들어가기 전에 몇 가지 기본 함수를 준비하세요

(1) 배열의 두 요소를 교환합니다

function swap(arr, sourceIndex, targetIndex) {
  let temp = arr[sourceIndex];
  arr[sourceIndex] = arr[targetIndex];
  arr[targetIndex] = temp;
}

(2) 0~N을 빠르게 생성합니다. code>의 배열 0~N的数组

function createArr(length) {
  return Array.from({length}, (_, i) => i);
}

（3）洗牌函数

洗牌函数可快速打乱数组，常见的用法如切换音乐播放顺序

function shuffle(arr) {
  for (let i = 0; i <h2><strong>二、排序</strong></h2><p>常见排序算法可以分为两大类：</p>

• 比较类排序：通过比较来决定元素间的相对次序，由于其时间复杂度不能突破O(nlogn)，因此也称为非线性时间比较类排序
• 非比较类排序：不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以线性时间运行，因此也称为线性时间非比较类排序

在本篇文章中，仅对比较类排序的几种排序方式进行学习介绍

2.1 冒泡排序

冒泡排序是所有排序算法中最简单的，通常也是我们学习排序的入门方法。但是，从运行时间的角度来看，冒泡排序是最差的一种排序方式。

核心：比较任何两个相邻的项，如果第一个比第二个大，则交换它们。元素项向上移动至正确的顺序，就好像气泡升至表面一样，冒泡排序因而得名

动图：

注意：第一层遍历找出剩余元素的最大值，至指定位置【依次冒泡出最大值】

代码：

function bubbleSort(arr) {
  const len = arr.length;
  for (let i = 0; i  arr[j + 1]) { // 比较相邻元素
        swap(arr, j, j + 1);
      }
    }
  }
  return arr;
}

2.2 选择排序

选择排序是一种原址比较排序算法。

核心：首先在未排序序列中找到最小元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕

动图：

注意：第一层遍历找出剩余元素最小值的索引，然后交换当前位置和最小值索引值【依次找到最小值】

代码：

function selectionSort(arr) {
  const len = arr.length;
  let minIndex;
  for (let i = 0; i  arr[j]) {
        minIndex = j; // 寻找最小值对应的索引
      }
    }
    if (minIndex === i) continue;
    swap(arr, minIndex, i);
  }
  return arr;
}

2.3 插入排序

插入排序的比较顺序不同于冒泡排序和选择排序，插入排序的比较顺序是当前项向前比较。

核心：通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入

动图：

注意：从第二项开始，依次向前比较，保证当前项以前的序列是顺序排列

代码：

function insertionSort(arr) {
  const len = arr.length;
  let current, pointer;
  for (let i = 1; i = 0 && current <h3><strong>2.4 归并排序</strong></h3><p>归并排序和快速排序相较于上面三种排序算法在实际中更具有可行性（在第四小节我们会通过实践复杂度来比较这几种排序算法）</p><blockquote>
<code>JavaScript</code>的<code>Array</code>类定义了一个<code>sort</code>函数(<code>Array.prototype.sort</code>)用以排序<code>JavaScript</code>数组。<code>ECMAScript</code>没有定义用哪个排序算法，所以浏览器厂商可以自行去实现算法。例如，<code>Mozilla Firefox</code>使用<strong>归并排序</strong>作为<code>Array.prototype.sort</code>的实现，而<code>Chrome</code>使用了一个<strong>快速排序</strong>的变体</blockquote><p><strong>归并排序是一种<code>分治算法</code>。其思想是将原始数组切分成较小的数组，直到每个小数组只有一 个位置，接着将小数组归并成较大的数组，直到最后只有一个排序完毕的大数组。因此需要用到<code>递归</code></strong></p><pre class="brush:php;toolbar:false">function mergeSort(arr) {
  const len = arr.length;

  if (len  right[0]) {
      ret.push(right.shift());
    } else {
      ret.push(left.shift());
    }
  }

  while (left.length) {
    ret.push(left.shift());
  }
  while (right.length) {
    ret.push(right.shift());
  }

  return ret;
}

(3) 셔플링 기능

셔플링 기능은 배열을 빠르게 뒤섞을 수 있습니다. 일반적인 용도로는 음악 재생 순서 전환이 있습니다.

function quickSort(arr, left = 0, right = arr.length - 1) {
  // left和right默认为数组首尾
  if (left <strong></strong> 2. 정렬 <p style="text-align: center;"><img src="https://img.php.cn/upload/image/174/628/728/1553738670821848.gif" title="1553738670821848.gif" alt="JS에서 정렬 및 검색 알고리즘을 구현하는 방법">일반적인 정렬 알고리즘을 사용할 수 있습니다. </p>

• 🎜비교 정렬🎜: 비교를 통해 요소 간의 상대적 순서를 결정합니다. 시간 복잡도는 O(nlogn)을 초과할 수 없으므로 비선형 시간 비교 정렬이라고도 합니다
• 🎜비비교 정렬🎜: 비교를 통해 요소 간의 상대적 순서를 결정하지 않으며 비교 정렬을 기반으로 시간 하한을 돌파하고 선형으로 실행될 수 있습니다. 시간이므로 선형 시간으로 비비교 클래스 정렬이라고도 합니다.

🎜🎜🎜이 글에서는 비교 정렬의 여러 정렬 방법만 배우고 소개합니다🎜

🎜2.1 버블 정렬🎜

🎜 버블 정렬은 모든 정렬 알고리즘 중 가장 간단하며 일반적으로 정렬을 배우는 입문 방법입니다. 그러나 실행 시간 관점에서 볼 때 버블 정렬은 최악의 정렬 방법입니다. 🎜🎜🎜핵심: 인접한 두 항목을 비교하고 첫 번째 항목이 두 번째 항목보다 크면 서로 바꿉니다 🎜. 거품이 표면으로 떠오르는 것처럼 요소 항목이 올바른 순서로 위로 이동하므로 거품 정렬이라는 이름이 붙었습니다. 🎜🎜🎜Gif: 🎜🎜🎜🎜🎜🎜참고: 첫 번째 수준에서는 나머지 요소의 최대값을 찾기 위해 순회하여 지정된 위치까지 이동합니다. [리스크는 차례로 최대값을 골라낸다]🎜🎜🎜🎜코드: 🎜🎜

function findItem(item, arr) {
  for (let i = 0; i <h3>🎜2.2 선택 정렬🎜</h3>🎜선택 정렬은 내부 비교 정렬 알고리즘입니다. 🎜🎜🎜핵심: 먼저 정렬되지 않은 시퀀스에서 가장 작은 요소를 찾아서 정렬된 시퀀스의 시작 부분에 저장한 다음, 정렬되지 않은 나머지 요소에서 가장 작은 요소를 계속 찾아 정렬된 시퀀스의 끝에 넣습니다. 등등 모든 요소가 정렬될 때까지🎜🎜🎜🎜Gif: 🎜🎜🎜<img src="https://img.php.cn/upload/image/693/571/416/155373864796177JS%EC%97%90%EC%84%9C%20%EC%A0%95%EB%A0%AC%20%EB%B0%8F%20%EA%B2%80%EC%83%89%20%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98%EC%9D%84%20%EA%B5%AC%ED%98%84%ED%95%98%EB%8A%94%20%EB%B0%A9%EB%B2%95" title=" 155373864796177JS에서 정렬 및 검색 알고리즘을 구현하는 방법" alt="JS에서 정렬 및 검색 알고리즘을 구현하는 방법">🎜🎜🎜참고: 순회 첫 번째 수준에서는 나머지 요소의 최소값에 대한 인덱스를 찾은 다음 현재 위치와 최소 인덱스 값을 교환합니다. 값순서]🎜🎜 🎜🎜코드: 🎜🎜<pre class="brush:php;toolbar:false">function binarySearch(item, arr) {
  arr = quickSort(arr); // 排序

  let low = 0;
  let high = arr.length - 1;
  let mid;

  while (low  item) {
      high = mid - 1;
    } else {
      return mid;
    }
  }
  return -1;
}

🎜2.3 삽입 정렬🎜

🎜삽입 정렬의 비교 순서는 버블 정렬 및 선택 정렬과 다릅니다. 삽입 정렬의 비교 순서는 순방향 비교입니다. 현재 항목의 🎜🎜🎜Core: 정렬된 시퀀스를 구성하여 정렬되지 않은 데이터의 경우 정렬된 시퀀스에서 뒤에서 앞으로 스캔하고 해당 위치를 찾아 삽입합니다. 🎜🎜🎜🎜Gif: 🎜🎜🎜🎜🎜🎜참고: 두 번째 항목부터 먼저 비교를 진행하세요. 현재 항목의 이전 순서가 올바른지 확인하기 위해🎜🎜🎜🎜코드: 🎜🎜

function increment(num){
    return ++num;
}

🎜2.4 병합 정렬🎜

🎜위의 세 가지 정렬 알고리즘에 비해 병합 정렬과 빠른 정렬이 더 많습니다. 실제로 실용적입니다. 더 실현 가능합니다(네 번째 섹션에서 실제 복잡성을 통해 이러한 정렬 알고리즘을 비교할 것입니다) 🎜

JavaScript의 Array 클래스는 sort 함수(Array.prototype.sort)는 JavaScript 배열을 정렬하는 데 사용됩니다. ECMAScript는 사용할 정렬 알고리즘을 정의하지 않으므로 브라우저 제조업체가 알고리즘을 직접 구현할 수 있습니다. 예를 들어 Mozilla Firefox는 Array.prototype.sort의 구현으로 🎜Merge Sort🎜를 사용하는 반면, Chrome은 🎜QuickSort🎜의 변형을 사용합니다.

🎜🎜병합 정렬은 분할 정복 알고리즘입니다. 아이디어는 각 작은 배열이 하나의 위치만 가질 때까지 원본 배열을 더 작은 배열로 분할한 다음 정렬된 큰 배열이 하나만 있을 때까지 작은 배열을 더 큰 배열로 병합하는 것입니다. 따라서 recursion🎜🎜🎜🎜Core: 병합 정렬, 왼쪽 및 오른쪽 배열로 분할, 별도로 정렬한 다음 병합해야 합니다.🎜🎜🎜🎜Gif: 🎜🎜🎜🎜🎜

注意：递归中最小的左右数组比较为单个元素的数组，因此在较上层多个元素对比时，左右两个数组一定是顺序的

代码：

function mergeSort(arr) {
  const len = arr.length;

  if (len  right[0]) {
      ret.push(right.shift());
    } else {
      ret.push(left.shift());
    }
  }

  while (left.length) {
    ret.push(left.shift());
  }
  while (right.length) {
    ret.push(right.shift());
  }

  return ret;
}

2.5 快速排序

快速排序也许是最常用的排序算法了。它的复杂度为O(nlogn)，且它的性能通常比其他的复 杂度为O(nlogn)的排序算法要好。和归并排序一样，快速排序也使用分治的方法，将原始数组分为较小的数组

核心：分治算法，以参考值为界限，将比它小的和大的值拆开

动图：

注意：每一次遍历筛选出比基准点小的值

代码：

function quickSort(arr, left = 0, right = arr.length - 1) {
  // left和right默认为数组首尾
  if (left <h2><strong>三、搜索算法</strong></h2><h3><strong>3.1 顺序搜索</strong></h3><p>顺序或线性搜索是最基本的搜索算法。它的机制是，将每一个数据结构中的元素和我们要找的元素做比较。<strong>顺序搜索是最低效的一种搜索算法。</strong></p><pre class="brush:php;toolbar:false">function findItem(item, arr) {
  for (let i = 0; i <h3><strong>3.2 二分搜索</strong></h3><p>二分搜索要求被搜索的数据结构已排序。以下是该算法遵循的步骤：</p><ol>
<li>选择数组的中间值</li>
<li>如果选中值是待搜索值，那么算法执行完毕</li>
<li>如果待搜索值比选中值要小，则返回步骤1在选中值左边的子数组中寻找</li>
<li>如果待搜索值比选中值要大，则返回步骤1在选中值右边的子数组中寻找</li>
</ol><pre class="brush:php;toolbar:false">function binarySearch(item, arr) {
  arr = quickSort(arr); // 排序

  let low = 0;
  let high = arr.length - 1;
  let mid;

  while (low  item) {
      high = mid - 1;
    } else {
      return mid;
    }
  }
  return -1;
}

四、算法复杂度

4.1 理解大O表示法

大O表示法用于描述算法的性能和复杂程度。分析算法时，时常遇到一下几类函数

（1）O(1)

function increment(num){
    return ++num;
}

执行时间和参数无关。因此说，上述函数的复杂度是O(1)(常数)

（2）O(n)

以顺序搜索函数为例，查找元素需要遍历整个数组，直到找到该元素停止。函数执行的总开销取决于数组元素的个数(数组大小)，而且也和搜索的值有关。但是函数复杂度取决于最坏的情况：如果数组大小是10，开销就是10；如果数组大小是1000，开销就是1000。这种函数的时间复杂度是O(n)，n是(输入)数组的大小

（3）O(n2)

以冒泡排序为例，在未优化的情况下，每次排序均需进行n*n次执行。时间复杂度为O(n2)

时间复杂度O(n)的代码只有一层循环，而O(n2)的代码有双层嵌套循环。如 果算法有三层遍历数组的嵌套循环，它的时间复杂度很可能就是O(n3)

4.2 时间复杂度比较

（1）常用数据结构时间复杂度

（2）排序算法时间复杂度

相关视频教程推荐：《JavaScript教程》

以上就是本篇文章的全部内容，希望能对大家的学习有所帮助。更多精彩内容大家可以关注php中文网相关教程栏目！！！

위 내용은 JS에서 정렬 및 검색 알고리즘을 구현하는 방법의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!