algorithm

Insertion sort is an algorithm that sorts data from the left side of an array.

In the sorting process, the data on the left is successively classified as, and the data left on the right is unsorted.

The idea of insertion sort is to take a number from the unsorted region on the right and insert it into the appropriate position in the sorted region.

Time complexity


1 + 2 + . . . + ( n – 1 ) = O ( n 2 ) 1 + 2 +… +(n-1)=O(n^2)

When inserting values into the sorted region on the left, the comparison method is used from right to left, so that in the worst case (sorting the array from largest to smallest), the k-1 comparison operation will be performed on round K, so the time complexity is O(n2)O(n^2)O(n2).

In fact, this part can be optimized by using binary search to reduce the operands, and the time complexity of binary search is O(logn)O(logn)O(logn), so the optimized time complexity should be log1+log2+… + log (n – 1) = O (logn!) log1+log2+… +log(n-1)=O(logn!) log1+log2+… + log (n – 1) = O (logn!)

js

const input = [4.2.15.2.5.6.21.67.2.3]
const sort = (arr) = > {
    const result = [input[0]]
    for (let i = 1; i < arr.length; i++) {
        const now = arr[i]
        if (now >= result[result.length -1]) {
            result.push(now)
        } else if (now <= result[0]) {
            result.unshift(now)
        } else {
            for (let j = i-2; j >0; j--) {
                if (now >= result[j]) {
                    result.splice(j+1.0,now)
                    j=0}}}}return result
}
console.log(sort(input))
Copy the code