Shulou(Shulou.com)06/02 Report--

This article mainly introduces "how to use JS sorting and search algorithm". In daily operation, I believe many people have doubts about how to use JS sorting and search algorithm. The editor consulted all kinds of materials and sorted out simple and easy-to-use operation methods. I hope it will be helpful to answer the doubts about "how to use JS sorting and search algorithm". Next, please follow the editor to study!

I. preparation

Before you get to the point, prepare a few basic functions

(1) swap two elements of the array

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

(2) you can click to quickly generate an array of zero N to view more generation methods.

Function createArr (length) {return Array.from ({length}, (_, I) = > I);}

(3) shuffle function

Shuffle function can quickly disrupt arrays, common uses such as switching music playback order

Function shuffle (arr) {for (let I = 0; I)

< arr.length; i += 1) { const rand = Math.floor(Math.random() * (i + 1)); if (rand !== i) { swap(arr, i, rand); } } return arr; } 二、排序 常见排序算法可以分为两大类： 比较类排序：通过比较来决定元素间的相对次序，由于其时间复杂度不能突破O(nlogn)，因此也称为非线性时间比较类排序 非比较类排序：不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以线性时间运行，因此也称为线性时间非比较类排序 在本篇博客中，仅对比较类排序的几种排序方式进行学习介绍 2.1 冒泡排序 冒泡排序是所有排序算法中最简单的，通常也是我们学习排序的入门方法。但是，从运行时间的角度来看，冒泡排序是最差的一种排序方式。 核心：比较任何两个相邻的项，如果***个比第二个大，则交换它们。元素项向上移动至正确的顺序，就好像气泡升至表面一样，冒泡排序因而得名 注意：***层遍历找出剩余元素的***值，至指定位置【依次冒泡出***值】 代码： function bubbleSort(arr) { const len = arr.length; for (let i = 0; i < len; i += 1) { for (let j = 0; j < len - 1 - i; j += 1) { if (arr[j] >

Arr [j + 1]) {/ / compare adjacent elements swap (arr, j, j + 1);} return arr;}

2.2 Select sort

Selection sorting is an in-situ comparison sorting algorithm.

Core: first find the smallest element in the unsorted sequence and store it at the beginning of the sorted sequence, then continue to find the smallest element from the remaining unsorted elements, and then put it at the end of the sorted sequence. And so on until all the elements have been sorted

Note: * layer traverses to find the index of the minimum value of the remaining elements, and then exchanges the current location and the minimum index value [finds the minimum value in turn]

Code:

Function selectionSort (arr) {const len = arr.length; let minIndex; for (let I = 0; I

< len - 1; i += 1) { minIndex = i; for (let j = i + 1; j < len; j += 1) { if (arr[minIndex] >

Arr [j]) {minIndex = j; / / find the index corresponding to the minimum}} if (minIndex = I) continue; swap (arr, minIndex, I);} return arr;}

2.3 insert sort

The comparison order of the insertion sort is different from the bubble sort and the selection sort, and the comparison order of the insertion sort is the forward comparison of the current item.

Core: by building an ordered sequence, for unsorted data, scan from back to front in the sorted sequence, find the corresponding position and insert it.

Note: starting from the second item, compare forward in turn to make sure that the previous sequence of the current item is in order.

Code:

Function insertionSort (arr) {const len = arr.length; let current, pointer; for (let I = 1; I

< len; i += 1) { current = arr[i]; pointer = i; while(pointer >

= 0 & & current

< arr[pointer - 1]) { // 每次向前比较 arr[pointer] = arr[pointer - 1]; // 前一项大于指针项，则向前移动一项 pointer -= 1; } arr[pointer] = current; // 指针项还原成当前项 } return arr; } 2.4 归并排序 归并排序和快速排序相较于上面三种排序算法在实际中更具有可行性（在第四小节我们会通过实践复杂度来比较这几种排序算法） JavaScript的Array类定义了一个sort函数(Array.prototype.sort)用以排序JavaScript数组。ECMAScript没有定义用哪个排序算法，所以浏览器厂商可以自行去实现算法。例如，Mozilla Firefox使用归并排序作为Array.prototype.sort的实现，而Chrome使用了一个快速排序的变体 归并排序是一种分治算法。其思想是将原始数组切分成较小的数组，直到每个小数组只有一 个位置，接着将小数组归并成较大的数组，直到***只有一个排序完毕的大数组。因此需要用到递归 核心：归并排序，拆分成左右两块数组，分别排序后合并

Note: the smallest left and right array in recursion is compared to an array of a single element, so when comparing multiple elements in the upper layer, the left and right arrays must be sequential.

Code:

Function mergeSort (arr) {const len = arr.length; if (len)

< 2) return arr; // 递归的终止条件 const middle = Math.floor(len / 2); // 拆分左右数组 const left = arr.slice(0, middle); const right = arr.slice(middle); return merge(mergeSort(left), mergeSort(right)); } function merge(left, right) { // 将左右两侧比较后进行合并 const ret = []; while (left.length && right.length) { if (left[0] >

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 Quick sort

Quick sort is perhaps the most commonly used sorting algorithm. Its complexity is O (nlogn), and its performance is usually better than other sorting algorithms with complexity O (nlogn). Like merge sorting, quick sorting uses the divide-and-conquer method to divide the original array into smaller arrays

Core: divide-and-conquer algorithm, taking the reference value as the boundary, separating the smaller and larger values.

Note: each traversal filters out values that are smaller than the datum point

Code:

Function quickSort (arr, left = 0, right = arr.length-1) {/ / left and right defaults to if (left < right) {let partitionpartitionIndex = partition (arr, left, right); quickSort (arr, left, partitionIndex-1); quickSort (arr, partitionIndex + 1, right);} return arr;} function partition (arr, left, right) {let pivot = left; let index = left + 1 / / for after the partition point (let I = index; I) if the comparison condition is met.

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.