Roar background is a classmate interview jingdong was asked to say a variety of sorting, a think about yourself is back so long, and then can not remember, there is no systematic sorting;

Evaluation Terms:

  1. Space-time complexity; Execution time and memory space required for running;
  2. Stable: In sorting, if a= B, stable means that the relative positions of the two indices do not change; Remember (quicksort and heap, selection sort is unstable!)

There’s a picture that I’ve used for a long time that I can’t remember after I’ve seen it a million times

General sorts are divided into insert (direct insert, Hill), select (simple select, heap), swap (bubble, quicksort), merge, and radix

Insert sort:

Direct insertion sort

Easy to understand ah, playing poker sort ha ha; See code animation see reference 1

function insertSort(arr){
    for(let i=0; i<arr.length; i++){var key = arr[i];
        var j = i - 1;
        while(j>=0 && arr[j]>key){
            arr[j+1] = arr[j];
            j--;
        }
        arr[j+1]=key
    }
    return arr
}
Copy the code

If improved, and previously sorted insert process can be binary; Time complexity: average (n2) best (n) worst (N2) stable

Hill:

The algorithm that can break n2 time complexity improves the insertion process by setting interval sequence. For example: the first time 1 to 5, 2 to 6, 3 to 7; And then when you’re done you cut the increment in half; To continue; Don’t take an examination of commonly

Code the wip:

For ordered sequences, swap is used when inserting
function shellSort(arr){
    // Gradually reduce the step size to 1
    for(let shellWidth = arr.length/2; shellWidth>0; shellWidth/2) {// Group arrays according to step size, and swap sort using insertion sort
        // Insert sort from the set of increments
        for(let atom =shellWidth; atom<arr.length; atom++ ){
            // Atom-shellWidth represents the element next to the element in the same group. For elements in the same group, insert sort
            while(atom-shellWidth>0&&arr[atom-shellWidth]>arr[atom]){ swap(arr,atom-shellWidth,atom); atom=atom-shellWidth; }}}}Copy the code

Selection sort:

Simple selection sort

Find the smallest element in the array and place it to the left of the array; It takes n minus one sort

function chooseSort(arr){
    for(let i=0; i<arr.length; i++){
        minIndex = i;
        for(let j=i+1; j<arr.length; j++){
            if(arr[j]<arr[minIndex]){
                minIndex = j
            }
        }
        [arr[i],arr[minIndex]] = [arr[minIndex],arr[i]] 
    }
    console.log(arr)
}
Copy the code

Time complexity, average best worst n2, unstable

Heap sort

The big top heap is when the root node is larger than the left and right child nodes, so first build a big top heap of the array, and then swap the root node with the last one, until the maximum value is at the end; And then n-1 continues to construct; And so on;

First leaf sub: math.floor (arr.length/ 2-1)

Reference: www.jianshu.com/p/90bf2dcd6…

Nlogn unstable

Swap sort:

Bubble:

The schematic diagram: cuijiahua.com/blog/2017/1…

contrast

function bubbleSort(arr) {
    var len = arr.length;
    for (var i = 0; i < len; 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 code

The worst and average best times are when inplace is used. It’s stable sort;

This can be improved with a flag; If data is not exchanged during a sort, all data is in order. You can end the sort immediately to avoid unnecessary comparison.

Improved code:

function bubbleSort(arr){
    for(let i = 0; i < arr.length; i++) {
    let flag = true
    for(let j = 0; j < arr.length - i - 1; j++) {
        if(arr[j] > arr[j+1]) {
          flag = false
          let temp = arr[j]
          arr[j] = arr[j+1]
          arr[j+1] = temp
        }
      }
      // The meaning of this flag is: if 'a loop' does not swap elements, it means that the sorting is complete
      if(flag)break;
    }
    return arr
  }
Copy the code

Fast row:

Nlogn! Unstable! It has nlogn space complexity

  1. Select the base element
  2. Elements smaller than the base element go to the left, and elements larger go to the right
  3. Repeat step one and two in the left and right subarrays until there is only one element left
  4. Merge arrays step by step up

Optimization: opened two memory, not too line oh;

  function quickSort(arr, left, right) {          // Left and right represent the interval subscripts of "new array" after partition. Since there is no new array, we need left/right to confirm the position of the new array
    if (left < right) {
        let pos = left - 1                      //pos is the "replaced position", the first trip is -1
        for(let i = left; i <= right; i++) {    // Loop through the array, replacing the elements
            let pivot = arr[right]              // Select the last bit of the array as the base number,
            if(arr[i] <= pivot) {               // if less than or equal to the base number, pos++, and transpose elements, use less than or equal to instead of less than, in order to avoid the endless loop due to repeated data
                pos++
                let temp = arr[pos]
                arr[pos] = arr[i]
                arr[i] = temp
            }
        }
        // After the sorting is complete, the pos position is the base position, and the array is split by the pos position
        quickSort(arr, left, pos - 1)        
        quickSort(arr, pos + 1, right)
    }
    return arr      // The recursion terminates when the array contains only 1 or 0 elements (left>=right)
}
Copy the code

merge

Reference:

[1] Juejin. Cn/post / 684490… [2]Juejin. Cn/post / 684490…