JavaScript数据结构与算法-排序全详解

冒泡排序

原理

冒泡排序比较所有相邻的两个项，如果第一个比第二个大，则交换他们。

代码一

/**
 * 冒泡排序(升序)
 * @param {*} array 
 * @returns 
 */
function bubbleSort(array) {
    const { length } = array
    for (let i = 0; i < length; i++) {
        for (let j = 0; j < length; j++) {
            if (array[j] > array[j + 1]) {
                let temp = array[j + 1]
                array[j + 1] = array[j]
                array[j] = temp
            }
        }
    }
    return array
}

优化冒泡排序

代码二

选择排序

原理

选择排序大致的思路是找到数据结构中的最小值并将其放置到第一位，接着找到第二小的值并将其放在第二位。

TS代码

function selectionSort(array: Array<number>) {
    const { length } = array
    for (let i = 0; i < length; i++) {
        let IndexMin = i
        for (let j = i; j < length; j++) {
            if (array[IndexMin] > array[j]) {
                console.log(j);
                IndexMin = j
            }
        }
        if (i != IndexMin) {
            let temp = array[IndexMin]
            array[IndexMin] = array[i]
            array[i] = temp

        }
    }
    return array
}

插入排序

JS代码

function insertionSort(arr) {
    for (var index = 1; index < arr.length; index++) {
        var end = index;
        var element = arr[index];
        // 比当前值大的都向前移位（前一位覆盖当前位），直到不符合要求
        while (end > 0 && element < arr[end - 1]) {
            arr[end] = arr[end - 1];
            end--;
        }
        // 把element 赋值end位
        arr[end] = element;
    }
}

排序小型数组时，此算法比选择排序和冒泡排序性能要好

归并排序

快速排序

原理

1、选定一个基准数，要使得基数的左边的数字全部小于它，右边的数字全部大于它。
2、　（升序）　分别设i和j从左右开始寻找，从左边找到第一个比基数大的数，从右边找到第一个比基数小的数，然后交换这两个数。当i和j相遇时，交换基数和i位置上的值
3、再以同样的方式处理两边的数组。

JS代码

function QuickSort(arr, s, e) {
    if(s>=e)return
    let basicValue = arr[s]  // 基准值
    let swapIndex = s + 1   // 交换初始位
    for (let i = swapIndex; i <= e; i++) {
        if (arr[i] < basicValue) {
            // 交换
            let temp = arr[i]
            arr[i] = arr[swapIndex]
            arr[swapIndex] = temp
            swapIndex++
        }
    }
    // 交换
    let temp = arr[--swapIndex]
    arr[swapIndex] = arr[s]
    arr[s] = temp
    QuickSort(arr, s,swapIndex-1)
    QuickSort(arr,swapIndex+1,e)
}

计数排序

原理

计数式排序式是一个分布式排序
计数排序使用一个用来存储每个元素在原始数组中出现次数的临时数组。在所有元素都计完数之后
，临时数组已排好并迭代以构建排序后的数组

TS代码

/**
 * 计数排序
 */
function countingSort(array: Array<number>) {
    if (array.length < 2) return array
    const maxValue = findMaxValue(array)
    // 计数数组
    const counts = new Array(maxValue + 1).fill(0)
    array.forEach(item => {
        counts[item]++
    })

    let sortIdnex = 0
    counts.forEach((count, i) => {
        while (count > 0) {
            array[sortIdnex++] = i
            count--
        }
    })
    return array
}
/**
 * 找数组中的最大值
 * @param array 
 * @returns 
 */
function findMaxValue(array: Array<number>) {
    let max = array[0]
    for (let i = 0; i < array.length; i++) {
        if (array[i] > max) {
            max = array[i]
        }
    }
    return max
}

桶排序

原理

算法分为两部分
1、用于创建桶并将不同元素分到不同的桶中
2、对每个桶进行插入排序算法和将所有桶并为排序后的结果数组

