算法——排序

插入排序

思想： 从前往后依次处理未排好的元素，对于每个元素，我们将它与之前排好序的元素从后往前进行比较，找到对应的位置后插入

/**
 * @description insertion sort
 * 时间复杂度:O(n*2) 空间复杂度:O(1)
 */
class InsertionSort {
    origin: number[]
    result: number[]
    constructor(arr: number[]) {
        this.origin = arr
        this.result = this.sort([...arr])
    }
    sort (arr: number[]) {
        let cur: number = 0
        let j: number = 0
        for (let i = 1; i < arr.length; i++) {
            cur = arr[i] //当前排序的元素
            j = i - 1
            // 从后往前比较其之前的元素，然后交换位置
            while (j >= 0 && cur < arr[j]) {
                arr[j + 1] = arr[j]
                arr[j] = cur
                j--
            }
        }
        return arr
    }
}

快排

思想：选取一个目标元素，然后分为两个子数组，使其左边的数组每项均小于该元素，右边数组每项均大于该元素

/**
 * @description quick sort
 * 最大时间复杂度:O(n*2) 平均复杂度O(nlogn)
 * 空间复杂度:O(n), 平均空间复杂度：O(logn)
 */
class QuickSort {
    origin: number[]
    result: number[]
    constructor(arr: number[]) {
        this.origin = arr
        this.result = [...arr]
        this.sort(this.result, 0, arr.length - 1)
    }
    sort (arr: number[], left: number, right: number) {
        if (left >= right) {
            return
        }

        const pointIndex: number = this.partition(arr, left, right)
        this.sort(arr, left, pointIndex - 1)
        this.sort(arr, pointIndex + 1, right)
    }
    partition (arr: number[], left: number, right: number): number {
        const point = arr[right]
        let leftIndex = left
        let rightIndex = right - 1
        while (true) {
            while (leftIndex < right && arr[leftIndex] < point) {
                leftIndex++
            }
            while (rightIndex > left && arr[rightIndex] > point) {
                rightIndex--
            }
            if (rightIndex <= leftIndex) {
                break
            }
            this.swap(arr, leftIndex, rightIndex)
        }
        // 将point放入指定位置
        this.swap(arr, right, leftIndex)
        return leftIndex;
    }
    swap (arr: number[], i: number, j: number) {
        const tem = arr[i]
        arr[i] = arr[j]
        arr[j] = tem;
        // arr[i] = arr[i] + arr[j]
        // arr[j] = arr[i] - arr[j]
        // arr[i] = arr[i] - arr[j]
    }
}

归并排序

思想：将原数组递归操作分为两个小数组，然后将两两小数组排序后合并，最后得到一个排序好的大数组

/**
 * @description merge sort
 * 时间复杂度:O(nlogn) 空间复杂度:O(n)
 */
class MergeSort {
    origin: number[]
    result: number[]
    constructor(arr: number[]) {
        let left: number = 0
        let right: number = arr.length - 1
        this.origin = arr
        this.result = [...arr]
        this.sort(this.result, left, right)

    }
    sort (arr: number[], left: number, right: number): void {
        if (left >= right) {
            return
        }

        let mid: number = Math.floor((left + right) / 2)
        this.sort(arr, left, mid)
        this.sort(arr, mid + 1, right)
        this.merge(arr, left, mid, right)
    }
    /**
    *@description 将数组[left,mid][mid+1,right]合并
    */
    merge (arr: number[], left: number, mid: number, right: number) {
        let l = left
        let r = mid + 1
        for (let k = left; k <= right; k++) {
            if (l > mid) {
                // left数组溢出,将right剩余的元素归并arr
                arr[k] = this.origin[r++]
            } else if (r > right) {
                arr[k] = this.origin[l++]
            } else if (this.origin[l] > this.origin[r]) {
                // 将小元素赋值给arr
                arr[k] = this.origin[r++]
            } else {
                arr[k] = this.origin[l++]
            }
        }
    }
}

测试案例

const insetSortObject = new InsertionSort([5, 3, 6, 3, 8, 4, 24, 2,1])
const quickSortObject = new QuickSort([5, 3, 6, 3, 8, 4, 24, 2])
const mergeSortObject = new MergeSort([5, 3, 6, 3, 8, 4, 24, 2])

参考资料

B站：图灵星球TuringPlanet