Algorithmic ideas for implementing quick sort in JavaScript-JS Tutorial-php.cn

Home

Web Front-end

JS Tutorial

Algorithmic ideas for implementing quick sort in JavaScript

不言

Jul 11, 2018 am 09:16 AM

javascript implementation

This article mainly introduces the algorithmic ideas about JavaScript to implement quick sorting. It has certain reference value. Now I share it with you. Friends in need can refer to it.

At present, the most common sorting algorithm is probably There are seven or eight types, among which "Quicksort" is the most widely used and faster. It was proposed by Turing Award winner C. A. R. Hoare in 1960.

The idea of "Quick Sort" is very simple. The entire sorting process only requires three steps:

(1) In the data set, select an element as the "pivot" (pivot).

　(2) All elements smaller than "baseline" are moved to the left of "baseline"; all elements larger than "baseline" are moved to the right of "baseline".

　(3) For the two subsets on the left and right of the "baseline", repeat the first and second steps until all subsets have only one element left.

For example, there is now a data set {85 , 24, 63, 45, 17, 31, 96, 50}, how to sort them?

The first step is to select the middle element 45 as the "baseline". (The base value can be arbitrary Choose, but choosing the middle value is easier to understand.)

The second step is to compare each element with the "baseline" in order to form two subsets, one "less than 45", and the other "greater than or equal to 45".

The third step is to repeat the first and second steps for the two subsets until there is only one element left in all subsets. So far.

Follow the previous steps and define a quickSort function:

var quickSort = function(arr) { //参数是一个数组
　　if (arr.length <= 1) { return arr; } //检查数组的元素个数，如果小于等于1，就返回。
　　var pivotIndex = Math.floor(arr.length / 2); //选择"基准"（pivot），并将其与原数组分离，再定义两个空数组，用来存放一左一右的两个子集。
　　var pivot = arr.splice(pivotIndex, 1)[0];
　　var left = [];
　　var right = [];
　　for (var i = 0; i < arr.length; i++){ //开始遍历数组，小于"基准"的元素放入左边的子集，大于基准的元素放入右边的子集。
　　　　if (arr[i] < pivot) {
　　　　　　left.push(arr[i]);
　　　　} else {
　　　　　　right.push(arr[i]);
　　　　}
　　}
　　return quickSort(left).concat([pivot], quickSort(right));
};

Copy after login

Realize the above animation:

Algorithm idea:

Select an element from the sequence, called the "pivot";
Reorder the array so that all elements smaller than the base value are placed in front of the base, and all elements larger than the base value are placed behind the base (the same number can go to either side). After the partition exits, the base is in the array The middle position. This is called a partition operation;
recursively sorts the subarray of elements smaller than the base value and the subarray of elements greater than the base value;

Implementation code:

function quickSort(arr, left, right) { 
　　var len = arr.length,
　　partitionIndex,
　　left = typeof left != &#39;number&#39; ? 0 : left,
　　right = typeof right != &#39;number&#39; ? len - 1 : right;
  
  
　　if (left < right) {
　　partitionIndex = partition(arr, left, right);
　　quickSort(arr, left, partitionIndex-1);
　　quickSort(arr, partitionIndex+1, right);
　　}
　　return arr;
}
function partition(arr, left ,right) { // 分区操作
　　var pivot = left,                // 设定基准值（pivot）
　　　　index = pivot + 1;
　　for (var i = index; i <= right; i++) {
　　　　if (arr[i] < arr[pivot]) {
　　　　　　swap(arr, i, index);
　　　　　　index++;
　　　　}
　　}
　　swap(arr, pivot, index - 1);
　　 return index-1;
}
  
function swap(arr, i, j) {
　　var temp = arr[i];
　　arr[i] = arr[j];
　　arr[j] = temp;
}
function partition2(arr, low, high) {
　　let pivot = arr[low];
　　while (low < high) {
　　　　while (low < high && arr[high] > pivot) {
　　　　--high;
　　　　}
　　　　arr[low] = arr[high];
　　　　while (low < high && arr[low] <= pivot) {
　　　　++low;
　　　　}
　　　　arr[high] = arr[low];
　　}
　　arr[low] = pivot;
　　return low;
}
  
function quickSort2(arr, low, high) {
　　if (low < high) {
　　let pivot = partition2(arr, low, high);
　　quickSort2(arr, low, pivot - 1);
　　quickSort2(arr, pivot + 1, high);
　　}
　　return arr;
}

