Summarize some sorting algorithms. Algorithm in any programming language can be implemented, algorithm focus is the idea, rather than language, we use JS here to demonstrate.

The array.prototype. sort method can be used to sort a prototype.

1. Bubble sort

Basic idea:

1. Compare two adjacent numbers in turn. If the first is smaller than the second, it remains the same. If the first one is larger than the second, reverse the order. After the round, the last number is the largest 2. Repeat the first step for all numbers except the last one until there is only one number left

Graphic display:

Code:

function bubbleSort(myArray){
  var len = myArray.length;
  var i;
  var j;
  var stop;

  for (i = 0; i < len - 1; i++){
    for (j = 0, stop = len - 1 - i; j < stop; j++){
      if (myArray[j] > myArray[j + 1]){
        exchange(myArray, j, j + 1); }}}return myArray;
}

function exchange(myArray, p1, p2){
  var temp = myArray[p1];
  myArray[p1] = myArray[p2];
  myArray[p2] = temp;
}
Copy the code

2. Select sort

Basic idea:

2. Of the remaining numbers, find the second smallest number and place it in the second 3. And so on and so forth

Graphic display:

Code:

function selectionSort(myArray){

    var len = myArray.length,
        min;

    for (i=0; i < len; i++){

        // Set the current position to the minimum value
        min = i;

        // Check if the rest of the array is smaller
        for (j=i+1; j < len; j++){
            if(myArray[j] < myArray[min]){ min = j; }}// If the current position is not minimum, change it to minimum
        if (i != min){
            exchange(myArray, i, min);
        }
    }

    return myArray;
}
function exchange(myArray, p1, p2){
    var temp = myArray[p1];
    myArray[p1] = myArray[p2];
    myArray[p2] = temp;
}
Copy the code

3. Insert sort

Basic idea:

1. Divide the array into sorted and unsorted parts. The first part is sorted and the other parts are unsorted. Extract the first term from [unsorted], compare it with the [sorted] portion, and insert it into the appropriate position

Graphic display:

Code:

function insertionSort(myArray) {

    var len     = myArray.length,     // The length of the array
        value,                      // The current value of the comparison
        i,                          // The current position of the unsorted part
        j;                          // The current position of the sorted part

    for (i=0; i < len; i++) {

        // Store the value of the current location
        value = myArray[i];

        /* * When the current element of the sorted part is greater than value, * moves the current element one bit back and compares the previous bit with value */
        for (j=i-1; j > -1 && myArray[j] > value; j--) {
            myArray[j+1] = myArray[j];
        }

        myArray[j+1] = value;
    }

    return myArray;
}
Copy the code

4. Merge sort

Basic idea:

1. Keep cutting the array in half until each array has only one. 2. Put them in order when merging

Graphic display:

Function merge(left, right) {var result = [], left_index = 0, right_index = 0; While (left_index < lef.length && right_index < right.length) {if (left[left_index] < right[right_index]) { result.push(left[left_index++]); } else { result.push(right[right_index++]); Return result.concat(lef.slice (left_index)).concat(right.slice(right_index)); return result.concat(lef.slice (left_index)). } function mergeSort(myArray) {if (myarray. length < 2) {return myArray; } var middle = Math.floor(myArray.length / 2), left = myArray.slice(0, middle), right = myArray.slice(middle); Merge (mergeSort(left), mergeSort(right)); merge(mergeSort(left), mergeSort(right)); }Copy the code

5. Quicksort

Basic idea:

1. Base on a number (the middle number), place the number smaller than the base on the left, and place the number larger than the base on the right 2. Then use this method to quickly sort the two parts of the data respectively (recursive) 3. Cannot exit the recursion after splitting, and merge the array again

Picture show:

Code:

var quickSort = function(myArray) {Exit recursion when there is only one array left to divide
if (myArray.length <= 1) {
return myArray;
   }

// Index of intermediate datum
var pivotIndex = Math.floor(myArray.length / 2);/ / value
var pivot = myArray.splice(pivotIndex, 1) [0];varleft = [];varright = [];// Put the small ones on the left and the big ones on the right
for (var i = 0; i < myArray.length; i++) {if(myArray[I] < pivot) {left.push(myArray[I]); }else{right. Push (myArray on [I]); }}/ / recursion
// Merge arrays together
return quickSort(left).concat([pivot], quickSort(right));
};
Copy the code