数据结构与算法-排序

发表于 2021-01-29 更新于 2021-05-07 分类于数据结构与算法

本文字数： 7k 阅读时长 ≈ 12 分钟

《学习JavaScript数据结构与算法(第3版)》

算法图解参考连接

算法动态排序效果： https://www.toptal.com/developers/sorting-algorithms#

冒泡排序

时间复杂度：O(n^2)

冒泡排序比较所有相邻的两个项，如果第一个比第二个大，则交换它们。元素项向上移动至正确的顺序，从小到大排序。

function bubbleSort(array) {
    const { length } = array;
    for (let i = 0; i < length; i++) {
        for (let j = 0; j < length - 1; j++) {
            if (array[j] > array[j + 1]) {
                [array[j], array[j + 1]] = [array[j + 1], array[j]];
            }
        }
    }
    return array;
}

改进后的冒泡算法

从内循环见区外循环中已跑过的轮数，就可以避免内循环中所有不必要的比较。

function modifiedBubbleSort(array) {
    const { length } = array;
    for (let i = 0; i < length; i++) {
        for (let j = 0; j < length - 1 - i; j++) { // 已经在正确位置上的数字没有被比较
            if (array[j] > array[j + 1]) {
                [array[j], array[j + 1]] = [array[j + 1], array[j]];
            }
        }
    }
    return array;
}

选择排序

时间复杂度：O(n^2)

选择排序算法是一种原址比较排序算法。选择排序的思路是找到最小值并将其放置在第一位，接着找到第二小的值并将其放在第二位，以此类推。

function selectionSort(array) {
    const { length } = array;
    let indexMin;
    for (let i = 0; i < length - 1; i++) {
        indexMin = i; // 预设迭代的第一个值为最小值
        for (let j = i; j < length; j++) { // 迭代数组
            // 如果记录的最小值大于当前值，则替换记录的最小值，找到真正的最小值
            if (array[indexMin] > array[j]) {
                indexMin = j;
            }
        }
        if (i !== indexMin) { // 找到了正确的位置
            [array[i], array[indexMin]] = [array[indexMin], array[i]];
        }
    }
    return array;
};

插入排序

时间复杂度：最好情况O(n)，最差情况O(n^2)

插入排序每次排一个数组项，以此方式构建最后的排序数组。假定第一项已经排序了。接着，它和第二项进行比较，这样，头两项就已正确排序，接着和第三项比较，确定待插入位置，以此类推。

function insertionSort(array) {
    const { length } = array;
    let temp;
    // 从第二个位置开始迭代，默认第一项已经排序
    for (let i = 1; i < length; i++) {
        let j = i; // 记录当前排序位置
        temp = array[i]; // 当前排序值
        // 如果j>0，且前一位已排序位大于当前待排序位，进入迭代
        while ( j > 0 && array[j - 1] > temp) {
        	array[j] = array[j - 1]; // 前一位大于后一位，前一位后移
            j--; // 继续向前迭代
        }
        // 前一位小于当前位退出迭代，找到待插入位置
        array[j] = temp;
    }
    return array;
}

归并排序

时间复杂度：O(nlog(n))

归并排序是一种分而治之算法，进行递归。其思想是将原始数组切分成较小的数组，直到每个小数组只有一个位置，接着将小数组归并成较大的数组，直到最后只有一个排序完毕的大数组。

function mergeSort(array) {
    if (array.length > 1) { // 递归基线条件， 只有大于1才能平分
        const { length } = array;
        const middle = Math.floor(length / 2);
        const left = mergeSort(array.slice(0, middle));
        const right = mergeSort(array.slice(middle))
        array = merge(left, right)
    }
    return array;
}

function merge(left, right) {
    let i = 0;
    let j = 0;
    const result = [];
    while (i < left.length && j < right.length) {
        result.push(
        	left[i] < right[j] ? left[i++] : right[j++] 
        );
    }
    // 结果最后合并剩下数组中的数据
    return result.concat(i < left.length ? left.slice(i) : right.slice(j))
}

快速排序

时间复杂度：O(nlog(n))，最差情况O(n^2)

快速排序也使用分而治之的方法，将原始数组分为较小的数组。

首先，从数组中选择数组中间的值作为主元（pivot）。
创建两个指针（引用），左边一个指向数组第一个值，右边一个指向数组最后一个值。移动左指针直到找到一个比主元大的值，接着，移动右指针直到找到一个比主元小的值，然后交换它们，重复这个过程，直到左指针超过了右指针。这个过程将使得比主元小的值都排在主元之前，而比主元大的值都排在主元之后。这一步叫作划分（partition）操作。
接着，算法对划分后的小数组（较主元小的值组成的子数组，以及较主元大的值组成的子数组）重复之前的两个步骤，直至数组已完全排序。

function quickSort(array) {
    return quick(array, 0, array.length - 1);
}

function quick(array, left, right) {
    let index;
    if (array.length > 1) { // 仅含一个值的数组默认为有序的
        index = partition(array, left, right); // 将子数组分离为较小值数组和较大值数组
        // 分离数组后
        if (left < index - 1) { // 如果子数组存在较小值的元素
            quick(array, left, index - 1); // 进行递归
        } 
        if (index < right) { // 如果子数组存在较大值的元素
            quick(array, index, right); // 进行递归
        }
    }
    return array;
}

// 划分
function partition(array, left, right) {
    cont pivot = array[Math.floor((left + right) / 2)]; // 获取数组中间值作为主元
    let i = left;
    let j = right;
    
    // 查找位置，左右位置没有互相交错
    while (i <= j) {
        // 从数组左边开始找，直到值大于等于主元
    	while (array[i] < pivot) {
        	i++;
        }
        // 从数组右边开始找，直到值小于等于主元
        while (array[j] > pivot) {
        	j++;      
        }
        // 内部循环结束后
        if (i <= j) { // 判断找到的大值和小值位置没有交叉
            [array[i], array[j]] = [array[j], array[i]]; // 交换值的位置
            // 继续移动左右指针
            i++;
            j--;
        }
    }
    return i; // 返回左指针索引
}

