1. Introduction

There are many kinds of sorting in data structure algorithm, common, uncommon, at least including more than ten kinds. According to their properties, they can be roughly divided into two types: comparison sort and non-comparison sort

  • Comparison sorting: to determine the relative order of elements by comparison, its time complexity can not break O(Nlogn), so it is also called nonlinear time comparison sorting.

  • 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

The sorting of non-comparison classes is seldom used in practice, and the notes mainly focus on the sorting of comparison classes. In fact, according to the stability of sorting, can also be divided into stable sorting and unstable sorting, such as quick sorting is unstable sorting, bubble sorting is stable sorting

2. Bubble sort

Bubble sort compares two elements at a time and swaps them if the order is wrong. Until there is no need to exchange

function bubbleSort(array) {
	const len = array.length
	if (len < 2) return array

	for (let i = 0; i < len - 1; i++) {
		for (let j = i + 1; j < len; j++) {

			if (array[j] < array[i]) {
				[array[i], array[j]] = [array[j], array[i]]
			}
		}
	}

	return array
}

var a = [1.3.6.3.23.76.1.34.222.6.456.221];
console.log(bubbleSort(a))  // [1, 1, 3, 3, 6, 6, 23, 34, 76, 221, 222, 456]
Copy the code

3. Quicksort

The basic idea of quicksort is to separate the records to be sorted 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

function quickSort(array) {

  var quick = function(arr) {
		const len = arr.length
    if (len < 2) return arr

    const index = Math.floor(len >> 1) // find the intermediate coordinates
		// => const index = Math.floor(len / 2)
    const pivot = arr.splice(index, 1) [0] / / intermediate value
    const left = []
    const right = []

    for (let i = 0; i < len; i++) {
			arr[i] > pivot
				? right.push(arr[i])
				: left.push(arr[i])
    }

    return quick(left).concat([pivot], quick(right))
  }
Copy the code

Pick an element from the sequence, called pivot; Then the sequence is reordered, with all elements smaller than the base value placed in front of the base value, and those larger than the base value placed behind the base value. After this distinction is made, the baseline is in the middle of the sequence; Then, the subsequence (left) less than the base value element and the subsequence (right) greater than the base value element are sorted recursively by calling quick method. This is the idea of fast sorting

4. Insert sort

By constructing an ordered sequence, unordered data can be scanned from back to front in the sorted sequence to find the corresponding position and insert, thus achieving the sorting effect

function insertSort(array) {
  const len = array.length
  let current, prev

  for (let i = 1; i < len; i++) {
    current = array[i]
    prev = i - 1

    while (prev >= 0 && array[prev] > current) {
      array[prev + 1] = array[prev]
      prev--
    }
    array[prev + 1] = current
  }
	
  return array
}
Copy the code

The idea of insertion sort is based on the array itself, first loop from I equals 1, get the current value, compare with the previous value, if the previous value is greater than the current value, swap the previous value with the current value, through this loop to achieve the purpose of sorting

5. Select sort

Store the smallest element at the beginning of the sequence, search for the smallest element from the remaining unsorted elements, and place it after the sorted sequence… And so on until all the elements are sorted

function selectSort(array) {
  const len = array.length
  let minIndex

  for (let i = 0; i < len - 1; i++) {
    minIndex = i

    for (let j = i + 1; j < len; j++) {
      if (array[j] < array[minIndex]) {
        minIndex = j
      }
    }

    [array[i], array[minIndex]] = [array[minIndex], array[i]]
  }

  return array
}
Copy the code

6. The heap sort

Heap sort is 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 than (or greater than) its parent node. The bottom layer of the heap is essentially a complete binary tree, which can be implemented using arrays

The heap with the largest root node is called the large root heap, and the heap with the smallest root node is called the small root heap. You can sort the heap from largest to smallest, or from smallest to largest, respectively

function heap_sort(arr) {
	var len = arr.length
	var k = 0
	
	function swap(i, j) {
		var temp = arr[i]
		arr[i] = arr[j]
		arr[j] = temp
	}

	function max_heapify(start, end) {
		var dad = start
		var son = dad * 2 + 1
		if (son >= end) return
		if (son + 1 < end && arr[son] < arr[son + 1]) {
			son++
		}
		if (arr[dad] <= arr[son]) {
			swap(dad, son)
			max_heapify(son, end)
		}
	}

	for (var i = Math.floor(len / 2) - 1; i >= 0; i--) {
		max_heapify(i, len)
	}

	for (var j = len - 1; j > k; j--) {
		swap(0, j)
		max_heapify(0, j)
	}

	return arr
}
Copy the code
  • The core point of heap sorting is to build the heap before sorting
  • Since the heap is a complete binary tree, if the parent node is numbered N, the leaf nodes are numbered 2n and 2n+1, respectively

There are two loops at the end of heap sort:

The first is the order in which the parent nodes are processed

The second loop adjusts the heap based on the size of the parent and leaf nodes. Through these two cycles of adjustment, finally heap sort is complete

7. Merge sort

Merge sort is an effective sorting algorithm based on merge operation, which is a very typical application of divide-and-conquer. The ordered subsequences are combined to obtain a fully ordered sequence. Order each subsequence first, and then order the segments of the subsequence. If two ordered tables are merged into one ordered table, it is called binary merge

function mergeSort(array) {
	const len = array.length
	if (len === 1) { return array }

	const mid = Math.floor(len / 2)
	const left = array.slice(0, mid)
	const right = array.slice(mid, len)

	return merge(mergeSort(left), mergeSort(right))
}

const merge = (left, right) = > {
	const result = []
	let il = 0, ir = 0

	while (il < left.length && ir < right.length) {
		left[il] < right[ir]
			? result.push(left[il++])
			: result.push(right[ir++])
	}
	while (il < left.length) {
		result.push(left[il++])
	}
	while (ir < right.length) {
		result.push(right[ir++])
	}

	return result
}
Copy the code

The array can be divided into left and right arrays by mid, and the sorting method is called recursively for the two arrays respectively. Finally, the two arrays are merged in order

8. To summarize