Quick sort

  1. Start by taking a number from the sequence as the base number
  2. Partitioning, you put everything to the right of this number, everything less than or equal to this number to the left of this number
  3. Repeat the second step for the left and right intervals until each interval has only one number
// Initial version quicksort
function quick_sort_v1(arr, l, r) {
    if (l >= r) return
    // Take the base value first in the current interval
    let x = l, y = r, base = arr[l]
    while (x < y) {
        // Find the position on the right less than the base value, put the value in the position of x, then x++
        while (x < y && arr[y] >= base) y--
        if (x < y) arr[x++] = arr[y]
        // Put the value in position y, and then y--
        while (x < y && arr[x] <= base) x++
        if (x < y) arr[y--] = arr[x]
    }
    // The last x and y positions are the reference positions
    arr[x] = base
    quick_sort_v1(arr, l, x - 1)
    quick_sort_v1(arr, x + 1, r)
}
Copy the code
// Single side recursive fast sorting
//
function quick_sort_v2(arr, l, r) {
    while (l < r) {
        if (l >= r) return
        let x = l, y = r, base = arr[l]
        while (x < y) {
            while (x < y && arr[y] >= base) y--
            if (x < y) arr[x++] = arr[y]
            while (x < y && arr[x] <= base) x++
            if (x < y) arr[y--] = arr[x]
        }
        arr[y] = base
        quick_sort_v2(arr, x + 1, r)
        r = x - 1}}Copy the code
// Insert sort optimized quicksort
// Set an interval size of 16, use quicksort for ranges greater than 16, use insert sort for ranges less than 16
const threshold = 16
// Take the second largest of the three numbers
function median(a, b, c) {
    if (a > b) [a, b] = [b, a]
    if (a > c) [a, c] = [c, a]
    if (b > c) [b, c] = [c, b]
    return b
}
function __quick_sort_v3(arr, l, r) {
    // Execute only when less than the preset range (16)
    while (r - l > threshold) {
        // The reference value is the second largest of the three values in the current range
        let x = l, y = r, base = median(arr[l], arr[(l + r) / 2], arr[r])
        do {
            // Locate the subscripts of the left part greater than the reference value and the right part less than the reference value, swap values
            while (arr[x] < base) { x++ }
            while (arr[y] > base) { y-- }
            if (x <= y) {
                [arr[x], arr[y]] = [arr[y], arr[x]]
                x++
                y--
            }
        } while (x <= y)
        __quick_sort_v3(arr, x, r)
        r = y
    }
}
// Insert sort, do the end, suitable for sorting between cells
function final_insert_sort(arr, l, r) {
    let ind = l
    for (let i = l + 1; i <= r; i++) {
        if (arr[i] < arr[ind]) {
            ind = i
        }
    }
    while (ind > l) {
        [arr[ind], arr[ind - 1]] = [arr[ind - 1], arr[ind]]
        --ind
    }
    for (let i = l + 2; i <= r; i++) {
        let j = i
        while (arr[j] < arr[j - 1]) {
            [arr[j], arr[j - 1]] = [arr[j - 1], arr[j]]
            j--
        }
    }
}
function quick_sort_v3(arr, l, r) {
    __quick_sort_v3(arr, l, r)
    final_insert_sort(arr, l, r)
}
Copy the code

LeetCode liver problem

    1. Sort an array
function median(a, b, c) {
    if (a > b) [a, b] = [b, a]
    if (a > c) [a, c] = [c, a]
    if (b > c) [b, c] = [c, b]
    return b
}
function quick_sort_v2(arr, l, r) {
    while (l < r) {
        if (l >= r) return
        let x = l, y = r, base = arr[l]
        while (x < y) {
            while (x < y && arr[y] >= base) y--
            if (x < y) arr[x++] = arr[y]
            while (x < y && arr[x] <= base) x++
            if (x < y) arr[y--] = arr[x]
        }
        arr[y] = base
        quick_sort_v2(arr, x + 1, r)
        r = x - 1}}var sortArray = function(nums) {
    quick_sort_v2(nums, 0, nums.length-1)
    return nums
};
Copy the code
    1. Sorting list
