algorithm
In the Art of Computer Programming, Gartner summarized algorithms as follows:
- Input: An algorithm must have zero or more inputs
- Output: An algorithm should have one or more outputs
- Clarity: The description of the algorithm must be unambiguous, and the actual results of the operation must be certain
- Finiteness: Must end in a finite number of steps
- Effectiveness: also known as feasibility, can be implemented
Data Structure and Algorithm Analysis is recommended if you want to study the algorithm in detail.
Define the problem
Array Array contains N positive integers. The input quantity is array. The output quantity is a sorted array
The code example
var array = [5.2.4.6.8]
function sort(){your code} sort(array) === [2.4.5.6.8]
Copy the codeWhat do you do when you run into a mental block?
- Turn abstract problems into concrete ones
- Turn unseen problems into seen problems
Sorting algorithm
A demo of all algorithms can be viewed here
BUBBLE sort
Repeatedly compare the sequence to be sorted, comparing two elements at a time and swapping them if they are in the wrong order. The task of comparing a sequence is repeated until no more exchanges are needed, that is, the sequence has been sorted. For each full round of comparisons, the largest one appears at the end of the name – bubble sort
The process is as follows:
- We get an array
- I start comparing the first two, and I find 44 is greater than 3, so I don’t swap
- And then we go back and we find 38 is less than 44, so we switch them
- And so on until the end of the first round, we get the biggest one —-50(The first bubble)
- Then in the next round, we start from the beginning two by two, repeating the first round, we get the second largest ——48
- We do this multiple times and we get an array from small to large
- Code implementation:
function bubbleSort(array) {
for (let i = 0; i < array.length - 1; i++) {
for (let j = 0; j < array.length - i - 1; j++) {
if (array[j] > array[j + 1]) {
let temp = array[j];
array[j] = array[j + 1];
array[j + 1] = temp; }}}}Copy the code2. SELECT sort
Each time the smallest (or largest) element is selected from the data elements to be sorted and stored at the beginning of the sequence until all the data elements to be sorted are sorted. The process is as follows:
- Get an array
- We’re going to pick the smallest element in the array and swap it with the first one, so we’re going to take 3 as the smallest, and then compare it to the next one.
- When we get to 2, we find that 3 is greater than 2, so we assume that 2 is the minimum, and we should compare everything to 2.
- When you compare all the elements and determine that 2 is the minimum value, switch the minimum value, which is 2, with the position of the first element.
- Then start a new round of comparison from the second element, the same process as the first round. Let’s take 44 as the minimum and compare it to everything else.
- After several rounds of comparison, we get an array from small to large.
- Code implementation
function selectSort(arr) {
var minIndex, temp;
for (let i = 0; i < arr.length - 1; i++) {
minIndex = i; // Take the first one as the minimum
for (let j = i + 1; j < arr.length; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
return arr;
}
Copy the code3, INSERT sort
The algorithm is suitable for sorting a small amount of data by inserting a data into the ordered data that has already been ordered, thus obtaining a new, number plus one ordered data. It’s a stable sorting method. The process is as follows:
- Get an array
- Treat the first element as a new array, and then compare the second element in turn to the elements of the new array (although there is only one…). And then insert it into the appropriate position.
- Then, by analogy, the first two elements are treated as a new array, and the third element is compared to the new array in turn and inserted into the appropriate position.
- Insert the remaining elements in order, resulting in the smallest to largest array.
- Code implementation
function insertionSort(array) {
for (let i = 1; i < array.length; i++) {
let key = array[i];
let j = i - 1;
while (j >= 0 && array[j] > key) {
array[j + 1] = array[j];
j--;
}
array[j + 1] = key;
}
return array;
}
Copy the code4. MERGE sort
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. The process is as follows:
- Get an array
- We divide the array equally into the left and right, we get two new arrays, and then we divide each array equally into two parts, until we get only two elements in each array, and then we compare the first group
- So 3 is less than 44 so it stays the same and then the second group, 38 is more than 5 so we switch places.
- So the point is, at this point we’re not going to compare the third group but we’re going to put the first and second groups together.
- Then you compare the third group and the fourth group, and you put them together again.
- Then, instead of comparing the fifth and sixth groups, you sort the new array from the first and second groups together with the new array from the third and fourth groups.
- Do the same for the rest of the process. We have two sorted arrays. And we’re done sorting these two arrays.
After the order:
- Code implementation
function mergeSort(arr) {
var len = arr.length;
if (len < 2) {
return arr;
}
var middle = Math.floor(len / 2),
left = arr.slice(0, middle),
right = arr.slice(middle);
return merge(mergeSort(left), mergeSort(right));
}
function merge(left, right) {
var result = [];
while (left.length && right.length) {
if (left[0] <= right[0]) {
result.push(left.shift());
} else{ result.push(right.shift()); }}while (left.length)
result.push(left.shift());
while (right.length)
result.push(right.shift());
return result;
}
Copy the code5. Quicksort
Each element finds its position (the first one is smaller than me, the second one is larger than me) as follows:
- Get an array
- Compare the first element with the following element, find all the elements that are smaller than the first element, put them to the right of the first element and swap the first element with the last of these elements that are smaller.
- The first two elements are already in the right place, and the third element is used as the standard to compare with the following elements.
- Put the element smaller than it to its right (green) and make it swap places with the last one green.
- Then start with the element (not orange) on the left that has no definite position —-, which is 19
- Until all the elements are in the right place.
- Code implementation
let quickSort = function (arr) {
if (arr.length <= 1) { return arr; }
let pivotIndex = Math.floor(arr.length / 2);
let pivot = arr.splice(pivotIndex, 1) [0];
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 code6. Random quicksort
As the name suggests, it is based on quicksort, adding randomness mechanism. In quicksort we pick from left to right, in random quicksort we pick at random. The process is as follows:
- Get an array
- Select an element at random.
- And he put the one younger than he on his right
- And then swap it with the smaller, right-most element
- Then pick a random element and repeat the process until all the elements are in the right place.
- Code implementation
let quickRandomSort = function (arr) {
if (arr.length <= 1) { return arr; }
let pivotIndex = Math.floor(Math.random()*arr.length);
let pivot = arr.splice(pivotIndex, 1) [0];
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