Home Web Front-end JS Tutorial Detailed code explanation of how JavaScript implements quick sorting

Detailed code explanation of how JavaScript implements quick sorting

Apr 10, 2018 am 10:27 AM
javascript Quick sort

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值最终的位置
}
Copy after login

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值最终的位置
}
Copy after login

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);
    }
}
Copy after login

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!

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

Undresser.AI Undress

AI-powered app for creating realistic nude photos

AI Clothes Remover

AI Clothes Remover

Online AI tool for removing clothes from photos.

Undress AI Tool

Undress AI Tool

Undress images for free

Clothoff.io

Clothoff.io

AI clothes remover

Video Face Swap

Video Face Swap

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

Hot Tools

Notepad++7.3.1

Notepad++7.3.1

Easy-to-use and free code editor

SublimeText3 Chinese version

SublimeText3 Chinese version

Chinese version, very easy to use

Zend Studio 13.0.1

Zend Studio 13.0.1

Powerful PHP integrated development environment

Dreamweaver CS6

Dreamweaver CS6

Visual web development tools

SublimeText3 Mac version

SublimeText3 Mac version

God-level code editing software (SublimeText3)

How to implement an online speech recognition system using WebSocket and JavaScript How to implement an online speech recognition system using WebSocket and JavaScript Dec 17, 2023 pm 02:54 PM

How to use WebSocket and JavaScript to implement an online speech recognition system Introduction: With the continuous development of technology, speech recognition technology has become an important part of the field of artificial intelligence. The online speech recognition system based on WebSocket and JavaScript has the characteristics of low latency, real-time and cross-platform, and has become a widely used solution. This article will introduce how to use WebSocket and JavaScript to implement an online speech recognition system.

WebSocket and JavaScript: key technologies for implementing real-time monitoring systems WebSocket and JavaScript: key technologies for implementing real-time monitoring systems Dec 17, 2023 pm 05:30 PM

WebSocket and JavaScript: Key technologies for realizing real-time monitoring systems Introduction: With the rapid development of Internet technology, real-time monitoring systems have been widely used in various fields. One of the key technologies to achieve real-time monitoring is the combination of WebSocket and JavaScript. This article will introduce the application of WebSocket and JavaScript in real-time monitoring systems, give code examples, and explain their implementation principles in detail. 1. WebSocket technology

How to use JavaScript and WebSocket to implement a real-time online ordering system How to use JavaScript and WebSocket to implement a real-time online ordering system Dec 17, 2023 pm 12:09 PM

Introduction to how to use JavaScript and WebSocket to implement a real-time online ordering system: With the popularity of the Internet and the advancement of technology, more and more restaurants have begun to provide online ordering services. In order to implement a real-time online ordering system, we can use JavaScript and WebSocket technology. WebSocket is a full-duplex communication protocol based on the TCP protocol, which can realize real-time two-way communication between the client and the server. In the real-time online ordering system, when the user selects dishes and places an order

How to implement an online reservation system using WebSocket and JavaScript How to implement an online reservation system using WebSocket and JavaScript Dec 17, 2023 am 09:39 AM

How to use WebSocket and JavaScript to implement an online reservation system. In today's digital era, more and more businesses and services need to provide online reservation functions. It is crucial to implement an efficient and real-time online reservation system. This article will introduce how to use WebSocket and JavaScript to implement an online reservation system, and provide specific code examples. 1. What is WebSocket? WebSocket is a full-duplex method on a single TCP connection.

JavaScript and WebSocket: Building an efficient real-time weather forecasting system JavaScript and WebSocket: Building an efficient real-time weather forecasting system Dec 17, 2023 pm 05:13 PM

JavaScript and WebSocket: Building an efficient real-time weather forecast system Introduction: Today, the accuracy of weather forecasts is of great significance to daily life and decision-making. As technology develops, we can provide more accurate and reliable weather forecasts by obtaining weather data in real time. In this article, we will learn how to use JavaScript and WebSocket technology to build an efficient real-time weather forecast system. This article will demonstrate the implementation process through specific code examples. We

Simple JavaScript Tutorial: How to Get HTTP Status Code Simple JavaScript Tutorial: How to Get HTTP Status Code Jan 05, 2024 pm 06:08 PM

JavaScript tutorial: How to get HTTP status code, specific code examples are required. Preface: In web development, data interaction with the server is often involved. When communicating with the server, we often need to obtain the returned HTTP status code to determine whether the operation is successful, and perform corresponding processing based on different status codes. This article will teach you how to use JavaScript to obtain HTTP status codes and provide some practical code examples. Using XMLHttpRequest

How to use insertBefore in javascript How to use insertBefore in javascript Nov 24, 2023 am 11:56 AM

Usage: In JavaScript, the insertBefore() method is used to insert a new node in the DOM tree. This method requires two parameters: the new node to be inserted and the reference node (that is, the node where the new node will be inserted).

JavaScript and WebSocket: Building an efficient real-time image processing system JavaScript and WebSocket: Building an efficient real-time image processing system Dec 17, 2023 am 08:41 AM

JavaScript is a programming language widely used in web development, while WebSocket is a network protocol used for real-time communication. Combining the powerful functions of the two, we can create an efficient real-time image processing system. This article will introduce how to implement this system using JavaScript and WebSocket, and provide specific code examples. First, we need to clarify the requirements and goals of the real-time image processing system. Suppose we have a camera device that can collect real-time image data

See all articles