JS에서 정렬 및 검색 알고리즘을 구현하는 방법-JS 튜토리얼-php.cn

이 기사의 내용은 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)，因此也称为非线性时间比较类排序
非比较类排序：不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以线性时间运行，因此也称为线性时间非比较类排序

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

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

2.1 冒泡排序

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

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

动图：

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

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

代码：

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

로그인 후 복사

2.2 选择排序

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

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

动图：

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

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

代码：

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 插入排序

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

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

动图：

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

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

代码：

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><div class="code" style="position:relative; padding:0px; margin:0px;"><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;
}

로그인 후 복사

🎜2.1 버블 정렬🎜

🎜2.3 삽입 정렬🎜

🎜2.4 병합 정렬🎜

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

2.5 快速排序

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

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

四、算法复杂度

4.1 理解大O表示法

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

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

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

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

4.2 时间复杂度比较

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

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