Diagram of ten sorting algorithms

N: Data scale
K: Number of buckets
In-place: takes up constant memory, no extra memory
Out-place: takes up extra memory

In-place sorting: the sorting algorithm whose space complexity is O(1)O(1)O(1).

Stability: If there are elements of the same value in the sorted sequence, the order of the elements will not change after sorting.

1. Bubble Sort

Algorithm thought

Bubbling sort is through the comparison and exchange between adjacent elements, so that the elements with smaller values gradually move from the back to the front, and the elements with larger values move from the front to the back, just like bubbles on the bottom of the water, so this sorting method is called bubbling sort method.

Algorithm steps

The first element in the array is compared with the second element. If the first element is larger than the second element, the two elements are swapped; otherwise, they are not swapped.
The second element is then compared with the third element. If the former is greater than the latter, the two will swap places, otherwise not.
Repeat until the n-1st element is compared (or swapped) with the NTH element. After such a sequence, the element with the largest value of n elements is placed in the NTH position of the array;
Then, the above process is carried out for the first n-1 element, so that the element with the largest value in the first n-1 element is placed in the n-1 position.
The above process is then repeated for the first n-2 elements until there is no change of position in the sorting process, and the sorting is finished.

Graphic thinking

Code implementation

function bubbleSort(arr) {
  const { length } = arr;
  for (let i = 0; i < length; i++) {
    // Subtracts I to stop iterating over the sorted elements
    for (let j = 0; j < length - 1 - i; j++) {
	  if (arr[j] > arr[j + 1]) {
	    [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]]; }}}return arr;
}
Copy the code

Complexity analysis

Time complexity: O(n2)O(n^2)O(n2). Each round of bubble sort iterates through all elements, for a total of (number of elements -1) rounds. Space complexity: O(1)O(1)O(1). You just have to use the extra space of the constant.

2. Select sort

Algorithm thought

Find the smallest value in the data structure and place it first, then find the second-smallest value and place it second, and so on.

Algorithm steps

So at the beginning of each sort run, I’m going to startmin = i(That is, the ith element of the sequence is temporarily assumed to be the minimum value, and the position of the minimum element is determined after comparison).
At the end of trip I, this isN − I + 1The element with the smallest value is the subscriptminThe corresponding element. At this point, ifmin == iThat means that the least valued element is right hereN − I + 1The first element of the element, meaning that there is no element swap for this sort; Otherwise exchange controlminAnd the firstiAn element.
Repeat until you reach the last element

Graphic thinking

Code implementation

function selectionSort(arr) {
  const { length } = arr;
  let min = 0;
  for (let i = 0; i < length; i++) {
    min = i;
	for (let j = i; j < length - 1; j++) {
	  if(arr[min] > arr[j]) { min = j; }}if (min !== i) {
	  [arr[min], arr[i]] = [arr[i], arr[min]];
	}
  }
  
  return arr;
}
Copy the code

Complexity analysis

Time complexity: O(n2)O(n^2)O(n2). Selecting a sequence with n elements requires n-1 sequences, and n-I + 1 elements are compared in each sequence. Space complexity: O(1)O(1)O(1). You just have to use the extra space of the constant.

3. Insert sort

Algorithm thought

The whole sequence is divided into two parts: the first I-1 element is an ordered sequence, and the last N-i + 1 element is an unordered sequence. Each time, the first element of the unordered sequence is inserted into the ordered sequence.

Algorithm steps

The first element is regarded as an ordered sequence, and the 2nd ~ n-1 element is regarded as an unordered sequence.
Scan the unordered sequence from beginning to end, inserting each scanned element into its proper place in the ordered sequence.

Graphic thinking

Code implementation

function insertionSort(arr) {
  const { length } = arr;
  for (let i = 1; i < length; i++) {
    let j = i;
    let temp = arr[i];
    while (j >= 1 && arr[j - 1] > temp) {
      arr[j] = arr[j - 1];
      j--;
    }
    arr[j] = temp;
  }
  return arr;
}
Copy the code

Complexity analysis

Time complexity: O(n2)O(n^2)O(n2). The array is traversed once, along with the previously sorted interval comparison. Space complexity: O(1)O(1)O(1). You just have to use the extra space of the constant.

4. Hill sort

