Javascript Coding Exercise: The QuickSort Implementation in Java

  • 时间:2020-09-25 11:32:47
  • 分类:网络文摘
  • 阅读:91 次

Given an array of integers nums, sort the array in ascending order.

Example 1:
Input: [5,2,3,1]
Output: [1,2,3,5]

Example 2:
Input: [5,1,1,2,0,0]
Output: [0,0,1,1,2,5]

Note:
1 <= A.length <= 10000
-50000 <= A[i] <= 50000

Relevant posts: How to Implement Quicksort Algorithm in Python – the Pythonic Way and Quick Demonstration of Quick Sort in Python

JS Javascript Coding Exercise: The QuickSort Implementation in Javascript algorithms javascript recursive sorting

NodeJs / Javascript

QuickSort in Javascript

Similarly, the quicksort implementation in Javascript can be done via Recursion. The first step is to pick a random element from the current array, which can be done via generating a random index. Here ia another post: The Recursive QuickSort Implementation in C++

The second step is to group the numbers in the array into three: the smaller ones, the equals ones and the larger ones.

Then, by recursions (to sort out the smaller and larger groups), we can concatenate (append arrays one by one) the groups by using Javascript triple dots notation.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
 * @param {number[]} nums
 * @return {number[]}
 */
var sortArray = function(nums) {
    if (nums.length === 0) return [];
    // pick a random value e.g. random.choice
    let x = nums[Math.floor(Math.random() * nums.length)];
    let lt = [];
    let eq = [];
    let gt = [];
    // separate into three groups
    nums.map(a => {
       if (a < x) lt.push(a);
       else if (a === x) eq.push(a);
       else gt.push(a);
    });
    // concatenate the part results
    let n = sortArray(lt);
    n.push(...eq);
    n.push(...sortArray(gt));
    return n;
};
/**
 * @param {number[]} nums
 * @return {number[]}
 */
var sortArray = function(nums) {
    if (nums.length === 0) return [];
    // pick a random value e.g. random.choice
    let x = nums[Math.floor(Math.random() * nums.length)];
    let lt = [];
    let eq = [];
    let gt = [];
    // separate into three groups
    nums.map(a => {
       if (a < x) lt.push(a);
       else if (a === x) eq.push(a);
       else gt.push(a);
    });
    // concatenate the part results
    let n = sortArray(lt);
    n.push(...eq);
    n.push(...sortArray(gt));
    return n;
};

Powerful, Simple and elegant – despite the fact that Javascript may look weird in some aspects!

–EOF (The Ultimate Computing & Technology Blog) —

推荐阅读:
存款保险条例(国务院令第660号)   博物馆条例(国务院令第659号)   侵害消费者权益行为处罚办法(工商总局令第73号)  先别想着做什么网站赚钱了 先做好网站建设吧  个人网站站长应了解的基础知识  作为个人站长,何不入驻今日头条  对个人站长的一些思考  一位个人站长的自白  2020疫情将过 个人站长能否有机会赚钱  这次疫情下对个人站长是机会吗? 
评论列表
添加评论