Detailed code explanation of how JavaScript implements quick sorting
The content of this article is to share with you how to implement quick sorting in JavaScript. It has a certain reference value. Friends in need can refer to it
I accidentally saw Teacher Ruan Yifeng’s blog A quick sorting algorithm from a few years ago in China created two additional arrays each time it was looped. If the amount of data is large, it will take up a lot of extra memory. However, arrays are reference types and can be modified. The original array itself can be directly manipulated to save memory.
The key to the quick sort method is to select a value and divide the entire array into two parts, the small one on the left and the large one on the right. Here is how this function is written:
//该函数的主要目的是交换数组中两个元素的位置 function swap(arr, index1, index2) { let data = arr[index1]; arr[index1] = arr[index2]; arr[index2] = arr[index1]; //数组是引用类型,允许修改原数组。 } //选取随机值,将数组分为两部分 function partition(arr, start, end) { let keyIndex = end, key = arr[keyIndex]; //将随机值(以后称key值)定为最后一个数,也可以真的随机选取,见下一行 // let keyIndex = Math.floor(Math.random() * (end - start)) + start; let i = start, j = end, order = true; //当order为true时正向筛选,当order为false时逆向筛选 //先从正向开始,因为我们把key值保存到了数组的结尾处。 while(i != j) { if(order) { //正向筛选 if (arr[i]>key) { swap(arr, i, j); //将大于key的数字和key进行交换 order = false; } else { i++; } } else { //逆向筛选 if(arr[j]<key) { swap(arr, i, j); //将小于key的数字和key进行交换 order = true; } else { j--; } } } return i;//返回key值最终的位置 }
Observe the grouping It is not difficult to find in the algorithm partition. In fact, there is always a key value stored in the i and j positions, and then it is exchanged with a value larger or smaller than it. Then we can also write it as a one-way grouping method:
function partition2(arr, start, end) { let keyIndex = end, key = arr[end]; let i = start -1, j = start; for (;j<end;j++) { if (arr[j]< key) { // i位置的值永远比key值小 i++; if (i != j) { swap(arr, i, j); } } } ++i; swap(arr, i, end); return i; //返回key值最终的位置 }
Next, call the grouping function recursively to sort the entire array:
function quickSort(arr, start, end) { if (start == end) return; let index = partition(arr, start, end); if (index > start){ quickSort(arr, start, index-1); } if (index<end) { quickSort(arr, index+1, end); } }
Related recommendations:
Summary of implementation and optimization of two methods of quick sort
Quick sort principle and java implementation
C++ implementation of quick sort
The above is the detailed content of Detailed code explanation of how JavaScript implements quick sorting. For more information, please follow other related articles on the PHP Chinese website!

JavaScript is widely used in websites, mobile applications, desktop applications and server-side programming. 1) In website development, JavaScript operates DOM together with HTML and CSS to achieve dynamic effects and supports frameworks such as jQuery and React. 2) Through ReactNative and Ionic, JavaScript is used to develop cross-platform mobile applications. 3) The Electron framework enables JavaScript to build desktop applications. 4) Node.js allows JavaScript to run on the server side and supports high concurrent requests.

Python is more suitable for data science and automation, while JavaScript is more suitable for front-end and full-stack development. 1. Python performs well in data science and machine learning, using libraries such as NumPy and Pandas for data processing and modeling. 2. Python is concise and efficient in automation and scripting. 3. JavaScript is indispensable in front-end development and is used to build dynamic web pages and single-page applications. 4. JavaScript plays a role in back-end development through Node.js and supports full-stack development.

C and C play a vital role in the JavaScript engine, mainly used to implement interpreters and JIT compilers. 1) C is used to parse JavaScript source code and generate an abstract syntax tree. 2) C is responsible for generating and executing bytecode. 3) C implements the JIT compiler, optimizes and compiles hot-spot code at runtime, and significantly improves the execution efficiency of JavaScript.

JavaScript's application in the real world includes front-end and back-end development. 1) Display front-end applications by building a TODO list application, involving DOM operations and event processing. 2) Build RESTfulAPI through Node.js and Express to demonstrate back-end applications.

The main uses of JavaScript in web development include client interaction, form verification and asynchronous communication. 1) Dynamic content update and user interaction through DOM operations; 2) Client verification is carried out before the user submits data to improve the user experience; 3) Refreshless communication with the server is achieved through AJAX technology.

Understanding how JavaScript engine works internally is important to developers because it helps write more efficient code and understand performance bottlenecks and optimization strategies. 1) The engine's workflow includes three stages: parsing, compiling and execution; 2) During the execution process, the engine will perform dynamic optimization, such as inline cache and hidden classes; 3) Best practices include avoiding global variables, optimizing loops, using const and lets, and avoiding excessive use of closures.

Python is more suitable for beginners, with a smooth learning curve and concise syntax; JavaScript is suitable for front-end development, with a steep learning curve and flexible syntax. 1. Python syntax is intuitive and suitable for data science and back-end development. 2. JavaScript is flexible and widely used in front-end and server-side programming.

Python and JavaScript have their own advantages and disadvantages in terms of community, libraries and resources. 1) The Python community is friendly and suitable for beginners, but the front-end development resources are not as rich as JavaScript. 2) Python is powerful in data science and machine learning libraries, while JavaScript is better in front-end development libraries and frameworks. 3) Both have rich learning resources, but Python is suitable for starting with official documents, while JavaScript is better with MDNWebDocs. The choice should be based on project needs and personal interests.


Hot AI Tools

Undresser.AI Undress
AI-powered app for creating realistic nude photos

AI Clothes Remover
Online AI tool for removing clothes from photos.

Undress AI Tool
Undress images for free

Clothoff.io
AI clothes remover

Video Face Swap
Swap faces in any video effortlessly with our completely free AI face swap tool!

Hot Article

Hot Tools

SublimeText3 English version
Recommended: Win version, supports code prompts!

mPDF
mPDF is a PHP library that can generate PDF files from UTF-8 encoded HTML. The original author, Ian Back, wrote mPDF to output PDF files "on the fly" from his website and handle different languages. It is slower than original scripts like HTML2FPDF and produces larger files when using Unicode fonts, but supports CSS styles etc. and has a lot of enhancements. Supports almost all languages, including RTL (Arabic and Hebrew) and CJK (Chinese, Japanese and Korean). Supports nested block-level elements (such as P, DIV),

SublimeText3 Mac version
God-level code editing software (SublimeText3)

MinGW - Minimalist GNU for Windows
This project is in the process of being migrated to osdn.net/projects/mingw, you can continue to follow us there. MinGW: A native Windows port of the GNU Compiler Collection (GCC), freely distributable import libraries and header files for building native Windows applications; includes extensions to the MSVC runtime to support C99 functionality. All MinGW software can run on 64-bit Windows platforms.

Atom editor mac version download
The most popular open source editor