search
HomeWeb Front-endJS TutorialAlgorithmic ideas for implementing quick sort in JavaScript
Algorithmic ideas for implementing quick sort in JavaScriptJul 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));
};

Realize the above animation:

Algorithm idea:

  1. Select an element from the sequence, called the "pivot";

  2. 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;

  3. 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;
}

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
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
Replace String Characters in JavaScriptReplace String Characters in JavaScriptMar 11, 2025 am 12:07 AM

Detailed explanation of JavaScript string replacement method and FAQ This article will explore two ways to replace string characters in JavaScript: internal JavaScript code and internal HTML for web pages. Replace string inside JavaScript code The most direct way is to use the replace() method: str = str.replace("find","replace"); This method replaces only the first match. To replace all matches, use a regular expression and add the global flag g: str = str.replace(/fi

8 Stunning jQuery Page Layout Plugins8 Stunning jQuery Page Layout PluginsMar 06, 2025 am 12:48 AM

Leverage jQuery for Effortless Web Page Layouts: 8 Essential Plugins jQuery simplifies web page layout significantly. This article highlights eight powerful jQuery plugins that streamline the process, particularly useful for manual website creation

Build Your Own AJAX Web ApplicationsBuild Your Own AJAX Web ApplicationsMar 09, 2025 am 12:11 AM

So here you are, ready to learn all about this thing called AJAX. But, what exactly is it? The term AJAX refers to a loose grouping of technologies that are used to create dynamic, interactive web content. The term AJAX, originally coined by Jesse J

10 jQuery Fun and Games Plugins10 jQuery Fun and Games PluginsMar 08, 2025 am 12:42 AM

10 fun jQuery game plugins to make your website more attractive and enhance user stickiness! While Flash is still the best software for developing casual web games, jQuery can also create surprising effects, and while not comparable to pure action Flash games, in some cases you can also have unexpected fun in your browser. jQuery tic toe game The "Hello world" of game programming now has a jQuery version. Source code jQuery Crazy Word Composition Game This is a fill-in-the-blank game, and it can produce some weird results due to not knowing the context of the word. Source code jQuery mine sweeping game

How do I create and publish my own JavaScript libraries?How do I create and publish my own JavaScript libraries?Mar 18, 2025 pm 03:12 PM

Article discusses creating, publishing, and maintaining JavaScript libraries, focusing on planning, development, testing, documentation, and promotion strategies.

jQuery Parallax Tutorial - Animated Header BackgroundjQuery Parallax Tutorial - Animated Header BackgroundMar 08, 2025 am 12:39 AM

This tutorial demonstrates how to create a captivating parallax background effect using jQuery. We'll build a header banner with layered images that create a stunning visual depth. The updated plugin works with jQuery 1.6.4 and later. Download the

How to Write a Cookie-less Session Library for JavaScriptHow to Write a Cookie-less Session Library for JavaScriptMar 06, 2025 am 01:18 AM

This JavaScript library leverages the window.name property to manage session data without relying on cookies. It offers a robust solution for storing and retrieving session variables across browsers. The library provides three core methods: Session

Load Box Content Dynamically using AJAXLoad Box Content Dynamically using AJAXMar 06, 2025 am 01:07 AM

This tutorial demonstrates creating dynamic page boxes loaded via AJAX, enabling instant refresh without full page reloads. It leverages jQuery and JavaScript. Think of it as a custom Facebook-style content box loader. Key Concepts: AJAX and jQuery

See all articles

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

AI Hentai Generator

AI Hentai Generator

Generate AI Hentai for free.

Hot Article

R.E.P.O. Energy Crystals Explained and What They Do (Yellow Crystal)
2 weeks agoBy尊渡假赌尊渡假赌尊渡假赌
R.E.P.O. Best Graphic Settings
2 weeks agoBy尊渡假赌尊渡假赌尊渡假赌
R.E.P.O. How to Fix Audio if You Can't Hear Anyone
2 weeks agoBy尊渡假赌尊渡假赌尊渡假赌

Hot Tools

PhpStorm Mac version

PhpStorm Mac version

The latest (2018.2.1) professional PHP integrated development tool

VSCode Windows 64-bit Download

VSCode Windows 64-bit Download

A free and powerful IDE editor launched by Microsoft

WebStorm Mac version

WebStorm Mac version

Useful JavaScript development tools

Dreamweaver CS6

Dreamweaver CS6

Visual web development tools

SublimeText3 Mac version

SublimeText3 Mac version

God-level code editing software (SublimeText3)