At the beginning of the New Year, it’s time for gold, silver and silver. In the face of more and more algorithm interview questions, I simply sorted out several more common array sorting methods, respectively introduced their basic principles and advantages and disadvantages. (ps: lack of talent, hope you can point out the issues below)

Selection sort

The principle of

Select sort to iterate over the maximum value, add a new array, delete the maximum value from the original array, repeat the above operation, and the resulting array is sorted from largest to smallest.

Code implementation

/** * params {number[]} list * return {number[]} */
function sort(list) {
  list = [...list]; // It is best not to operate on groups of elements
  const newList = []; // Create an empty array to return
  while(list.length) { // If list.length === 0, the processing is complete
    let min = Infinity; // Set the minimum value to infinity or equal to any position in the list
    let minIndex; // Record the minimum subscript
    list.forEach((el, index) = > { // Loop through list to find the minimum value of the current list
      if(el < min) { min = el; minIndex = index; }}); newList.push(list[minIndex]);// Push the minimum subscript into the array
    list.splice(minIndex, 1); // Delete the value from the list
  }
  return newList
}
Copy the code

Pros and cons

Advantages:

  • Start relatively simple, more in line with the normal logic of people’s thinking.

Disadvantages:

  • Time complexity O(n^2), the operation speed is very slow, when the number of array elements is large, the time growth is amazing.

Bucket sort

The principle of

Bucket sort as the name implies, is to prepare some “buckets”, and then to sort the array values into the corresponding “bucket”, all elements into the “bucket”, and then expand the “bucket” to get the sorted array. For example, if we need to sort the current array [8, 3, 5, 9, 2, 3, 0, 8], we can prepare an array of length 10, each value is 0, we start to facilitate the need to sort the array, when we meet 8, we newList[8] 0, increment 1, change 1; Then for the next 3, we add the 0 in newList[3] to 1… After processing all the elements, print the newList convenience to get the sorted array. Of course, this is just a simple introduction to bucket sorting. Real bucket sorting is more complicated than this.

Code implementation

const list = [8.3.5.9.2.3.0.8]; // Array to be sorted

/** * params {number[]} list * return {number[]} */
function sort(list) {
  const newList = Array.from({length: 10}).fill(0); // Create an array [0, 0... 0] of length 10
  list.forEach(el= > newList[el] += 1); // Record the array elements on newList
  return newList.reduce((pre, el, index) = > { // Expand the array
    for(let i = el; i; i--) {
      pre.push(index)
    }
    returnpre; }}, [])Copy the code

Pros and cons

Advantages:

  • The time complexity is only O(m+ N), and the calculation efficiency is high

Disadvantages:

  • Space consumption is relatively large

  • You need to know the maximum and the minimum in advance

Bubble sort

The principle of

Bubble sort let me explain how it works, and you’ll see why it’s called bubble sort. There is an array [8, 3, 5, 9, 2, 3, 0, 8] that needs to be sorted from smallest to largest. Do we just put the small ones on the left and the big ones on the right? Apparently. Compare the first 8 with the second digit 3, 8 is greater than 3, so let’s move 8 to the right, change the position of 8 and 3, the array is [3, 8, 5, 9, 2, 3, 0, 8], continue to compare the second digit 8 with the third digit 5, 8 is greater than 5, The array after replacement is [3, 5, 8, 9, 2, 3, 0, 8]. Repeat the operation. If you encounter the same array or the current value is less than the last one, you do not need to change it. So if you look at the path of the eight, does it look like a bubble is coming up, so this sort method is called bubble sort.

Code implementation

/** * params {number[]} list * return {number[]} */
function sort(list) {
  list = [...list];
  let length = list.length;
  while(length--) {
    for(let i = 0; i < length; i++) {
      const current = list[i];
      const next = list[i + 1];
      if(current > next) {
        [list[i], list[i + 1]] = [next, current]; }}}return list;
}
Copy the code

Pros and cons

Advantages:

  • No merit, I don’t know. Welcome.

Disadvantages:

  • Time complexity O(n^2), slow calculation.

Quick sort

The central idea is to use binary fast sort, can quickly complete the sorting task, is also a sorting way I recommend.

The principle of

The advantage of quicksort is that it’s fast. Why is it fast? Let me show you how quicksort works. Select a reference value, generally select a value of the array, traverse the number group, large put on the right, small put on the left, the same large put in the middle (ha ha ha ha 😀), the use of recursive repetition of the large array and small array split, finally come to the sorted array.

Code implementation

function quickSort(arr) {
  if(arr.length < 2) {
    return arr;
  } else {
    const pivot = arr[0]; / / value
    const pivotArr = []; // Put the same size in the middle
    const lowArr= []; // Put the small one on the left
    const hightArr = []; // Put the big one on the right
    arr.forEach(current= > {
      if(current === pivot) pivotArr.push(current);
      else if(current > pivot) hightArr.push(current);
      else lowArr.push(current);
    })
    returnquickSort(lowArr).concat(pivotArr).concat(quickSort(hightArr)); }}Copy the code

Pros and cons

Advantages:

  • Fast, order n log n.

Disadvantages:

  • Thanks @cringKong for the Pointers. The average time complexity of quicksort is O(n * log n), but the worst case complexity is O(n ^ 2), such as the ordered array [1, 2, 3, 4, 5]. Quicksort is not as stable as merge sort.
  • I didn’t realize you guys were available for guidance. O O (studying studying) thank you