Algorithm thought

The whole sequence is divided into several sub-sequences according to a certain interval value, and each sub-sequence is inserted and sorted separately. Then, the interval is gradually narrowed for the next round of molecular sequence and insertion sorting. Insertion sort is performed on the whole sequence until the last sort interval is 1.

Algorithm steps

Firstly, an element interval number gap is determined, and then the sequence participating in the sorting is divided into several sub-sequences from the first element according to the interval number, that is, all the elements separated by gap are regarded as a sub-sequence, and some sorting method is used in each sub-sequence (insertion sorting is used here);
Then reduce the number of intervals, and re-divide the whole sequence into several sub-sequences according to the new number of intervals, and sort each sub-sequence respectively. And so on, until the gap is equal to 1.

Graphic thinking

Code implementation

function shellSort(arr) {
  const length = arr.length;
  let gap = Math.floor(length / 2);
  while (gap > 0) {
    // Insert the gap element one by one
    for (let i = gap; i < length; i++) {
	  let temp = arr[i];
	  let j = i;
	  while (j >= gap && arr[j - gap] > temp) {
	    arr[j] = arr[j - gap];
	    j -= gap;
	  }
	  arr[j] = temp;
	}
	gap = Math.floor(gap / 2);
  }
  
  return arr;
}
Copy the code

Complexity analysis

Time complexity: O(nlogn)O(nlogn)O(nlogn). Space complexity: O(1)O(1)O(1). You just have to use the extra space of the constant.

5. Merge sort

Algorithm thought

Merge sort is a divide-and-conquer algorithm. The idea is to cut the original array into smaller arrays until each of the smaller arrays has only one location, and then merge the smaller arrays into larger arrays until there is only one sorted large array.

Algorithm steps

Divide the array into two halves, sort the two halves separately, and merge the sorted halves together.

Graphic thinking

Code implementation

function merge(left, right) {
  let i = 0;
  let j = 0;
  const result = [];
  while (i < left.length && j < right.length) {
    result.push(left[i] < right[j] ? left[i++] : right[j++]);
  }
  
  return result.concat(i < left.length ? left.slice(i) : right.slice(j));
}

function mergeSort(arr) {
  if (arr.length > 1) {
    const middle = Math.floor(arr.length / 2);
	const left = mergeSort(arr.slice(0, middle));
	const right = mergeSort(arr.slice(middle));
	
	arr = merge(left, right);
  }
  
  return arr;
}
Copy the code

Complexity analysis

Time complexity: O(nlogn)O(nlogn)O(nlogn). Space complexity: O(n)O(n)O(n).

6. Quicksort

Algorithm thought

Quicksort: Split the sequence into two parts by picking a base element in each round and moving other elements larger than it to one side and smaller elements to the other.

Algorithm steps

Select a base element (select the middle element of the array below), move the elements larger than it to the right, and the elements smaller than it to the left, and return the index position I. Repeat the previous steps until the index position is no longer divisible (so to speak, there is only one element).

Graphic thinking

Code implementation

function quickSort(arr) {
  return quick(arr, 0, arr.length - 1);
}

function quick(arr, left, right) {
  let index;
  if (array.length > 1) {
    index = partition(arr, left, right);
	if (left < index - 1) {
	  quick(arr, left, index - 1);
	}
	if(index < right) { quick(arr, index, right); }}}function partition(arr, left, right) {
  const pivot = arr[Math.floor((right + left) / 2)];
  let i = left;
  let j = right;
  
  while (i <= j) {
    while (arr[i] < pivot) {
	  i++;
	}
	while (arr[j] > pivot) {
	  j--;
	}
	
	if(i <= j) { [arr[i], arr[j]] = [arr[j], arr[i]]; i++; j--; }}return i;
}
Copy the code

Complexity analysis

Time complexity: O(nlogn)O(nlogn)O(nlogn). Space complexity: O(1)O(1)O(1). You just have to use the extra space of the constant.

7. The heap sort

Algorithm thought

Borrow “heap structure” design sort algorithm. The array is converted to the big top heap, and the node with the largest value is repeatedly removed from the big top heap, and the remaining heap remains the big top heap.

Algorithm steps

