Selection Sort

Selection-sort is a simple and intuitive sorting algorithm. It works by first finding the smallest (largest) element in the unsorted sequence and storing it at the beginning of the sorted sequence, then continuing to find the smallest (largest) element from the remaining unsorted elements and placing it at the end of the sorted sequence. And so on until all the elements are sorted.

Algorithm description

Direct selection sort of N records can get ordered results after n-1 direct selection sort. The specific algorithm is described as follows:

  • Initial state: the disordered region is R[1..n], and the ordered region is empty.
  • Th order (I =1,2,3… N-1), the current ordered region and disordered region are R[1..i-1] and R(I.. N). This sorting selects the record R[k] with the smallest keyword from the current unordered region and exchanges it with the first record R in the unordered region, so that R[1.. I] and R[I +1..n) become the new ordered region with 1 more records and the new unordered region with 1 less records, respectively.
  • N minus one is done, and the array is sorted.

Code implementation

There are no subfunction versions

function selectionSort(arr) { varlen = arr.length; varminIndex, temp; for(vari = 0; i < len - 1; i++) { minIndex = i; for(varj = i + 1; j < len; J ++) {if(arr[j] < arr[minIndex]) {// find minIndex = j; }} temp = arr[I]; arr[i] = arr[minIndex]; arr[minIndex] = temp; } returnarr; }Copy the code

There are subfunction versions

/*minIndex*/ let minIndex = (numbers) => { let index = 0; for(let i = 1; i < numbers.length; i++){ if(numbers[i] < numbers[index]){ index = i; } } return index; } /*swap */ let swap = (array, I, j) => {let temp = array[I]; array[i] = array[j]; array[j] = temp; }// The array takes the parameter. When passing the argument, it copies the address of the array. Operations in the function also change the argument. /* let sort = (numbers) => {for(let I =0; i < numbers.length -1; MinIndex (numbers. Slice (I)) {let index = minIndex(numbers. Slice (I))+ I /* minIndex(numbers. ==i){ swap(numbers, index, i) } } return numbers }Copy the code

Bubble Sort

Bubble sort is a simple sorting algorithm. It repeatedly walks through the sequence to be sorted, comparing two elements at a time and swapping them if they are in the wrong order. The task of visiting an array is repeated until no more exchanges are needed, that is, the array has been sorted. The algorithm gets its name because smaller elements slowly “float” to the top of the list through swapping.

Algorithm description

  • Compare adjacent elements. If the first one is larger than the second, swap them both;
  • Do the same for each pair of adjacent elements, starting with the first pair and ending with the last pair, so that the last element should be the largest;
  • Repeat for all elements except the last one;
  • Repeat steps 1 to 3 until the sorting is complete.

Code implementation

for(let i=0; i<arr.length-1; Var j=0; var j=0; j<arr.length-i-1; J++) {/ / determine the number of comparisons each time the if (arr [j] > arr [j + 1]) {tem = arr [j]; arr[j] = arr[j+1]; arr[j+1] = tem; }}}Copy the code

Merge Sort

Merge sort is an efficient sorting algorithm based on merge operation. This algorithm is a very typical application of Divide and Conquer. The ordered subsequences are combined to obtain a fully ordered sequence. That is, each subsequence is ordered first, and then the subsequence segments are ordered. If two ordered tables are joined into one ordered table, it is called 2-way merge.

Algorithm description

  • The input sequence of length N is divided into two subsequences of length N /2.
  • Merge sort is used for these two subsequences respectively.
  • Combine two sorted subsequences into a final sorted sequence.

Code implementation

let mergeSort = arr =>{ if(arr.length===1){return arr} let left = arr.slice(0, Math.floor(arr.length/2))// math.floor let right = arr.slice(math.floor (arr.length/2)) return merge(mergeSort(left), mergeSort(right)) } let merge = (a , b) =>{ if(a.length===0) return b; if(b.length===0) return a; return a[0]>b[0]? [b[0]].concat(merge(a,b.slice(1))):[a[0]].concat(merge(a.slice(1),b)) }Copy the code

Quick Sort

The basic idea of quicksort is that the records to be sorted are separated into two independent parts through a sort. If the keywords of one part of the records are smaller than those of the other part, the two parts of the records can be sorted separately to achieve the order of the whole sequence.

Algorithm description

Quicksort uses divide-and-conquer to divide a list into two sub-lists. The specific algorithm is described as follows:

  • Pick an element from the sequence, called pivot;
  • Reorder the array so that all elements smaller than the base value are placed in front of the base value and all elements larger than the base value are placed behind the base value (the same number can go to either side). After the partition exits, the benchmark is in the middle of the array. This is called a partition operation;
  • Recursively sorts subsequences of elements less than a reference and subsequences of elements greater than a reference.

Code implementation

let quickSort = arr => { if(arr.length <= 1){return arr; } let pivotIndex = Math.floor(arr.length/2); let pivot = arr.splice(pivotIndex, 1)[0]; // Take the 0th element of the cut array, because splice returns the array let left = []; let right = []; for(let 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)); }Copy the code

Counting Sort

Counting sort is not a comparison-based sorting algorithm. Its core is to convert the input data values into keys and store them in an extra array space. As a sort of linear time complexity, counting sort requires that the input data must be integers with a definite range.

Algorithm description

  • Find the largest and smallest elements in the array to be sorted;
  • Count the number of occurrences of each element of value I in the array and store it in the i-th entry of array C;
  • Add up all the counts (starting with the first element in C, adding each term to the previous one);
  • Reverse populating the target array: place each element I in the C(I) item of the new array, subtracting C(I) by 1 for each element.

Code implementation

let countingSort = arr =>{ let hashTable = {}, max = 0, result = []; for(let i=0; i < arr.length; I++){// iterate over the group if(! (arr[i] in hashTable)){ hashTable[arr[i]] = 1; }else{ hashTable[arr[i]] += 1; } if(arr[i] > max){ max = arr[i]; } } for(let j=0; j <= max; j++){ if(j in hashTable){ for(let i=0; i < hashTable[j]; I++){//j for arr, hashashTable[j] for j, result.push(j)}} return result}Copy the code

conclusion

  1. Select sort: each time find the smallest to put in the first, and then find the smallest behind, repeat
  2. Bubble sort: Compare two adjacent numbers and switch positions if necessary
  3. Merge sort: find the midpoint, to the midpoint as the baseline left and right respectively sort, and then merge
  4. Quick sort: find the midpoint, based on the midpoint, the size of each side
  5. Counting sort: iterate over the number group, use hash table to store the occurrence times of each word, find Max at the same time, search from j∈ (0, Max), if j is in the hash table, push j exists times, if not ignored