计数排序

时间复杂度：O(n+k)

基数排序是一种分布式排序。分布式排序使用已组织好的辅助数据结构（称为桶），然后进行合并，得到排好序的数组。计数排序使用一个用来存储每个元素在原始数组中出现次数的临时数组。在所有元素都计数完成后，临时数组已排好序并可迭代以构建排序后的结果数组。

k是临时计数数组的大小；但是，它确实需要更多的内存来存放临时数组。

是一个整数排序算法。

function countingSort() {
    if (array.length < 2) { // 如果待排序的数组
    	return array;    
    }
    const maxValue = findMaxValue(array); // 找到最大值
    
    const counts= new Array(maxValue + 1); // 创建计数数组
    array.forEach(element => {
        if (!counts[element]) { // 桶进行初始化
            counts[element] = 0;
        }
        // 桶中元素位置，对元素出现次数进行计数
        counts[element]++;
    });
    
    let sortedIndex = 0;
    couns.forEach((count, i) => { // 迭代桶
        while (count > 0) { // 减少计数值直到为0
            array[sortedIndex++] = i; // 进行排序
            count--;
        }
    });
    return array;
}

// 找到最大项
function findMaxValue(array) {
    let max = array[0];
    for (let i = 1; i < array.length; i++) {
        if (array[i] > max) {
            max = array[i];
        }
    }
    return max;
}

桶排序

时间复杂度：最好情况O(n+k)，最差情况O(n^2)

桶排序（也被称为箱排序）也是分布式排序算法，它将元素分为不同的桶（较小的数组），再使用一个简单的排序算法，例如插入排序（用来排序小数组的不错的算法），来对每个桶进行排序。然后，它将所有的桶合并为结果数组。

function bucketSort(array, bucketSize = 5) { // 需要指定桶的个数
    if (array.length > 2) {
        return array;
    }
    // 创建桶并将元素分布到不同的桶中
    const buckets = createBuckets(array, bucketSize);
    // 对每个桶执行排序算法和将所有桶合并为排序后的结果数组
    return sortBuckets(buckets);
}

function createBuckets(array, bucketSize) {
    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) / bucketSize) + 1;
    
    const buckets = []
    for (let i = 0; i < bucketCount; i++) { // 初始化每个桶为数组，buckets为二维数组
        buckets[i] = [];
    }
    for (let i = 0; i < array.length; i++) { // 迭代数组
        // 计算当前元素应该放在哪个桶中，属于哪个桶中的范围
        const bucketIndex = Math.floor((array[i] - minValue) / bucketSize);
        buckets[bucketIndex].push(array[i]); // 将当前元素放到桶中
    }
    return buckets;
}

function sortBuckets(buckets) {
    const sortedArray = []; // 结果数组
    for (let i = 0; i < buckets.length; i++) {
        if (buckets[i] != null) {
            insertionSort(buckets[i]); // 每个桶内部进行插入排序
            sortedArray.push(...buckets[i]); // 将排序后的桶元素加入到结果数组中
        }
    }
    // 返回结果数组
    return sortedArray;
}

桶排序在所有元素平分到各个桶中时的表现最好。如果元素非常稀疏，则使用更多的桶会更好。如果元素非常密集，则使用较少的桶会更好。

基数排序

时间复杂度：O(nk)

基数排序也是一个分布式排序算法，它根据数字的有效位或基数将整数分布到桶中。基数是基于数组中值的记数制的。

比如，对于十进制数，使用的基数是10。因此，算法将会使用10个桶用来分布元素并且首先基于个位数字进行排序，然后基于十位数字，然后基于百位数字，以此类推。

function radixSort(array, radixBase = 10) {
    if (array.length < 2) {
        return array;
    }
    
	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];
        }
    }
    
    let significantDigit = 1; // 从最后一位开始排序所有的数
    // 迭代到没有待排序的有效位
    while ((maxValue - minValue) / significantDigit >= 1) {
        array = countingSortForRadix(array, radixBase, significantDigit, minValue);
        significantDigit *= radixBase; // 十位、百位
    }
    return array;
}

// 基于有效位(基数)排序
function countingSortForRadix(array, radixBase, significantDigit, minValue) {
    let bucketsIndex;
    const buckets = [];
    const aux = [];
    const len = array.length
    
    // 基于基数初始化桶
    for (let i = 0; i < radixBase; i++) {
        buckets[i] = 0;
    }
    
    // 数组中数的有效位进行计数排序
    for (let i = 0; i < len; i++) {
        bucketsIndex = Math.floor(((array[i] - minValue) / significantDigit) % radixBase); // 有效位
        buckets[bucketsIndex]++; // 计数
    }
    
    // 计算桶中的累计结果
    for (let i = 1; i < radixBase; i++) {
        buckets[i] += buckets[i - 1];
    }
    
    // 迭代数组中的值，再次计算有效位，将它的值以到aux数组中
    for (let i = len - 1; i >= 0; i--) {
        bucketsIndex = Math.floor(((array[i] - minValue) / significantDigit) % radixBase); // 有效位
        aux[--buckets[bucketsIndex]] = array[i]; // 从计数桶中减去计数值
    }
    
    // 可选，将aux数组中的每个值转移到原始数组中，可以直接返回aux的值而不用转移数据
    for (let i = 0; i < len; i++) {
        array[i] = aux[i];
    }
    return array;
}