Sorting algorithm is the most frequently used in daily life, many complex scenes in the work need to use sorting, such as sorting data and then do search, analysis, statistics and other processing.

Bubble sort

Basic idea:

  • Basic idea: bubbling sort, similar to bubbling in water, the larger number sinks and the smaller number rises slowly. Assume that from small to large, that is, the larger number slowly moves to the back row and the smaller number slowly moves forward.
  • Visually, each time you walk, you move the largest number to the end of the sequence.

Algorithm description:

Compare adjacent elements, if the previous one is larger than the next, swap them.

The first trip sort the first and second pair, compare and swap, then the second and third pair compare swap, and so on until the second and last one, move the largest number to the last digit.

The second trip moves the second largest number to the last

Code visualization:

Code implementation:

Var arr =,3,32,5,1,2,3,4 [1]; for(var i=0; i<arr.length-1; i++){ for(var j=0; j<arr.length-i-1; j++){ if(arr[j]>arr[j+1]){ var temp = arr[j]; arr[j] = arr[j+1]; arr[j+1] = temp; } } } console.log(arr);Copy the code

Selection sort

First, find the smallest element in the unsorted sequence and place it at the beginning of the sorted sequence. Then, continue to find the smallest element from the remaining unsorted elements and place it in the second element. And so on until all the elements are sorted.

Algorithm description:

  1. In an unordered array of length N, the first iteration of an n-1 number finds the smallest and first commutation.

  2. The second time you go through the n-2 number starting with the next number, find the smallest number and swap with the second number.

  3. Repeat the above operation until the n-1st iteration of the smallest number and the n-1st number are swapped, and the sorting is complete.

Algorithm visualization:

Code implementation:

Var example =,94,15,88,55,76,21,39 [8]; function selectSort(arr){ var len=arr.length; var minIndex,temp; Console. time(' Select sort time '); for(i=0; i<len-1; i++){ minIndex=i; for(j=i+1; j<len; j++){ if(arr[j]<arr[minIndex]){ minIndex=j; } } temp=arr[i]; arr[i]=arr[minIndex]; arr[minIndex]=temp; } console.timeEnd(' select sort time '); return arr; } console.log(selectSort(example));Copy the code

Selection sort and bubble sort difference:

  • Bubble sort compares the left and right numbers, while selection sort compares the next number with the first number in each round;
  • Bubble sort swaps more times in each round, while select sort swaps only once in each round.
  • Bubble sort is to find the position by number, selection sort is to find the number by given position;
  • When an array encounters the same number, bubble sort is relatively stable, while selection sort is unstable;
  • In terms of time efficiency, selection sort is better than bubble sort.

Other instructions

  • Time complexity refers to the time it takes an algorithm to execute.
  • Spatial complexity refers to the amount of memory required to run a program.
  • Stable means that if a is equal to B, a is ahead of B, and a is still ahead of B after sorting.
  • Unstable means that if a is equal to B, a comes before B, and it might switch places after sorting.

Technology Communication: The Front End – DORA