Example analysis of JavaScript implementation of selection sort algorithm (picture)-JS Tutorial-php.cn

Example analysis of JavaScript implementation of selection sort algorithm (picture)

黄舟

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

Original

1818 people have browsed it

This article mainly introduces the selection sorting algorithm implemented in JavaScript, and analyzes the principle, implementation steps and related operation techniques of selection sorting in the form of examples. Friends in need can refer to it. Next

The example in this article describes the selection sorting algorithm implemented in JavaScript. Share it with everyone for your reference, the details are as follows:

Simple selection sorting is the most familiar comparison method, and its algorithm idea is: FromStarting from the beginning of the array, compare the first element with other elements. After all elements have been checked, the smallest element is placed at the first position of the array, and the algorithm continues from the second position. This process will continue until the penultimate position of the array is reached, and all data will be sorted.

The code is as follows:

<!DOCTYPE html>
<html>
<head>
<meta charset="utf-8">
<title>JavaScript选择排序</title>
</head>
<body>
<script type="text/javascript">
 function selectSort(nums){//选择排序
  var min;//最小值
  for(var outer=0;outer<nums.length-1;outer++){//外循环选中元素
   min=outer;
   for(var inner=outer+1;inner<=nums.length;++inner){
    if(nums[inner]<nums[min]){//如果内循环中元素比选中元素小
     min=inner;//将其标为最小元素
    }//直到每次外循环的最小元素
    swap(nums,outer,min);//最小值被调整到合适的位置
   }
  }
 }
 function swap(arr,i,j){//交换位置
  var temp=arr[i];
  arr[i]=arr[j];
  arr[j]=temp;
 }
 function show(nums){//显示数组
  for(var i=0;i<nums.length;i++){
   document.write(nums[i]+&#39; &#39;);
  }
  document.write(&#39;<br>&#39;);
 }
 var nums=[6,8,0,6,7,4,3,5,5,10];
 show(nums);//6 8 0 6 7 4 3 5 5 10
 selectSort(nums);
 show(nums);//0 3 4 5 5 6 6 7 9 10
</script>
</body>
</html>

Copy after login

Analysis shows that the time complexity of simple selection sorting is O(n2). The main operation of selection sorting is comparison between keywords, so improving simple selection sorting should start from how to reduce comparisons. In fact, there is a good example in real life, which is the total championship of the game. Selecting the champion among 8 people does not actually require 7+6+5=18 games. It can be done through pairwise comparison, which is 11 games. This method is calledTree selection sort.

Tree selection sorting is a method of selecting and sorting according to the idea of a tournament. First, compare the keywords of n records in pairs, and then compare n/2 of them. The smaller ones are then compared in pairs until the smallest keyword is found. It can be represented by a complete binary tree. Since the depth of a complete binary tree containing n nodes is log2n+1, each selection of a sub-small keyword only requires log2n operations during the sorting process, so its time complexity is O (nlog2n) , but this sorting has the disadvantage of taking up a lot of space.

So we need to introduce a more excellent sorting, which is Heap sorting.

Attachment: Heap sort algorithm

##Heap sortOnly requires an auxiliary record size space, each record to be sorted only occupies one storage space.

Heap sorting takes advantage of the feature that the key recorded at the top of the large root heap (or small root heap) is the largest (or smallest), so that the record with the largest (or smallest) keyword selected in the current unordered area becomes Gotta be simple. Let's take the big heap as an example. The basic operations of sorting are as follows:

The first step is to

build the heap. Building the heap is the process of constantly adjusting the heap, starting from len2 and continuing to the first nodes, where len is the number of elements in the heap. The process of building a heap is a linear process. The process of adjusting the heap is always called from len2 to 0. The time complexity of building a heap is O(n). Next is
Adjustment heap. Adjustment heap is used in the process of heap building and heap sorting. The idea of utilization is to compare node i and its child node left( i) and right(i), select the largest (or smallest) of the three. If the largest (small) value is not node i but one of its child nodes, then exchange the two nodes and continue recursion. Then
heap sort:Take out the root node of the heap, replace the root node with the last element, continue the heap adjustment process with the first len-1 nodes, and then Talk about removing the root node until all nodes are removed. The time complexity of adjusting the heap is O(log2n)So the time complexity of heap sorting is O(nlog2n). Heap sort is an in-place sort and its auxiliary space is O(1). But it is unstable (
Stability of sorting means that if there are two identical elements in the sorted sequence, their relative positions will not change before and after sorting).

The following simulates the process of building a heap:

Heap sorting is not worth advocating for files with a small number of records, but it is still suitable for files with a large n Quite effective.

The above is the detailed content of Example analysis of JavaScript implementation of selection sort algorithm (picture). For more information, please follow other related articles on the PHP Chinese website!