Code graphic analysis of JavaScript implementation of quick sort algorithm-JS Tutorial-php.cn

Code graphic analysis of JavaScript implementation of quick sort algorithm

黄舟

Release： 2017-04-15 09:31:27

Original

1606 people have browsed it

This article mainly introduces the quick sorting algorithm based on JavaScript, analyzes the principle of quick sorting, and provides the operation steps and related implementation skills of javascript quick sorting in the form of examples. Friends in need You can refer to the example below

This article describes the quick sort algorithm based on JavaScript. Share it with everyone for your reference. The details are as follows:

First of all, we need to introduce bubble sorting. The process of bubble sorting is very simple. First put the The key of one record is compared with the key of the second record. If the order is reversed, the two keys are exchanged, and then the second and third are compared until the last comparison is completed. This is the first bubbling, and as a result, the record with the largest keyword is placed in the last position. Then bubble the first n-1 elements of the sequence for the second time, and select the penultimate one. And so on until all are selected, and the bubbling ends.

Through analysis, it can be concluded that the time complexity of bubble sorting is O(n2).

Quick sort is an improvement on bubble sort. It is one of the fastest sorts to handle large data sets, through recursionThe data is decomposed into different subsequences containing smaller elements and larger elements in sequence, and the process is repeated until all the data is ordered. This algorithm must first select a baseline value and proceed around the baseline value.

The example is as follows:

Algorithm idea is as follows:

Select a base element and add the list Divide into two subsequences;

Reorder the list, put all elements smaller than the base element in the front and larger ones in the back;

Repeat the above two steps for the subsequence of smaller elements and the subsequence of larger elements.

We implement the code through js as follows:

<!DOCTYPE html>
<html lang="en">
<head>
  <meta charset="UTF-8">
  <title>JavaScript快速排序</title>
</head>
<body>
<script type="text/javascript">
  function qSort(nums) {//快速排序
    if(nums.length==0){
      return [];
    }
    var lesser=[];
    var greater=[];
    var pivot=nums[0];//选择基准元素
    for(var i=1;i<nums.length;i++){
      if(nums[i]<pivot){//分成两个之序列
        lesser.push(nums[i]);
      }else{
        greater.push(nums[i]);
      }
    }
    return qSort(lesser).concat(pivot,qSort(greater));//递归
  }
  function show(nums){//显示数组
    for(var i=0;i<nums.length;i++){
      document.write(nums[i]+&#39; &#39;);
    }
    document.write(&#39;<br>&#39;);
  }
  var nums=[68,80,12,80,95,70,79,27,88,93];
  show(nums);//newNums
  var newNums=qSort(nums);//希尔排序
  show(newNums);//0 0 2 3 4 5 5 6 8 9
</script>
</body>
</html>

Copy after login

In terms of average time, quick sort is currently considered The best internal sorting method. Quick sort is very suitable for large data sets, but performance will decrease when processing small data sets. Its time complexity is O(nlog2n)

The above is the detailed content of Code graphic analysis of JavaScript implementation of quick sort algorithm. For more information, please follow other related articles on the PHP Chinese website!