To construct the disordered number into a binary heap, it is necessary to sort from small to large, then it is constructed into the maximum heap. To sort from large to small, build a minimum heap;
The loop removes the top element, replaces it to the end of the binary heap, and adjusts the heap to produce a new top.

Graphic thinking

Code implementation


function heapSort(arr) {
	buildHeap(arr, arr.length);
	let k = arr.length - 1;
	while (k > 0) {
		// Place the top element at the end of the current heap
		[arr[k], arr[0]] = [arr[0], arr[k]];
		k--;
		// Rebuild the big top heap from the unsorted elements
		heapify(arr, k, 0);
	}

	return arr;
}

// n indicates the number of elements in the heap
function buildHeap(arr, n) {
	// Start from bottom to top from the first non-leaf node
	for (let i = Math.floor((n - 1) / 2); i >= 0; i--) { heapify(arr, n, i); }}/ / heap
function heapify(arr, n, i) {
	while (true) {
		let maxPos = i;
		// Compare with the left child node, take the maximum position
		if (i * 2 + 1 <= n && arr[i] < arr[i * 2 + 1]) {
			maxPos = i * 2 + 1;
		}
		// Compare with the right child node, take the maximum position
		if (i * 2 + 2 <= n && arr[i * 2 + 2] > arr[maxPos]) {
			maxPos = i * 2 + 2;
		}
		if (maxPos === i) {
			break; } [arr[i], arr[maxPos]] = [arr[maxPos], arr[i]]; i = maxPos; }}Copy the code

Complexity analysis

Time complexity: O(nlogn)O(nlogn)O(nlogn). Space complexity: O(1)O(1)O(1). You just have to use the extra space of the constant.

8. Counting sort

Algorithm thought

Counting sort and other sort is different, not by comparing the size of elements to achieve, but by counting all the same elements appear the number of times to sort, the idea is very different from other sort.

As a sort of linear time complexity, counting sort requires that the input data must be integers with a definite range.

Algorithm steps

Find the maximum and minimum element 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 the array;
Sums all counts (starting with the first element in COUNTS and summing each and the previous one)
Inversely populate the target array: Place each element I in the counts[I] column of the new array. For each element, count [I] -= 1.

Graphic thinking

Code implementation

function countSort(arr) {
	let maxValue = arr[0];

    // Find the maximum value
	for (let i = 1; i < arr.length; i++) {
		if(arr[i] > maxValue) { maxValue = arr[i]; }}const temp = new Array(maxValue + 1);
	temp.fill(0);

    // Count the number of each element and place it in temp
	for (let i = 0; i < arr.length; i++) {
		temp[arr[i]]++;
	}

	// // copies the results to the ARR array
	let p = 0;
	for (let i = 0; i < temp.length; i++) {
		let j = temp[i];

		while (j > 0) { arr[p++] = i; j--; }}return arr;
}
Copy the code

Complexity analysis

Time complexity: O(n)O(n)O(n). Space complexity: O(n)O(n)O(n). Where n is the value of the largest element in the array, and a temporary array of length N is needed to count it.

9. Bucket sorting

Algorithm thought

Bucked Sort is to store the elements in the set to be sorted in the same range into the same bucket, that is, according to the characteristics of the element value, the set is divided into multiple regions, then the buckets formed after splitting are in an ordered state from the range. If the elements in each bucket are sorted, the set of elements in all buckets is sorted.

Algorithm steps

Let’s divide the interval into twonTwo sub-intervals of the same size, each called a bucket;
Iterate over the number group, and put each element into the corresponding bucket;
Sort the elements within each bucket individually (using insert, merge, quicksort, etc.);
Finally, merge the elements in the bucket in order.

Graphic thinking

Code implementation

function bucketSort(arr) {
	if (arr.length < 2) {
		return arr;
	}
	
	/ / create a bucket
	const buckets = createBuckets(arr);
	
	return sortBuckets(buckets);
}

function createBuckets(arr) {
	// The number of elements in each bucket
	const bucketSize = 3;
	let minValue = arr[0];
	let maxValue = arr[0];
	for (let i = 1; i < arr.length; i++) {
		if (arr[i] < minValue) {
			minValue = arr[i];
		} else if(arr[i] > maxValue) { maxValue = arr[i]; }}// Number of buckets
	const bucketCount = Math.floor((maxValue - minValue) / bucketSize) + 1;
	const buckets = [];
	for (let i = 0; i < bucketCount; i++) {
		buckets[i] = [];
	}
	for (let i = 0; i < arr.length; i++) {
		const bucketIndex = Math.floor((arr[i] - minValue) / bucketSize);
		buckets[bucketIndex].push(arr[i]);
	}
	
	return buckets;
}

