JavaScript 十大排序算法详解

冒泡排序算法

冒泡排序是一种简单的排序算法,它的核心思想是将相邻的两个元素逐一比较,如果顺序不对就交换位置,直至整个序列变得有序。下面是冒泡排序的具体操作步骤:

  1. 比较相邻的两个元素。如果第一个元素比第二个元素大,就交换这两个元素;
  2. 对每一对相邻元素做同样的工作,从开始的第一对到结尾的最后一对;
  3. 针对所有的元素重复上述步骤,除了最后一个;
  4. 重复步骤 1~3,直至排序完成。
// 定义冒泡排序函数
function bubbleSort(arr) {
    // 获取数组长度
    let len = arr.length;

    // 循环遍历数组元素,每次比较相邻两个元素
    for (let i = 0; i < len - 1; i++) {
        // 每轮循环把最大的数放在最后面,因此内层循环次数逐步减少
        for (let j = 0; j < len - i - 1; j++) {
            // 如果前一个元素比后一个元素大,则交换两个元素位置
            if (arr[j] > arr[j + 1]) {
                let temp = arr[j]; // 用临时变量保存当前元素
                arr[j] = arr[j + 1]; // 把后一个元素赋值给前一个元素
                arr[j + 1] = temp; // 把当前元素赋值给后一个元素
            }
        }
    }

    // 返回已排序的数组
    return arr;
}

在上述代码中,我们使用了两个for循环来实现冒泡排序。外层循环控制排序的轮数,内层循环用于比较相邻元素并交换它们的位置。每一轮排序结束后,数组中最大的元素都会被放到数组的末尾,因此下一轮排序中就不再考虑该元素。

需要注意的是,在最坏情况下,即待排序序列为逆序排列时,冒泡排序的时间复杂度为 O(n2n^2)。但是,在实际应用中,由于它的实现简单,对于小规模数据的排序仍然是一个较为不错的选择。

选择排序算法

选择排序算法是一种简单但低效的排序算法,它的时间复杂度为 O(n2n^2)。该算法的基本思路如下:

  1. 在待排序数组中选出最小(亦或是最大)的一个元素,存放在数组的起始位置;
  2. 从剩余未排序的元素中继续寻找最小(亦或是最大)的元素,然后放到已排序序列的末尾;
  3. 重复第二步,直至所以元素排序完毕。
