Quick sort

introduce

The implementation of quicksort is mainly divided into two kinds, one is recursive implementation, one is cyclic nesting implementation, the main characteristics of the use of recursive implementation is simple, but will consume a lot of memory space, and the use of cyclic nesting implementation is not, but the idea is more complex. Quicksort *

Time complexity

On average, it’s order nlogn, and in the worst case, it’s order n^2^, which is actually less than order nlogn in most cases.

Spatial complexity

O(logn) (Recursive call consumption)

The stability of

It’s unstable, because when you sort, you swap places.

implementation

The recursive implementation

/** * @param {Array} Array * @returns {Array} */
 function quickSort1(array) {
	/** * returns the element */ when the array is split to a single element
	if (array.length < 2) {
		return array
	}
	const target = array[0],
          left = [],
          right = []
    
    for (let i = 1; i < array.length; i++) {
	    if (array[i] < target) {
			left.push(array[i])
	    } else {
	        right.push(array[i])
	    }
  	}
  	/** * Returns the array by subdividing the array until it is divided into each element. * This ensures that the array is ordered at the top of the call stack until it returns to the end of the entire array. * /
	return quickSort1(left).concat([target], quickSort1(right))
 }
Copy the code

Cycle to achieve

/** * @param {Array} Array Array * @param {Number} start Start index value * @param {Number} end End index value * @returns {Array} */
 function quickSort2(array, start, end) {
    if (end - start < 1) {
    	return
    }

    const target = array[start]
    let l = start,
        r = end
	  /** ** l is the left-most index value, r is the right-most index value, when l < r loop */
    while (l < r) {
      Array [r] = array[l]; /** * select * from array[l]; Because the target value is the same as array[l] on the first * execution, there is no need to worry about losing the original value on the first array[L] assignment. * /
    	while (l < r && array[r] >= target) {
      		r--
    	}
    	array[l] = array[r]
      /** * Select * from array[r], select * from array[r], select * from array[r], select * from array[r], select * from array[r] Because the array[r] at this point has already assigned the value to the current array[L] in the code above *, there is no need to worry too much. * /
        while (l < r && array[l] < target) {
      		l++
        }
    	array[r] = array[l]
  	}
    /** * if r===l, this round is completed, and only the target value is incorrectly assigned
  	array[l] = target
  	/** * will do the above through the index partitioned array */
  	quickSort2(array, start, l - 1)
  	quickSort2(array, l + 1, end)

  	return array
}
Copy the code

conclusion

Recursive implementation of quicksort is relatively simple, when using a loop to achieve quicksort, mainly in the loop to carry out the current operation is which index value, it is clear at a glance.