Ret1 = ret1; ret2 = ret2; ret1 = ret2
var sortList = function(head) {
    if(! head)return head
    let p = head, q, min = p.val, max = p.val, base = 0, ret1 = null, ret2 = null
    while(p) {
        min = Math.min(min, p.val)
        max = Math.max(max, p.val)
        p = p.next
    }
    if (min == max) return head
    base = (max + min) / 2
    p = head
    while(p) {
        q = p.next
        if (p.val <= base) {
            p.next = ret1
            ret1 = p
        } else {
            p.next = ret2
            ret2 = p
        }
        p = q
    }
    ret1 = sortList(ret1)
    ret2 = sortList(ret2)
    p = ret1
    while(p.next) p = p.next
    p.next = ret2
    return ret1
};
Copy the code
  1. 21. Reorder the array so that the odd number precedes the even number
// Define two Pointers, I to the left odd, j to the right even, and then switch
var exchange = function(nums) {
    let i = 0, j = nums.length - 1
    while(i < j) {
        while(nums[i] % 2= =1 && i < j) i++
        while(nums[j] % 2= =0 && i < j) j--
        if (i == j) break
        [nums[i], nums[j]] = [nums[j], nums[i]]
        i++
        j--
    }
    return nums
};
Copy the code
    1. Color classification
// Set l to red 0, I to white 1, r to blue 2
var sortColors = function(nums) {
    if (nums.length <= 1) return nums
    let l = -1, r = nums.length,  i = 0, base = 1
    while(i < r) {
        if (nums[i] == base) {
            i++
        } else if (nums[i] < base) {
            l++
            [nums[i], nums[l]] = [nums[l], nums[i]]
            i++
        } else {
            r--
            [nums[i], nums[r]] = [nums[r], nums[i]]
        }
    }
};
Copy the code
  1. Interview question 17.14. Minimum K number
// Put k digits into the result set (can be optimized to the left range of k digits left)
function median(a, b, c) {
    if (a > b) [a, b] = [b, a]
    if (a > c) [a, c] = [c, a]
    if (b > c) [b, c] = [c, b]
    return b
}
function quick_sort_v2(arr, l, r) {
    while (l < r) {
        if (l >= r) return
        let x = l, y = r, base = arr[l]
        while (x < y) {
            while (x < y && arr[y] >= base) y--
            if (x < y) arr[x++] = arr[y]
            while (x < y && arr[x] <= base) x++
            if (x < y) arr[y--] = arr[x]
        }
        arr[y] = base
        quick_sort_v2(arr, x + 1, r)
        r = x - 1}}var smallestK = function(arr, k) {
    let ans = []
    if (k == 0) return ans
    quick_sort_v2(arr, 0, arr.length - 1)
    while(k) ans.push(arr[--k])
    return ans
};
Copy the code
    1. Different binary search tree II
// Arrange and combine all the results
var dfs = function(l, r) {
    let ans = []
    if (l > r) {
        ans.push(null)
        return ans
    }
    for (let i = l; i <= r; i++) {
        let left_tree = dfs(l, i - 1)
        let right_tree = dfs(i + 1, r)
        for (let leftItem of left_tree){
            for(let rightItem of right_tree) {
                let treeNode = new TreeNode(i, leftItem, rightItem)
                ans.push(treeNode)
            }
        }
    }
    return ans
}
var generateTrees = function(n) {
    if(n == 0) return []
    return dfs(1, n)
};
Copy the code
    1. String decoding
// Iterate over strings by type concatenation
var decodeString = function(s) {
    let numArr = [], strArr = [], num = 0, ans = ' '
    for(let item of s) {
        if (item >= '0' && item <= '9') {
            num = num * 10 + parseInt(item)
        } else if (item == '[') {
            strArr.push(ans)
            ans = ' '
            numArr.push(num)
            num = 0
        } else if (item == '] ') {
            ans = strArr.pop() + ans.repeat(numArr.pop())
        } else {
            ans += item
        }
    }
    return ans
};
Copy the code