TS代码

/**
 * 桶排序
 * @param array 
 * @param bucketSize 
 */
function createBuckets(array: Array<number>, bucketSize: number) {
    let minValue = array[0]
    let maxValue = array[0]
    for (let i = 1; i < array.length; i++) {
        if (array[i] < minValue) {
            minValue = array[i]
        } else if (array[i] > maxValue) {
            maxValue = array[i]
        }
    }
    // 已得到到数组的最小值和最大值
    const bucketCount = Math.floor((maxValue - minValue) / 2) + 1
    const buckets: Array<Array<number>> = []    // 创建桶
    for (let i = 0; i < bucketCount; i++) {
        buckets[i] = []
    }
    // 放入各自的桶中
    for (let i = 0; i < array.length; i++) {
        const buketIndex = Math.floor((array[i] - minValue) / bucketSize)
        buckets[buketIndex].push(array[i])
    }
    return buckets
}
/**
 * 排序每个桶并合并每个桶
 * @param buckets 
 * @returns 
 */
function sortBuckets(buckets: Array<Array<number>>) {
    const sortedArray = []
    for (let i = 0; i < buckets.length; i++) {
        if (buckets[i] != null) {
            // 插入排序对每个桶进行（这个是上面的插入排序insertionSort）排序
            insertionSort(buckets[i]);
            // 合并桶
            sortedArray.push(buckets)
        }
    }
    return sortedArray
}

基数排序

原理

基数排序也是一个分布式算法，根据数组的有效位或基数将整数分不到桶中。
对于10进制数，使用的基数为10。因此，算法将会使用10个桶用来分布元素并且基于个位数字进行排序、然后十位、然后百位以此类推。

TS代码

function radixSort(arr: Array<number>) {
    let length = arr.length
    let counter: Array<Array<number>> = []
    let mod = 10
    let dev = 1
    if (length < 1) {
        return arr
    }
    // 获取数组中最大位数
    let maxDigit = String(Math.max(...arr)).length
    for (let i = 0; i < maxDigit; i++, dev *= 10) {
        for (let j = 0; j < arr.length; j++) {
            // 获取相应位置上的数
            var bucket = (arr[j] / dev) % mod;

            if (counter[bucket] == null) {
                counter[bucket] = [];
            }
            counter[bucket].push(arr[j]);
        }
        console.log(counter);
        
        var pos = 0;
        console.log(counter.length);
        
        for (let k = 0; k < counter.length; k++) {
            var value = null;
            if (counter[k]) {
                while ((value = counter[k].shift()) != null) {
                    arr[pos++] = value;
                }
            }
        }    
    }
    return arr;
}

堆排序

原理

1、用数组创建一个最大堆用作源数据
2、在创建最大堆后，最大值会存储在堆的第一个位置。我们需要把这个最大值与最大堆的最后一个节点进行交换，然后将堆的length-1
3、根节点下移，重复步骤2 直到结束

TS代码

/**
* 构建大顶堆
*/
function Heap(arr: Array<number>, length: number) {
    // 构建大顶堆
    for (let i = arr.length - 1; i >= 0; i--) {
        swap(arr, i)
    }
    // 递归交换
    function swap(arr: Array<number>, i: number) {
        let left = 2 * i + 1
        let right = 2 * i + 2
        let max: number = i
        if (left < length && arr[left] > arr[max]) {
            max = left
        }
        if (right < length && arr[right] > arr[max]) {
            max = right
        }
        if (max != i) {
            let temp = arr[max]
            arr[max] = arr[i]
            arr[i] = temp
            swap(arr, max)
        }
    }
}
function sort(arr: Array<number>) {
    Heap(arr, arr.length)
    let length = arr.length - 1
    while (length >= 0) {
        let temp = arr[0]
        arr[0] = arr[length]
        arr[length] = temp
        length--
        Heap(arr, length)
    }
    return arr
}