function sortBuckets(buckets) {
	const sortedArray = [];
	for (let i = 0; i < buckets.length; i++) {
		if (buckets[i].length) {
			// Sort each bucket with insert sort
			insertionSort(buckets[i]);
			// tiled the sortedArray into sortedArray
			sortedArray.push(...buckets[i]);
		}
	}
	return sortedArray;
}
Copy the code

Complexity analysis

Time complexity: O(n+ K)O(n+ K)O(n+k). Where n is the number of elements in the array and k is the number of buckets. Space complexity: O(n+k)O(n +k)O(n +k). Where n is the number of elements in the array and k is the number of buckets.

10. Radix sort

Algorithm thought

Radix sort is improved on the basis of counting sort by splitting the sorting work into multiple stages, each stage is sorted according to only one character, a total of N rounds of sorting (n is the data length).

Algorithm steps

Radix sort starts with sorting the digits based on the last significant bit, and on the next iteration, it sorts on the second significant bit, then the third significant bit, and so on until there are no significant bits left to sort

Graphic thinking

Code implementation


MaxDigit {number} maxDigit **/
function radixSort(arr, maxDigit = 10) {
	if (arr.length < 2) {
		return arr;
	}
	let mod = 10;
	// Start the sequence from back to front
	let dev = 1;
	let counter = [];
	for (let i = 0; i < maxDigit; i++, dev *= 10, mod *= 10) {
		// Assign buckets according to valid bits (valid bits are the same in the same bucket)
		for (let j = 0; j < arr.length; j++) {
			// Get the current significant bit
			const bucket = Math.floor((arr[j] % mod) / dev);
			if(! counter[bucket]) { counter[bucket] = []; } counter[bucket].push(arr[j]); }// If only one bucket contains data, the sorting is complete
		if (counter[0].length === arr.length) {
			break;
		}
		let pos = 0;
		// Reassign the bucket elements to the original array (sorted by significant bits)
		for (let j = 0; j < counter.length; j++) {
			let value;
			if (counter[j] && counter[j].length) {
				value = counter[j].shift();
				while (value >= 0) { arr[pos++] = value; value = counter[j].shift(); }}}}return arr;

}
Copy the code

Complexity analysis

Time complexity: O(N ∗k)O(n * k)O(n∗k). Where n is the number of elements in the array and k is the number of buckets. Space complexity: O(n+k)O(n +k)O(n +k). Where n is the number of elements in the array and k is the number of buckets.

Limited ability, general level, if there are mistakes, welcome to correct.

Diagram of ten sorting algorithms

1. Bubble Sort

Algorithm thought

Algorithm steps

Graphic thinking

Code implementation

Complexity analysis

2. Select sort

Algorithm thought

Algorithm steps

Graphic thinking

Code implementation

Complexity analysis

3. Insert sort

Algorithm thought

Algorithm steps

Graphic thinking

Code implementation

Complexity analysis

4. Hill sort

Algorithm thought

Algorithm steps

Graphic thinking

Code implementation

Complexity analysis

5. Merge sort

Algorithm thought

Algorithm steps

Graphic thinking

Code implementation

Complexity analysis

6. Quicksort

Algorithm thought

Algorithm steps

Graphic thinking

Code implementation

Complexity analysis

7. The heap sort

Algorithm thought

Algorithm steps

Graphic thinking

Code implementation

Complexity analysis

8. Counting sort

Algorithm thought

Algorithm steps

Graphic thinking

Code implementation

Complexity analysis

9. Bucket sorting

Algorithm thought

Algorithm steps

Graphic thinking

Code implementation

Complexity analysis

10. Radix sort

Algorithm thought

Algorithm steps

Graphic thinking

Code implementation

Complexity analysis

Related Posts

JS design pattern 3: module pattern

Babel(4) : plugins

What is the difference between map() and forEach() in JavaScript?