algorithm

One number is randomly selected as the base value, and the rest are divided by size

Then repeat the above algorithm for both sides

Time complexity


O ( n l o g n ) < = O < = O ( n 2 ) O(nlogn) <= O <=O(n^2)

Note: If the selected base value is always the minimum value in the unsorted array, the time complexity will become the maximum O(n2)O(n^2)O(n2). At this time, we can take a random index value at the base value of each round, instead of a fixed index. In this way, we can break the previous sorting and achieve the balance of the unsorted parts on the left and right sides as far as possible

js

const input = [4.2.15.2.5.6.21.67.2.3]
const sort = (arr = []) = > {
    if (arr.length <= 1) return arr
    const middle = Math.floor(arr.length / 2)
    const base = arr[middle];
    const left = [];
    const right = [];
    for (let i = 1; i <= middle; i++) {
      const leftIndex = middle - i;
      if (leftIndex >= 0) {
        const val = arr[leftIndex];
        if (val > base) {
          right.push(val)
        } else {
          left.push(val)
        }
      }
      const rightIndex = middle + i;
      if (rightIndex < arr.length) {
        const val = arr[rightIndex];
        if (val > base) {
          right.push(val)
        } else {
          left.push(val)
        }
      }
    }
    
    
    return sort(left).concat([base]).concat(sort(right))
}
console.log(sort(input))
Copy the code