Copy after login

The above is the entire content of this article. I hope it will be helpful to everyone’s study. For more related content, please pay attention to the PHP Chinese website!

Related recommendations:

How to randomly sort js arrays

js moves any element to a specified position

The above is the detailed content of Algorithmic ideas for implementing quick sort in JavaScript. For more information, please follow other related articles on the PHP Chinese website!

Statement of this Website

The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn

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

How to fix KB5055518 fails to install in Windows 10?

1 months ago By DDD

How to fix KB5055523 fails to install in Windows 11?

1 months ago By DDD

Roblox: Grow A Garden - Complete Mutation Guide

3 weeks ago By DDD

Roblox: Bubble Gum Simulator Infinity - How To Get And Use Royal Keys

3 weeks ago By 尊渡假赌尊渡假赌尊渡假赌

How to fix KB5055612 fails to install in Windows 10?

3 weeks ago By DDD

Hot Tools

Notepad++7.3.1

Easy-to-use and free code editor

SublimeText3 Chinese version

Chinese version, very easy to use

Zend Studio 13.0.1

Powerful PHP integrated development environment

Dreamweaver CS6

Visual web development tools

SublimeText3 Mac version

God-level code editing software (SublimeText3)

Hot Topics

Java Tutorial

1664

CakePHP Tutorial

1423

Laravel Tutorial

1317

PHP Tutorial

1268

C# Tutorial

1246

Related knowledge

The Evolution of JavaScript: Current Trends and Future Prospects Apr 10, 2025 am 09:33 AM

The latest trends in JavaScript include the rise of TypeScript, the popularity of modern frameworks and libraries, and the application of WebAssembly. Future prospects cover more powerful type systems, the development of server-side JavaScript, the expansion of artificial intelligence and machine learning, and the potential of IoT and edge computing.

JavaScript Engines: Comparing Implementations Apr 13, 2025 am 12:05 AM

Different JavaScript engines have different effects when parsing and executing JavaScript code, because the implementation principles and optimization strategies of each engine differ. 1. Lexical analysis: convert source code into lexical unit. 2. Grammar analysis: Generate an abstract syntax tree. 3. Optimization and compilation: Generate machine code through the JIT compiler. 4. Execute: Run the machine code. V8 engine optimizes through instant compilation and hidden class, SpiderMonkey uses a type inference system, resulting in different performance performance on the same code.

Python vs. JavaScript: The Learning Curve and Ease of Use Apr 16, 2025 am 12:12 AM

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.

JavaScript: Exploring the Versatility of a Web Language Apr 11, 2025 am 12:01 AM

JavaScript is the core language of modern web development and is widely used for its diversity and flexibility. 1) Front-end development: build dynamic web pages and single-page applications through DOM operations and modern frameworks (such as React, Vue.js, Angular). 2) Server-side development: Node.js uses a non-blocking I/O model to handle high concurrency and real-time applications. 3) Mobile and desktop application development: cross-platform development is realized through ReactNative and Electron to improve development efficiency.

How to Build a Multi-Tenant SaaS Application with Next.js (Frontend Integration) Apr 11, 2025 am 08:22 AM

This article demonstrates frontend integration with a backend secured by Permit, building a functional EdTech SaaS application using Next.js. The frontend fetches user permissions to control UI visibility and ensures API requests adhere to role-base

Building a Multi-Tenant SaaS Application with Next.js (Backend Integration) Apr 11, 2025 am 08:23 AM

I built a functional multi-tenant SaaS application (an EdTech app) with your everyday tech tool and you can do the same. First, what’s a multi-tenant SaaS application? Multi-tenant SaaS applications let you serve multiple customers from a sing

From C/C to JavaScript: How It All Works Apr 14, 2025 am 12:05 AM

The shift from C/C to JavaScript requires adapting to dynamic typing, garbage collection and asynchronous programming. 1) C/C is a statically typed language that requires manual memory management, while JavaScript is dynamically typed and garbage collection is automatically processed. 2) C/C needs to be compiled into machine code, while JavaScript is an interpreted language. 3) JavaScript introduces concepts such as closures, prototype chains and Promise, which enhances flexibility and asynchronous programming capabilities.

JavaScript and the Web: Core Functionality and Use Cases Apr 18, 2025 am 12:19 AM

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.

See all articles