// 定义选择排序函数
function selectionSort(arr) {
    // 获取数组长度
    const len = arr.length;
    let minIndex; // 定义最小值的索引

    // 循环遍历数组元素,从第一个元素开始比较
    for (let i = 0; i < len - 1; i++) {
        minIndex = i; // 假设当前元素为最小值

        // 从下一个元素开始比较
        for (let j = i + 1; j < len; j++) {
            // 如果该元素比当前最小值还要小,则将其视为新的最小值
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }

        // 如果最小值的位置不是当前位置,则交换两个元素位置
        if (minIndex !== i) {
            [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
        }
    }

    // 返回已排序的数组
    return arr;
}

在上述代码中,首先定义了一个名为selectionSort的函数,它有一个参数arr,表示待排序的数组。函数中使用了两个嵌套的循环来实现选择排序。外层循环控制已排序部分的末尾位置,从第一个元素开始遍历到倒数第二个元素。假设当前已经排好序的区间是[0, i-1],那么 ii 就是未排序部分的起始位置。内层循环用来寻找未排序部分中最小的元素,并将其记录在minIndex变量中。从 i+1i+1 位置开始遍历到数组末尾,如果发现某个位置上的元素比minIndex位置上的元素还要小,则将该位置赋值给minIndex。当内层循环结束后,我们就可以得到未排序部分中最小的元素,将其与 ii 位置上的元素交换,即可将该元素归入到已排序部分的末尾。最后则返回排好序的数组。

[arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];

在上述代码中,我们使用了解构赋值对两个变量的值进行了交换。我们首先创建了一个包含两个元素的数组,其中第一个元素是arr[minIndex],即当前未排序部分中最小的元素,第二个元素是arr[i],即当前轮次起始位置上的元素。

[arr[minIndex], arr[i]]

随后,我们将这个数组的值解构赋值给另外一个数组[arr[i], arr[minIndex]]。这样做就相当于将arr[i]arr[minIndex]的值进行了交换。通过这种方式,我们可以省略中间变量,使得代码更加简洁。但需要注意的是,这种解构赋值的语法在 JavaScript 中被成为“数组解构赋值”,它允许我们从一个数组中提取值,然后将其赋值给变量。在本例中,由于我们要操作的元素是两个特定的数组元素,因此使用数组解构赋值来实现交换操作非常方便。

选择排序的优点是,它比冒泡排序更高效,并且在对小型数据集进行排序时表现良好。该算法可以就地排序,因此不需要额外的空间。然而,JavaScript 选择排序也有一些缺点。首先,在对较大数据集进行排序时,选择排序可能会变得非常缓慢,因为它需要检查每个元素并将其放置在正确的位置上。其次,即使输入数组已经排好序,选择排序仍然需要检查每个元素,这是因为算法不能利用输入数据的任何初始顺序信息。最后,JavaScript 选择排序的时间复杂度是 O(n2n^2),这意味着当数据集变得越来越大时,算法的性能将会急剧下降。

插入排序算法

JavaScript 插入排序是一种基本的排序算法,其主要思想是将待排序的元素一个个地插入到已排好序的元素序列之中。该算法的基本思路如下:

  1. 首先,确定数组的长度,并从第二个元素开始遍历整个数组;
  2. 对于数组中的每个元素,都将其与已拍好序的元素序列进行比较,并找到其应该插入的位置;
  3. 插入新元素时,需要将其前面的所有元素向右移动一个位置,以腾出空间;
  4. 重复上述步骤,知道数组中所有的元素都被插入到正确的位置为止。

方法一

function insertionSort(arr) {
    const len = arr.length; // 获取数组长度
    for (let i = 1; i < len; i++) { // 循环遍历数组元素,从第二个元素开始比较
        let temp = arr[i]; // 将当前要比较的元素存储到临时变量中
        let j = i - 1; // 初始化j为当前元素的前一个元素,用于比较和移动元素位置
        while (j >= 0 && arr[j] > temp) { // 如果当前元素比前一个元素小,则交换两个元素的位置
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = temp; // 如果当前元素比前一个元素大,则将其放在正确位置上
    }
    return arr; // 返回已排序的数组
}

在上述代码示例中,我们首先定义了insertionSort函数来实现插入排序。函数接受一个数组作为参数,并返回一个已排序的数组。接下来,我们遍历整个数组,并将当前元素存储在一个临时变量temp中。然后,我们将已排好序的元素与临时变量进行比较,并找到其应该插入的位置。在这个过程中,我们使用while循环来向右移动已排序的元素。最后,我们将已排序的元素序列中的所有大于当前元素的元素都向右移动一个位置,并将当前元素插入到正确的位置。重复执行次过程,知道数组中的所有元素都被插入到正确的位置为止。

方法二

function insertionSort(arr) {
    // 外层循环控制趟数,外层循环表示无序区第一个值
    for (let i = 1; i < arr.length; i++) {
        // 声明变量,保存无序区第一个值
        let current = arr[i];
        // 内层循环控制无序区第一个值在有序区合适位置的查找
        // 从后往前扫描有序区,前提:无序区第一个值小于有序区的值,当无序区第一个值大于有序区的值,停止扫描
        for (var j = i - 1; j >= 0 && current < arr[j]; j--) {
            // 插入到合适的位置
            // 有序区的值往后移动一位,无序的第一个值插入到最后移动元素的位置
            arr[j + 1] = arr[j];
        }
        // 将当前无序区第一个值插入到有序区合适位置
        arr[j + 1] = current;
    }

    // 返回排序后的数组
    return arr;
}

这是插入排序的另一种算法,与上一种方法的区别较小。此种方法首先通过外部循环遍历数组中的每个元素,从第二个元素开始,假设第一个元素已经排序。在循环内部,将当前元素存储在current变量中。然后,内部循环从已排序子数组的最后一个元素开始,比较每个元素与current值。如果当前元素大于current值,则将其向右移动一个位置,为current值创建空间以便将其插入到正确的位置。然后持续进行比较,直到找到正确的位置或到达已排序子数组的开通。找到正确的位置后,将current值插入到数组中。最后,函数返回排序后的数组。

插入排序的时间复杂度为 O(n2n^2),其中 nn 是待排序元素的个数。具体来说,最坏的情况下,需要进行 n(n1)/2n*(n-1)/2 次比较和交换操作,因此时间复杂度为 O(n2n^2)。最好的情况下,如果输入数据已经接近有序,那么每次只需要进行少量比较和交换操作,时间复杂度可以达到 O(nn)。平均情况下,插入排序的时间复杂度也为 O(n2n^2)。虽然插入排序相对其它排序算法来说并不是最优的,但它在某些特定场景下仍然具有较好的性能表现。例如,对于小规模数据集合或者已经接近有序的数据集合,插入排序往往可以达到较高的效率。

希尔排序算法

希尔排序是插入排序的一种高效率实现,也被称为“缩小增量排序”。它通过将原始数组分割成若干个子数组来改进插入排序,并对每个子数组使用插入排序。这些子数组是按照一定间隔进行选择的,成为增量序列。希尔排序的核心思想是,先使得整个数组达到部分有序状态,然后再通过插入排序将整个数组变为有序。

function shellSort(arr) {
    const len = arr.length;  // 获取数组的长度
    let gap = Math.floor(len / 2);  // 初始化增量为数组长度的一半

    while (gap > 0) {  // 当增量大于 0 时循环执行排序
        for (let i = gap; i < len; i++) {  // 对每个子序列进行插入排序
            let j = i;
            const temp = arr[i];  // 保存当前需要插入的元素
            while (j >= gap && arr[j - gap] > temp) {  // 插入排序的过程
                arr[j] = arr[j - gap];  // 移动元素
                j -= gap;  // 缩小索引值
            }
            arr[j] = temp;  // 将当前元素插入到合适的位置
        }
        gap = Math.floor(gap / 2);  // 缩小增量
    }

    return arr;  // 返回排序后的数组
}

上述代码示例,首先定义了一个shellSort函数,它接收一个待排序的数组arr作为参数。然后获取数组的长度len,并初始化增量gap为数组长度的一半。接下来通过一个while循环不断缩小增量,直到增量为 00 为止。在每个循环中,使用一个for循环来遍历子数组,其中j的初始值为i,即从后往前遍历子数组。接着使用一个while循环,如果当前元素比前面的元素小,则交换两个元素的位置,知道找到合适的位置,并将当前元素插入到该位置。经过多次缩小增量和插入排序操作后,整个数组就可以达到有序状态,最后返回数组即可。需要注意的是,这里使用的增量序列是通过Math.floor(len / 2)来初始化的,也可以选择其它增量序列来实现希尔排序算法。

希尔排序对于小规模数组,它的效率与插入排序类似,但对于大规模数组,它的效率则比插入排序要高的很多。希尔排序也是目前排序算法中较为稳定的算法之一,即相等元素的相对位置在排序前后不会改变。但是希尔排序的时间复杂度并没有被严格证明,因此难以预测其运行的时间,且希尔排序相对于其它更加先进的排序算法,性能并不是最优的。虽是如此,但依然无可否认的是,希尔排序是目前较为高效的一种排序算法,也比较适合处理大规模数据集。

归并排序算法

当我们需要对一个数组进行排序时,归并排序算法采用分治思想来解决问题。在分治思想中,“分”指的是将问题拆分成更小的子问题;“治”指的是解决子问题。具体地,对于一个待排序的数组,归并排序算法会将其分成左右两个子数组,对这两个子数组风别递归调用归并排序算法,知道子数组长度为 1100,即只剩下一个元素或者没有元素,此时子数组已经有序,可以开始进行合并。

在合并过程中,将两个有序的子数组合并成一个有序数组。具体地,使用两个指针分别只想两个子数组的开头,比较两个指针所指元素大小,将较小的元素放入结果数组中,并将对应指针向后移动一位。当其中一个数组的指针到达末尾的时候,将另一个数组中剩余的元素全部放入到结果数组中。这样的话最终得到的就是一个有序数组。因为每次将一个数组划分成两个子数组,所以归并算法的时间复杂度为 O(nlognnlogn)。缺点则是需要额外的存储空间来保存中间结果,所以空间复杂度也是 O(nn)。因为归并算法稳定且效率高,所以在实际应用中得到了广泛的应用。

简单来说,归并排序算法的基本思想即为将一个大数组分为两个较小的子数组,然后递归地对这两个子数组进行排序,最后将两个已排序的子数组合并成为一个有序的数组。

// mergeSort() 函数接受一个数组作为参数,并返回一个排序后的新数组
function mergeSort(arr) {
    // 如果传入的数组长度小于等于 1,那么它已经是有序的了,直接返回
    if (arr.length <= 1) {
        return arr;
    }
    // 计算数组的中间位置,并将数组分成左右两个子数组
    const mid = Math.floor(arr.length / 2);
    const leftArr = arr.slice(0, mid);
    const rightArr = arr.slice(mid);
    // 对左右两个子数组递归调用 mergeSort() 函数进行排序,并将结果合并
    return merge(mergeSort(leftArr), mergeSort(rightArr));
}

// merge() 函数接受两个已排序的子数组作为参数,并返回一个合并后的新数组
function merge(leftArr, rightArr) {
    let result = []; // 新数组,用于存储合并后的结果
    let i = 0, j = 0; // 分别代表左右两个子数组的当前元素的下标
    // 比较左右两个子数组的当前元素大小,将较小的元素添加到新数组中
    while (i < leftArr.length && j < rightArr.length) {
        if (leftArr[i] < rightArr[j]) {
            result.push(leftArr[i]);
            i++;
        } else {
            result.push(rightArr[j]);
            j++;
        }
    }
    // 将剩余的元素添加到新数组中
    return result.concat(leftArr.slice(i)).concat(rightArr.slice(j));
}

在这个函数中,mergeSort()函数首先检查传递给它的数组长度是否小于或者等于 11,如果是,则直接返回该数组。否则,它使用slice()方法将数组切割成两个较小的子数组,并递归调用自身来对两个子数组进行排序。最后,它调用merge()函数来将排序后的两个子数组合并成一个有序的数组。merge()函数使用两个指针ij来遍历左右子数组,比较它们的元素大小,并将较小的元素推入结果数组中。最后,如果一个子数组的所有元素都被添加到了结果数组中,那么另一个子数组中剩余的元素也会被添加到结果数组中。

快速排序算法

快速排序是 JavaScript 中一种经典的基于比较的、分治思想的高效排序算法。它的核心思想是通过分而治之的策略将一个大问题不断拆解成多个小问题,然后分别解决这些小问题。在快速排序中,我们通常会选择待排序序列中的一个元素作为基准值(pivot),然后将所有小于等于基准值的元素放到基准值的左侧,所有大于基准值的元素放到基准值的右侧,最终将整个序列拆解成两个子序列。对于这两个子序列,我们可以递归地应用同样的方法进行排序,知道序列有序。

快速排序的时间复杂度为 O(nlognnlogn),且在实际应用中具有很高的效率。由于其采用了原地排序的方式,不需要额外的空间,因此空间复杂度为 O(11)。但是,快速排序的最坏时间复杂度为 O(n2n^2),在处理含有大量重复元素 的序列时可能出现性能退化的问题,需要通过优化算法来避免此类情况的发生。

传统快速排序

传统快速排序的实现过程可以概括为一下几个步骤:

  1. 选定一个基准值,一般选择数组中间的元素作为基准值;
  2. 将数组中小于基准值的元素移到基准值左边,将大于基准值的元素移到基准值右边;
  3. 对基准值左右两部分重复以上步骤,直到各部分只有一个元素为止。
function quickSort(arr) {
    if (arr.length <= 1) { // 如果数组长度不大于1,则返回原始数组
        return arr;
    }

    const pivotIndex = Math.floor(arr.length / 2); // 选取基准值
    const pivot = arr[pivotIndex]; // 获取基准值

    const leftArr = []; // 定义存储小于基准值元素的左侧数组
    const rightArr = []; // 定义存储大于等于基准值元素的右侧数组

    for (let i = 0; i < arr.length; i++) { // 遍历数组中所有元素
        if (i === pivotIndex) { // 如果当前遍历位置是基准值所在位置,则跳过不处理
            continue;
        }

        if (arr[i] < pivot) { // 如果当前元素小于基准值,则放入左侧数组
            leftArr.push(arr[i]);
        } else { // 否则将其放入右侧数组
            rightArr.push(arr[i]);
        }
    }

    // 递归处理左右两侧数组并合并结果
    return quickSort(leftArr).concat(pivot, quickSort(rightArr));
}

上述代码示例便是一个传统快速排序的算法,它接收一个数组作为输入参数,并返回已排序的数组。首先,函数检查传入的数组是否为空或者只有一个元素。如果是这种情况,它将简单地返回原始数组,因为不需要对其进行排序。然后,函数选择数组中间的元素作为基准值。并且创建了两个空数组leftArrrightArr,用于存储小于基准值的元素和大于等于基准值的元素,然后遍历整个输入数组,将每一个元素与基准值进行比较,如果当前元素小于基准值,则将其添加到leftArr中;否则,将其添加到rightArr中。

接下来,函数递归地调用quickSort函数来对leftArrrightArr进行排序。在这些递归调用中,会对leftArrrightArr每一部分重复上述过程,直到所有子数组都只包含一个元素或为空。最后,函数通过合并以排序的leftArr、基准值和rightArr来返回完全排序的数组。

此种算法的时间复杂度取决于如何选择基准值。在这个实现中,选择中间的元素作为基准值,而不是随机选择或者其它方式,这可能会导致快速排序算法的性能收到影响,最坏的情况下时间复杂度为 O(n2n^2)。但是,在平均情况下,该算法具有 O(nlognnlogn) 的时间复杂度,因此在处理大型数据时具有很高的效率。

双路快速排序算法

双路快速排序是一种常用的排序算法,与传统的快速排序相比,可以在处理有大量重复元素的数组时提供更好的性能。该算法的基本思想是选择一个随机数作为基准值,将数组分为左右两个部分。左边的部分包含小于等于基准值的元素,右边的部分包含大于等于基准值的元素。然后递归地对左右两个部分进行快速排序,直到整个数组有序。

// 定义双路快排函数,接收待排序数组和起始下标和结束下标作为参数
function quickSort(arr, left, right) {
    // 已经排完序
    if (left >= right) {
        return;
    }

    // 随机选择一个枢轴元素作为基准值
    const randomIndex = Math.floor(Math.random() * (right - left + 1)) + left;
    swap(arr, left, randomIndex);
    const pivot = arr[left];

    // 定义左右指针,从两端同时扫描数组
    let i = left + 1;
    let j = right;

    while (true) {
        // 从左往右找第一个大于等于基准值的元素
        while (i <= right && arr[i] < pivot) {
            i++;
        }

        // 从右往左找第一个小于等于基准值的元素
        while (j >= left + 1 && arr[j] > pivot) {
            j--;
        }

        // 左右指针相遇,扫描结束
        if (i > j) {
            break;
        }

        // 将左边大于等于基准值的元素和右边小于等于基准值的元素交换位置
        swap(arr, i, j);
        i++;
        j--;
    }

    // 将基准值放到正确的位置上
    swap(arr, left, j);

    // 对左右两个部分递归进行快速排序
    quickSort(arr, left, j - 1);
    quickSort(arr, j + 1, right);
}

// 定义交换数组中两个元素位置的函数
function swap(arr, i, j) {
    const temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

// 测试代码
const arr = [3, 2, 5, 1, 4, 6, 8, 7, 9, 0];
quickSort(arr, 0, arr.length - 1);
console.log(arr); // 输出 [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

在上述代码中,函数quickSort接收了三个参数:要排序的数组arr、数组左边界left和数组右边界right。函数首先判断左右两个指针是否相遇,如果相遇,就说明以及排好序了,直接返回。否则,则会随机选择一个元素作为基准值,定义左右指针ij,从两端同时扫描数组,找到左边大于等于基准值的元素和右边小于等于基准值的元素,然后交换它们的为止。重复执行上述操作直至左右指针相遇。最后,将基准值放在正确的位置上(即与右边小于等于基准值的元素交换),并递归地对左右两个部分进行快速排序。除此之外,上述代码还定义了一个函数swap,用于交换数组中两个元素的为止。测试代码将一个无需数组传递给quickSort函数进行排序,并打印输出结果。

双路快速排序是一种改进的快速排序算法,与传统的快速排序算法相比,它使用了两个基准值而非一个。在排序过程中,将数组分为三部分:小于第一个基准值的元素、介于两个基准值之间的元素、大于第二个基准值的元素。然后,对前后两部分递归地引用双路快速排序算法。双路快速排序的时间复杂度为 O(nlognnlogn),其中 nn 是待排序数组的大小。这也是标准快速排序算法的时间复杂度。具体来说,双路快速排序的时间复杂度可以通过递推公式求得:T(n)=2Tn/2+O(n)T(n) = 2T{n/2} + O(n),更具主定理,上述递推公式的解为 O(nlognnlogn)。因此,双路快速排序算法的平均时间复杂度为 O(nlognnlogn),最坏情况下的时间复杂度为 O(n2n^2).但是,在实际引用中,双路快速排序的最坏情况很少出现,并且其平均性能优于传统快速排序算法。

三路快速排序算法

三路快速排序是一种优化后的快速排序算法,用于解决原始快速排序中重复元素造成的性能问题。该算法将数组分为三部分:小于、等于和大于基准值的元素。

function quickSort3Way(arr, left, right) {
    if (left >= right) { // 如果左右指针相遇,则返回
        return;
    }

    let lt = left; // 左指针,初始指向数组第一个元素
    let gt = right; // 右指针,初始指向数组最后一个元素
    let i = left + 1; // 遍历指针,初始指向数组第二个元素
    const pivot = arr[left]; // 基准值,选择数组第一个元素

    while (i <= gt) { // 当遍历指针小于等于右指针时
        if (arr[i] < pivot) { // 如果当前元素小于基准值
            [arr[i], arr[lt]] = [arr[lt], arr[i]]; // 将当前元素与左指针交换,并将左指针向右移动
            lt++;
            i++;
        } else if (arr[i] > pivot) { // 如果当前元素大于基准值
            [arr[i], arr[gt]] = [arr[gt], arr[i]]; // 将当前元素与右指针交换,并将右指针向左移动
            gt--;
        } else { // 如果当前元素等于基准值
            i++; // 将遍历指针向右移动
        }
    }

    quickSort3Way(arr, left, lt - 1); // 对小于基准值的元素进行递归排序
    quickSort3Way(arr, gt + 1, right); // 对大于基准值的元素进行递归排序
}

const arr = [5, 4, 3, 2, 1, 5, 4, 3, 2, 1];
quickSort3Way(arr, 0, arr.length - 1);
console.log(arr);

在上述代码中,lt表示小于基准值的元素右边界,初始时与左指针重合;gt表示大于基准值的元素的左边界,初始时与右指针重合;i表示遍历指针,从数组第二个元素开始遍历;pivot表示基准值,选择数组第一个元素作为基准值。

整个算法的流程如下:

  1. 首先将左指针指向数组第一个元素,右指针指向数组最后一个元素,遍历指针指向数组第二个元素;
  2. 遍历数组,如果当前元素小于基准值,则将该元素与左指针指向的元素交换,并将左指针向右移动;如果当前元素大于基准值,则将该元素与右指针指向的元素交换,并将右指针向左移动;
  3. 遍历完成后,数组被分为三大部分:小于、等于和大于基准值的元素;
  4. 对小于基准值的元素和大于基准值的元素分别进行递归排序。

由于每次将等于基准值的元素放在了中间,因此可以有效地避免重复元素造成的性能问题。

三路快速排序是一种基于快速排序的改进算法,它可以更好地处理存在大量重复元素的数组。与传统的快速排序不同,三路快速排序将数组划分为三部分而不是两部分。具体来说,三路快速排序将原始数组划分为小于、等于和大于基准值的三个部分,然后递归地对小于和大于基准值的部分进行快速排序。这样就可以避免在存在大量重复元素的情况下过多地重复比较相等元素,从而提高了排序效率。在时间复杂度方面,三路快速排序的平均时间复杂度为 O(n2n^2),最坏时间复杂度为 O(n2n^2)。空间复杂度方面,三路快速排序需要 O(lognlogn) 的栈空间用于递归调用。

总结

传统快速排序和双路快速排序在一般情况下具有相似的性能表现,但当数组中存在大量重复的元素时,它们的性能会变得较差,这是因为在排序过程中需要进行大量的比较和交换的操作。而三路快速排序相对于传统快速排序和双路快速排序,在处理存在大量重复元素的数组时性能则更为优秀。因为三路快速排序将数组划分为三个部分,可以更加有效地处理重复元素,降低比较的次数,从而提高排序效率。

综合来看,如果处理的数据中存在大量重复元素,那么三路快速排序的性能会更好;如果数据没有明显的重复元素,传统快速排序和双路快速排序可能更为合适。但是,实际上每种排序算法的性能都与具体问题的特点密切相关,需要更具实际问题选择更为适合的算法。

堆排序算法

堆排序是一种高效的排序算法之一,其时间复杂度为 O(nlognnlogn)。它采用了树形结构,将待排序数组看作一颗完全二叉树,并将其转化为一个最大堆或最小堆。

堆排序算法有两种常见方法,分别是:最大堆和最小堆。在最大堆中,堆的根节点是堆中元素的最大值,而在最小堆中,堆的根节点是堆中元素的最小值。因此,在最大堆中,我们可以使用一下步骤进行堆排序:

  1. 将未排序的数组构建成一个最大堆;
  2. 将堆的根节点与数组的最后一个元素交换为止,然后将数组长度减一;
  3. 重新构建最大堆,并将堆的根节点与当前未排序子数组的最后一个元素交换为止;
  4. 重复步骤 2 和 3,直到整个数组都已排序。

在最小堆中,我们只需要将步骤 2 和 3 中的“最大”改为“最小”即可。

最大堆排序算法

构建最大堆的方法是冲最后一个非叶子节点开始循环,一次向上调整堆。对于每个非叶子节点,我们将其和它的左右子节点进行比较,并将最大值交换到当前节点为止。如果发生了交换,那么我们还需要对交换后的子树进行递归调整。

// 最大堆排序函数
function heapSort(arr) {
    // 构建最大堆
    buildHeap(arr);

    // 交换堆顶元素和末尾元素,并重新调整堆
    for (let i = arr.length - 1; i > 0; i--) {
        [arr[0], arr[i]] = [arr[i], arr[0]];  // 交换堆顶元素和末尾元素
        adjustHeap(arr, 0, i);  // 重新调整堆
    }

    return arr;  // 返回排序后的数组
}

// 构建最大堆函数
function buildHeap(arr) {
    // 从最后一个非叶子节点开始循环,依次向上调整堆
    for (let i = Math.floor(arr.length / 2) - 1; i >= 0; i--) {
        adjustHeap(arr, i, arr.length);
    }
}

// 调整堆函数
function adjustHeap(arr, i, len) {
    // 将当前非叶子节点和它的左右子节点进行比较,并将最大值交换到当前节点位置
    let left = 2 * i + 1;
    let right = 2 * i + 2;
    let maxIndex = i;

    if (left < len && arr[left] > arr[maxIndex]) {
        maxIndex = left;
    }

    if (right < len && arr[right] > arr[maxIndex]) {
        maxIndex = right;
    }

    if (maxIndex !== i) {
        [arr[i], arr[maxIndex]] = [arr[maxIndex], arr[i]];  // 交换当前节点和最大值的位置
        adjustHeap(arr, maxIndex, len);  // 递归调整子树
    }
}

上述代码示例中,我们先调用buildHeap函数来构建最大堆。然后我们从数组的最后一个元素开始循环,一次将堆元素(即数组的第一个元素)与当前未排序子数组的最后一个元素交换位置,并重新调整堆。重复这个过程直到整个数组都已排序。

最小堆排序算法

构建最小堆的方法和构建最大堆的方法类似,只不过是将每个非叶子节点与它的左右子节点进行比较,将最小值交换到当前节点为止。如果发生了交换,那么我们还需要堆交换后的子树进行递归调整。

// 最小堆排序函数
function heapSort(arr) {
    // 构建最小堆
    buildHeap(arr);

    // 交换堆顶元素和末尾元素,并重新调整堆
    for (let i = arr.length - 1; i > 0; i--) {
        [arr[0], arr[i]] = [arr[i], arr[0]];  // 交换堆顶元素和末尾元素
        adjustHeap(arr, 0, i);  // 重新调整堆
    }

    return arr;  // 返回排序后的数组
}

// 构建最小堆函数
function buildHeap(arr) {
    // 从最后一个非叶子节点开始循环,依次向上调整堆
    for (let i = Math.floor(arr.length / 2) - 1; i >= 0; i--) {
        adjustHeap(arr, i, arr.length);
    }
}

// 调整堆函数
function adjustHeap(arr, i, len) {
    // 将当前非叶子节点和它的左右子节点进行比较,并将最小值交换到当前节点位置
    let left = 2 * i + 1;
    let right = 2 * i + 2;
    let minIndex = i;

    if (left < len && arr[left] < arr[minIndex]) {
        minIndex = left;
    }

    if (right < len && arr[right] < arr[minIndex]) {
        minIndex = right;
    }

    if (minIndex !== i) {
        [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];  // 交换当前节点和最小值的位置
        adjustHeap(arr, minIndex, len);  // 递归调整子树
    }
}

在上述代码示例中,我们首先先调用了buildHeap函数来构建最小堆。然后我们从数组的最后一个元素开始循环,依次将堆顶元素(即数组的第一个元素)与当前未排序子数组的最后一个元素交换位置,并重新调整堆。重复这个过程直到整个数组都已排序。

计数排序算法

计数排序是一种非比较排序算法,可以对具有固定范围的整数数组进行排序。计数排序算法首先计算每个元素出现的次数,然后累加这些计数器来确定每个元素在排序数组中的位置。计数排序的时间复杂度为 O(n+kn + k),其中 nn 是输入数组的长度,kk 是输入数组中的元素(最大值和最小值之差 +1+1),这是因为使用计数排序算法首先要遍历输入数组并增加计数器,这一步的操作需要花费 O(nn) 的时间复杂度,随后,还需要堆计数器数组进行遍历并更新输入数组,这一步操作需要花费 O(kk) 的时间复杂度。因为计数器数组大小是 kk,所以这里的时间复杂度是 O(kk)。综上所述,总时间复杂度为 O(n+kn +k)。计数排序算法的空间复杂度为 O(kk),其中 kk 是输入数组中的元素范围(最大值和最小值之差 +1+1)。

在使用计数排序方法需要注意的是,当输入数组中的元素范围很大,空间复杂度可能会很高。如果输入数组中元素的范围超过了计数器数组的大小,那么计数器数组将无法容纳所有元素的计数,这时候就可以使用其它排序算法,例如归并排序或者快速排序。除此之外,计数排序只适用于具有固定范围的整数数组,并不适用于包含负数的数组。

function countingSort(arr, min, max) {
  // 创建一个存储计数器的数组
  const counts = new Array(max - min + 1).fill(0);
  
  // 遍历输入数组并增加计数器
  for (let i = 0; i < arr.length; i++) {
    counts[arr[i] - min]++;
  }
  
  // 遍历计数器数组并更新输入数组
  let j = 0;
  for (let i = 0; i < counts.length; i++) {
    while (counts[i] > 0) {
      arr[j] = i + min;
      j++;
      counts[i]--;
    }
  }
  
  return arr;
}

// 示例用法
const unsortedArray = [9, 3, 1, 4, 6, 8, 7, 2, 5];
const sortedArray = countingSort(unsortedArray, 1, 9);

console.log(sortedArray);

在上述代码示例中,首先定义了一个名为countingSort的函数,并且令其接收三个参数,分别是:待排序数组arr、数组中的最小值min和最大值max。在函数内部,我们创建了一个名为counts的计数器数组。该数组的大小为 maxmin+1max – min +1,以便于存储输入数组中出现的每个元素的计数。接下来,我们遍历输入数组并为每个元素增加计数器。这里需要注意的是,在计数器数组中的索引应该与输入数组中的值对应,因此我们将arr[i] - min作为计数器数组的索引。最后,我们遍历计数器数组并更新输入数组。我们使用两个循环变量ij,一个用于迭代计数器数组,另一个则用于保持输入数组中元素的顺序。内部的while循环用于处理计数器数组中的多个相同元素。

桶排序

桶排序是一种线性时间复杂度的排序算法,它的基本思想是将排序元素分到有限数量的桶中,再堆每个桶进行排序,最后将各个桶中的结果按照顺依次连接起来得到有序序列。

function bucketSort(arr, bucketSize = 5) {
    if (arr.length === 0) {  // 如果数组为空,则直接返回
        return arr;
    }

    // 找到最大值和最小值
    let minValue = arr[0];
    let maxValue = arr[0];
    for (let i = 1; i < arr.length; ++i) {
        if (arr[i] < minValue) {
            minValue = arr[i];
        } else if (arr[i] > maxValue) {
            maxValue = arr[i];
        }
    }

    // 计算桶的数量
    const bucketCount = Math.floor((maxValue - minValue) / bucketSize) + 1;
    const buckets = new Array(bucketCount);

    // 将元素放入桶中
    for (let i = 0; i < arr.length; ++i) {
        const bucketIndex = Math.floor((arr[i] - minValue) / bucketSize);
        if (!buckets[bucketIndex]) {
            buckets[bucketIndex] = [];
        }
        buckets[bucketIndex].push(arr[i]);
    }

    // 对每个桶内部进行排序
    arr.length = 0;  // 清空原数组
    for (let i = 0; i < buckets.length; ++i) {
        insertionSort(buckets[i]); // 这里使用插入排序对桶内部进行排序
        for (let j = 0; j < buckets[i].length; ++j) {
            arr.push(buckets[i][j]);  // 将排好序的元素放回数组中
        }
    }

    return arr;  // 返回排序后的数组
}

// 插入排序,用于对每个桶内部进行排序
function insertionSort(arr) {
    const len = arr.length;
    for (let i = 1; i < len; ++i) {
        let j = i - 1;
        const temp = arr[i];
        while (j >= 0 && arr[j] > temp) {
            arr[j + 1] = arr[j];  // 将元素向右移动
            --j;
        }
        arr[j + 1] = temp;  // 将当前元素插入到正确的位置
    }
}

再上述代码中,首先是定义了一个名为bucketSort的函数。该函数定义了两个参数,分别是:arr和一个可选的桶大小参数bucketSize。如果输入数组为空,则直接返回。否则,它会遍历一边输入数组,找到其中的最小值和最大值。然后根据桶大小和最小值、最大值计算出所需的桶数量,并创建一个空桶数组。接着将输入数组中的每个元素分配到相应的桶中。再分配过程中,需要根据元素的值和最小值来计算该元素所属的桶。最后,堆每个非空的桶内部进行排序,采用插入排序算法。排序完成后,按照桶的顺序以此将各个桶中排好序的元素拼接成一个新的有序数组并返回即可。接下来,我们还定义了一个名为insertionSort的函数。这是一个辅助函数,用于对每个桶内部进行排序。它接收一个数组arr作为输入,使用插入排序算法对其进行排序。最后,由于 JavaScript 的语言特征,再对桶内部进行排序时需要提前清空原数组,这样才能保证排序结果正确。

桶排序是一种常用的线性排序算法,其主要优点是时间复杂度较低、稳定性好,缺点则是占用空间较多,在数据分布不均匀的状态下,排序效率可能降低。桶排序的时间复杂度为 O(n+kn + k),其中 nn 是待排序元素的个数,kk 是桶的个数。空间复杂度取决于桶的个数和每个桶能容纳的元素数量,如果每个桶只能容纳一个桶,则需要 nn 个桶,空间复杂度为 O(nn),但如果每个桶可以容纳多个元素,则需要更少的桶,空间复杂度也会相应的减小。在实际应用过程中,桶排序通常用于对非负整数进行排序,此时桶的数量通常为最大元素值 +1+1,因此空间复杂度也为 O(kk)。

基数排序算法

JavaScript 基数排序,它根据数字的位数将整数分配到桶中进行排序。基数排序可以按照数字的个位、十位、百位等顺序对数据进行排序,依次类推直到最高位排序完成。

// 基数排序算法
function radixSort(arr) {
    // 获取数组中最大的数字,确定需要遍历几次
    const maxNum = Math.max(...arr);
    const maxLength = maxNum.toString().length;

    // 初始化桶数组
    const bucket = Array.from({ length: 10 }, () => []);

    for (let i = 0; i < maxLength; i++) {
        // 根据当前位数的值放入对应的桶中
        for (let j = 0; j < arr.length; j++) {
            const num = arr[j];
            const digit = getDigit(num, i); // 获取 num 在第 i 位上的数字值
            bucket[digit].push(num); // 将 num 放入对应的桶中
        }

        // 依次将桶中的元素取出,并放回原数组,重复这个过程直到最高位
        let idx = 0;
        for (let k = 0; k < bucket.length; k++) {
            while (bucket[k].length > 0) {
                arr[idx++] = bucket[k].shift(); // 依次取出桶中的数字并放回原数组
            }
        }
    }

    return arr; // 返回排序后的数组
}

// 获取数字在指定位数上的值
function getDigit(num, i) {
    // 使用 Math.floor() 函数和 Math.abs() 函数获取 num 的绝对值,并将其除以 10^i 取整,再对 10 取模,得到 num 在第 i 位上的数字值
    return Math.floor(Math.abs(num) / Math.pow(10, i)) % 10;
}

在上述代码中,函数radixSort(arr)的参数是要排序的整个数组arr。该函数返回排序后的数组。首先,函数通过Math.max()函数获取到了数组中的最大值,然后计算出最大值所占位数maxLength。接着,初始化一个桶组数bucket,其中包含了 10 个空数组,分别对于数字 0~9。接下来,使用了两个嵌套循环,从低到高以此将数字放入对应的桶中。具体来说,外层循环遍历位数(从 0 到maxLength-1),内层循环遍历数组元素,并根据当前位数上的数字将其放入桶中。这里使用了一个辅助函数getDigit(num, i),它返回数字num在第i位上的数字值。当所有数字被放入桶中后,再从低到高以此将桶中的数字取出,并放回原数组中。具体来说,外层循环遍历位数(从 0 到maxLength-1),内层循环遍历桶数组中的每一个桶,并将桶中的数字依次取出并放回原数组中。在这个过程中需要使用一个变量idx来记录原数组中数字的位置。最后,函数返回排序后的数组。

基数排序的时间复杂度为 O(knkn),其中 kk 是最大数字的位数,nn 是要排序的数字总数。在每一次遍历中,需要对 nn 个数字进行放入桶和收集的操作,所以总共需要进行 kk 次遍历,因此时间复杂度为 O(n+kn + k)。它的空间复杂度通常为 O(n+kn + k),其中 nn 是要排序的数字总数,kk 是桶的数量。在排序过程中需要使用多个桶来存储待排序的元素,每个桶的大小不会超过 nn,因此需要的额外空间为 O(n+kn + k)。相对于其它排序算法,基数排序具有线性复杂度,并且适用于大量数字长度相同的排序场景。然而,基数排序可能需要额外空间来存储桶,并且只适用于数字类型的数据。

原文链接:https://juejin.cn/post/7225879724545966117 作者:名岐

(0)
上一篇 2023年4月26日 上午10:10
下一篇 2023年4月26日 上午10:20

相关推荐

发表回复

登录后才能评论