Recently, WHEN I was reading the content of data Structure and Algorithm, I saw some articles explaining algorithm in the form of animation on the Internet, which gave me a new understanding of algorithm. The original algorithm can also be so vivid and interesting! Now sort out my first blog. I refer to: www.cnblogs.com/onepixel/p/… Blog.csdn.net/meibenxiang… www.runoob.com/w3cnote/ten… Ps: Using “comic book algorithm” and so on, “Introduction to algorithms” is completely put on the shelf after borrowing back
0. Overview of algorithm
0.1 Algorithm Classification
The ten common sorting algorithms can be divided into two broad categories:
- Comparison sort: Determines the relative order of elements by comparison, which cannot be broken by time complexity2N), so it is also called nonlinear time comparison sort.
- Non-comparative sorting: it does not determine the relative order of elements by comparison. It can break through the lower bounds of time based on comparison sorting and operates in linear time. Therefore, it is also called linear time non-comparative sorting.
0.2 Algorithm complexity
1. Sorting algorithm with O(n^2) time complexity
- Bubble sort
- Selection sort
- Insertion sort
- Hill sort (Hill sort is special, its performance is slightly better than O(n)2), but not as good as O(nlog2N), let’s put it in this category)
2. The time complexity is O(nlog)2N) sorting algorithm
- Quick sort
- Heap sort
- Merge sort
3. Sorting algorithm with linear O(n) time complexity
- Count sorting
- Bucket sort
- Radix sort
0.3 Glossary
- Stable: If a is ahead of B and a= B, a will still be ahead of B after sorting.
- Unstable: If a is in front of B and a= B, a may appear behind B after sorting.
- Time complexity: Total number of operations on sort data. Reflect the rule of operation times when n changes.
- Spatial complexity: A measure of the storage space required for an algorithm to execute within a computer, and a function of data size N.
1, 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.
1.1 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.
1.2 GIF demonstration
1.3 Code Implementation
function bubbleSort(arr) {
var len = arr.length;
for (var i = 0; i < len - 1; i++) {
for (var j = 0; j < len - 1 - i; j++) {
if (arr[j] > arr[j+1]) { // Compare adjacent elements in pairs
var temp = arr[j+1]; // Element swap
arr[j+1] = arr[j]; arr[j] = temp; }}}return arr;
}
Copy the code2, 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.
2.1 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.
2.2 GIF demonstration
2.3 Code Implementation
function selectionSort(arr) {
var len = arr.length;
var minIndex, temp;
for (var i = 0; i < len - 1; i++) {
minIndex = i;
for (var j = i + 1; j < len; j++) {
if (arr[j] < arr[minIndex]) { // Find the smallest number
minIndex = j; // Save the smallest index
}
}
temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
return arr;
}
Copy the code2.4 Algorithm Analysis
One of the most stable sorting algorithms, because whatever data goes in is O(n2) time, so when you use it, the smaller the data, the better. The only benefit might be that it doesn’t take up any extra memory. Theoretically speaking, the choice sort may also be the usual sort ordinary people think of the most sorting method.
1, Insertion Sort
Insertion Sort algorithm is a simple and intuitive sorting algorithm. It works by building an ordered sequence, scanning back to front in the sorted sequence for unsorted data, finding the appropriate location and inserting it.
3.1 Algorithm Description
In general, insert sorts are implemented on arrays using in-place. The specific algorithm is described as follows:
- Starting with the first element, the element can be considered sorted;
- Fetch the next element and scan back to front in the sorted element sequence;
- If the element (sorted) is larger than the new element, move the element to the next position;
- Repeat step 3 until you find a place where the sorted element is less than or equal to the new element;
- After inserting a new element into that position;
- Repeat steps 2 to 5.
3.2 GIF demonstration
3.3 Code Implementation
function insertionSort(arr) {
var len = arr.length;
var preIndex, current;
for (var i = 1; i < len; i++) {
preIndex = i - 1;
current = arr[i];
while(preIndex >= 0 && arr[preIndex] > current) {
arr[preIndex+1] = arr[preIndex];
preIndex--;
}
arr[preIndex+1] = current;
}
return arr;
}
Copy the code3.4 Algorithm Analysis
In the implementation of insertion sort, in-place sort is usually adopted (that is, the sort only needs to use O(1) extra space). Therefore, in the process of scanning from back to front, the sorted elements need to be moved backward step by step repeatedly to provide insertion space for the latest elements.
4, Shell Sort
1959 Shell invention, the first breakthrough O(N2) sorting algorithm, is an improved version of simple insertion sort. It differs from insertion sort in that it compares distant elements first. Hill sort is also called reduced increment sort.
4.1 Algorithm Description
Firstly, the whole record sequence to be sorted is divided into several sub-sequences for direct insertion sorting. The specific algorithm is described as follows:
- Select a delta sequence T1, T2… , where Ti >tj, tk=1;
- Sort the sequence k times according to the number of incremental sequences k;
- In each sort, the sequence to be sorted is divided into several sub-sequences of length M according to the corresponding increment TI, and each sub-table is sorted by direct insertion. Only when the increment factor is 1, the whole sequence is treated as a table, and the length of the table is the length of the whole sequence.
4.2 GIF demonstration
4.3 Code Implementation
function shellSort(arr) {
varlen = arr.length;
for(vargap = Math.floor(len / 2); gap > 0; gap = Math.floor(gap / 2)) {
// Note: this is different from the GIF, which is executed in groups. In practice, multiple groups are executed alternately
for(vari = gap; i < len; i++) {
varj = i;
varcurrent = arr[i];
while(j - gap >= 0 && current < arr[j - gap]) {
arr[j] = arr[j - gap];
j = j - gap;
}
arr[j] = current;
}
}
returnarr;
}
Copy the code4.4 Algorithm Analysis
The core of Hill sequence is the setting of interval sequence. You can either set the interval sequence in advance or define the interval sequence dynamically. The algorithm for dynamically defining interval sequences was developed by Robert Sedgewick, co-author of Algorithms (4th Edition).
5. 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.
5.1 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.
5.2 GIF demonstration
5.3 Code Implementation
function quickSort(arr, left, right) {
var len = arr.length,
partitionIndex,
left = typeofleft ! ='number' ? 0 : left,
right = typeofright ! ='number' ? len - 1 : right;
if (left < right) {
partitionIndex = partition(arr, left, right);
quickSort(arr, left, partitionIndex-1);
quickSort(arr, partitionIndex+1, right);
}
return arr;
}
function partition(arr, left ,right) { // Partition operations
var pivot = left, // Set the pivot value
index = pivot + 1;
for (var i = index; i <= right; i++) {
if (arr[i] < arr[pivot]) {
swap(arr, i, index);
index++;
}
}
swap(arr, pivot, index - 1);
return index-1;
}
function swap(arr, i, j) {
var temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
function partition2(arr, low, high) {
let pivot = arr[low];
while (low < high) {
while (low < high && arr[high] > pivot) {
--high;
}
arr[low] = arr[high];
while (low < high && arr[low] <= pivot) {
++low;
}
arr[high] = arr[low];
}
arr[low] = pivot;
return low;
}
function quickSort2(arr, low, high) {
if (low < high) {
let pivot = partition2(arr, low, high);
quickSort2(arr, low, pivot - 1);
quickSort2(arr, pivot + 1, high);
}
return arr;
}
Copy the code6. Heap Sort
Heapsort refers to a sort algorithm designed by using heap data structure. Heap is a nearly complete binary tree structure, and also satisfies the property of heap: that is, the key value or index of the child node is always smaller (or larger) than its parent node.
6.1 Algorithm Description
- The initial sequence of keywords to be sorted (R1,R2… .rn) is constructed into the big top heap, which is the initial unordered region;
- By exchanging the top element R[1] with the last element R[n], a new unordered region (R1,R2… Rn-1) and a new ordered region (Rn), and R[1,2… n-1]<=R[n];
- Since the new heap top R[1] after the swap may violate the heap properties, it is necessary to apply the current unordered region (R1,R2… Rn-1) adjusts to the new heap, and then swaps R[1] again with the last element of the unordered region to obtain the new unordered region (R1,R2… .Rn-2) and the new ordered region (Rn-1,Rn). This process is repeated until the number of elements in the ordered region is N-1, and the whole sorting process is complete.
6.2 GIF demonstration
6.3 Code Implementation
var len; // Since multiple declared functions require data length, len is set as a global variable
function buildMaxHeap(arr) { // Create a big top heap
len = arr.length;
for (var i = Math.floor(len/2); i >= 0; i--) { heapify(arr, i); }}function heapify(arr, i) { / / heap of adjustment
var left = 2 * i + 1,
right = 2 * i + 2,
largest = i;
if (left < len && arr[left] > arr[largest]) {
largest = left;
}
if (right < len && arr[right] > arr[largest]) {
largest = right;
}
if (largest != i) {
swap(arr, i, largest);
heapify(arr, largest);
}
}
function swap(arr, i, j) {
var temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
function heapSort(arr) {
buildMaxHeap(arr);
for (var i = arr.length-1; i > 0; i--) {
swap(arr, 0, i);
len--;
heapify(arr, 0);
}
return arr;
}
Copy the codeMerge Sort (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.
7.1 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.
7.2 GIF demonstration
7.3 Code Implementation
function mergeSort(arr) { // Use a top-down recursive approach
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 code7.4 Algorithm Analysis
Merge sort is a stable sorting method. As with select sort, merge sort performs independently of the input data, but performs much better than select sort because it is always O(nlog2n) time. The trade-off is extra memory.
8, 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.
8.1 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.
8.2 GIF demonstration
8.3 Code Implementation
function countingSort(arr, maxValue) {
var bucket = new Array(maxValue+1),
sortedIndex = 0;
arrLen = arr.length,
bucketLen = maxValue + 1;
for (var i = 0; i < arrLen; i++) {
if(! bucket[arr[i]]) { bucket[arr[i]] =0;
}
bucket[arr[i]]++;
}
for (var j = 0; j < bucketLen; j++) {
while(bucket[j] > 0) { arr[sortedIndex++] = j; bucket[j]--; }}return arr;
}
Copy the code8.4 Algorithm Analysis
Counting sort is a stable sorting algorithm. When the input elements are n integers between 0 and k, the time complexity is O(n+k) and the space complexity is also O(n+k), which is faster than any comparison sorting algorithm. Counting sort is a very efficient sorting algorithm when k is not very large and the sequence is relatively concentrated.
9, Bucket Sort
Bucket sort is an updated version of counting sort. It makes use of the mapping relation of functions, and the key of efficiency lies in the determination of the mapping function. Bucket sort works by dividing the data into a finite number of buckets, assuming that the input data is evenly distributed, and sorting each Bucket separately (it is possible to use another sorting algorithm or to continue sorting using Bucket sort recursively).
9.1 Algorithm Description
- Set a quantitative array as an empty bucket;
- Iterate over the input data and put the data one by one into the corresponding bucket;
- Sort each bucket that is not empty;
- Splicing together sorted data from never-empty buckets.
9.2 GIF demonstration
9.3 Code Implementation
function bucketSort(arr, bucketSize) {
if (arr.length === 0) {
return arr;
}
var i;
var minValue = arr[0];
var maxValue = arr[0];
for (i = 1; i < arr.length; i++) {
if (arr[i] < minValue) {
minValue = arr[i]; // The minimum value of input data
} else if (arr[i] > maxValue) {
maxValue = arr[i]; // The maximum value of the input data}}// Initialize the bucket
var DEFAULT_BUCKET_SIZE = 5; // Set the default number of buckets to 5
bucketSize = bucketSize || DEFAULT_BUCKET_SIZE;
var bucketCount = Math.floor((maxValue - minValue) / bucketSize) + 1;
var buckets = new Array(bucketCount);
for (i = 0; i < buckets.length; i++) {
buckets[i] = [];
}
// Allocate data to buckets using mapping functions
for (i = 0; i < arr.length; i++) {
buckets[Math.floor((arr[i] - minValue) / bucketSize)].push(arr[i]);
}
arr.length = 0;
for (i = 0; i < buckets.length; i++) {
insertionSort(buckets[i]); // Sort each bucket, using insert sort
for (var j = 0; j < buckets[i].length; j++) { arr.push(buckets[i][j]); }}return arr;
}
Copy the code9.4 Algorithm Analysis
The optimal linear time for bucket sorting is O(n). The time complexity of bucket sorting depends on the time complexity of sorting data between buckets, because the time complexity of all other parts is O(n). Obviously, the smaller the bucket, the less data there is between the buckets, and the less time it takes to sort. But the corresponding space consumption will increase.
10, Radix Sort
Radix sort is sorted by low order and then collected; And then sort it in order, and then collect it; And so on, all the way to the highest place. Sometimes some attributes are prioritized, first by low priority, then by high priority. The final order is that the higher-priority ones come first, and the lower-priority ones come first.
10.1 Algorithm Description
- Get the largest number in the array and get the number of digits;
- Arr is the original array, and each bit is taken from the lowest level to form the RADIX array.
- The radix is sorted by counting (taking advantage of the fact that counting sorting is suitable for small range numbers);
10.2 GIF demonstration
10.3 Code Implementation
//LSD Radix Sort
var counter = [];
function radixSort(arr, maxDigit) {
var mod = 10;
var dev = 1;
for (var i = 0; i < maxDigit; i++, dev *= 10, mod *= 10) {
for(var j = 0; j < arr.length; j++) {
var bucket = parseInt((arr[j] % mod) / dev);
if(counter[bucket]==null) {
counter[bucket] = [];
}
counter[bucket].push(arr[j]);
}
var pos = 0;
for(var j = 0; j < counter.length; j++) {
var value = null;
if(counter[j]! =null) {
while((value = counter[j].shift()) ! =null) { arr[pos++] = value; }}}}return arr;
}
Copy the code10.4 Algorithm Analysis
Radix sort is based on sorting separately, collecting separately, so it’s stable. However, the performance of radix sort is slightly worse than that of bucket sort. It takes O(n) time complexity for each bucket allocation of keywords, and O(n) time complexity for obtaining new keyword sequences after allocation. If the data to be sorted can be divided into D keywords, the time complexity of radix sort will be O(D *2n). Of course, D is much smaller than N, so it is basically linear.
The space complexity of radix sort is O(n+k), where K is the number of buckets. Generally n>> K, so you need about n extra Spaces. There are two ways to sort radix:
- MSD sorts from the top
- LSD sorts from the low end
Radix sort vs counting sort vs bucket sort
These three sorting algorithms all use the concept of buckets, but there are obvious differences in the way buckets are used:
- Counting sort: Each bucket stores a single key value
- Bucket sort: Each bucket stores a range of values
- Radix sort: Buckets are allocated based on each digit of the key value