JavaScript数组排序的六种常见算法总结

一、排序算法简介

排序算法是计算机学科中最基本的算法之一，也是编程中必须要了解的重要内容。在JavaScript编程中，排序算法的应用非常广泛，尤其是在处理和展现数据方面。

二、排序算法分类

根据不同的排序方式和算法思想， 排序算法可以被分类为以下六类。

1. 冒泡排序
2. 选择排序
3. 插入排序
4. 快速排序
5. 归并排序
6. 希尔排序

下面将逐一介绍这六种排序算法的具体实现和使用场景。

1. 冒泡排序

冒泡排序是最简单的排序算法之一，可以用于对几乎任何类型的数据进行排序。它的基本思想是：对比相邻的两个元素，如果前一个元素大于后一个元素，则将它们交换位置，这样一轮下来就可以将列表中最大的元素移到最右边。

以下是一个简单的冒泡排序的实现。

function bubbleSort(arr) {
  var len = arr.length;
  for (var i = 0; i < len - 1; i++) {
    for (var j = 0; j < len - i - 1; j++) {
      // 如果前一个元素比后一个元素大，则交换它们的位置
      if (arr[j] > arr[j + 1]) {
        var temp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
      }
    }
  }
  return arr;
}

下面是一个使用冒泡排序对数组进行排序的演示示例。

var arr = [5, 3, 8, 4, 2];

console.log(bubbleSort(arr)); // 输出 [2, 3, 4, 5, 8]

2. 选择排序

选择排序是一种简单的排序算法，其基本思想是：找到数组中最小的元素，将其放在数组的第一位，接着找到数组中第二小的元素，将其放在数组的第二位，以此类推，直到排序完成。

以下是一个简单的选择排序的实现。

function selectionSort(arr) {
    var len = arr.length;
    var minIndex, temp;
    for (var i = 0; i < len - 1; i++) {
        minIndex = i;
        for (var j = i + 1; j < len; j++) {
            if (arr[j] < arr[minIndex]) { // 找到最小的元素
                minIndex = j; // 将最小元素的索引保存
            }
        }
        temp = arr[i];
        arr[i] = arr[minIndex];
        arr[minIndex] = temp;
    }
    return arr;
}

下面是一个使用选择排序对数组进行排序的演示示例。

var arr = [5, 3, 8, 4, 2];

console.log(selectionSort(arr)); // 输出 [2, 3, 4, 5, 8]

3. 插入排序

插入排序是一种简单的排序算法，其基本思想是：将一个元素插入到已经排好序的数组的合适位置中，以此类推，直到排序完成。

以下是一个简单的插入排序的实现。

function insertionSort(arr) {
    var len = arr.length;
    var preIndex, current;
    for (var i = 1; i < len; i++) {
        preIndex = i - 1;
        current = arr[i];
        while(preIndex >= 0 && arr[preIndex] > current) {
            arr[preIndex + 1] = arr[preIndex];
            preIndex--;
        }
        arr[preIndex + 1] = current;
    }
    return arr;
}

下面是一个使用插入排序对数组进行排序的演示示例。

var arr = [5, 3, 8, 4, 2];

console.log(insertionSort(arr)); // 输出 [2, 3, 4, 5, 8]

4. 快速排序

快速排序是一种高效的排序算法，其基本思想是：选取一个值作为基准值，将比基准值小的数移动到左边，比基准值大的数移动到右边，然后对左右两个子数组分别执行此操作，直到子数组中只有一个元素。

以下是一个简单的快速排序的实现。

function quickSort(arr) {
    if (arr.length <= 1) { // 如果数组只有一个元素，直接返回
        return arr;
    }
    var pivotIndex = Math.floor(arr.length / 2); // 取基准值的索引
    var pivot = arr.splice(pivotIndex, 1)[0]; // 取出基准值，并将其从数组中删除
    var left = [];
    var right = [];
    for (var i = 0; i < arr.length; i++) {
        if (arr[i] < pivot) { // 把较小的值放在左边
            left.push(arr[i]);
        } else { // 把较大的值放在右边
            right.push(arr[i]);
        }
    }
    return quickSort(left).concat([pivot], quickSort(right));
}

下面是一个使用快速排序对数组进行排序的演示示例。

var arr = [5, 3, 8, 4, 2];

console.log(quickSort(arr)); // 输出 [2, 3, 4, 5, 8]

5. 归并排序

归并排序是一种基于归并操作的排序算法，其基本思想是：将两个有序数组归并成一个更大的有序数组，以此类推，直到整个数组有序为止。

以下是一个简单的归并排序的实现。

function mergeSort(arr) {
    var len = arr.length;
    if (len < 2) { // 如果数组只有一个元素，直接返回
        return arr;
    }
    var middle = Math.floor(len / 2), // 取中间值
        left = arr.slice(0, middle),
        right = arr.slice(middle);
    return merge(mergeSort(left), mergeSort(right));
}
function merge(left, right) {
    var result = [];
    while (left.length && right.length) {
        if (left[0] <= right[0]) { // 如果左边数组的第一个元素小于右边数组的第一个元素
            result.push(left.shift()); //  将左边数组的第一个元素取出，放入结果数组中，并删除左边数组的第一个元素
        } else {
            result.push(right.shift()); //  将右边数组的第一个元素取出，放入结果数组中，并删除右边数组的第一个元素
        }
    }
    while (left.length) result.push(left.shift()); // 如果左边数组还有其余元素，就将其全部加入结果数组中
    while (right.length) result.push(right.shift()); // 如果右边数组还有其余元素，就将其全部加入结果数组中
    return result;
}

下面是一个使用归并排序对数组进行排序的演示示例。

var arr = [5, 3, 8, 4, 2];

console.log(mergeSort(arr)); // 输出 [2, 3, 4, 5, 8]

6. 希尔排序

希尔排序是一种改进版的插入排序算法，它的基本思想是：将一个数组分成若干个子数组，分别对这些子数组进行插入排序，待整个数组中的元素基本有序时，再对整个数组进行一次插入排序。

以下是一个简单的希尔排序的实现。

function shellSort(arr) {
    var len = arr.length,
        temp,
        gap = 1;
    while(gap < len/3) { // 计算间隔序列
        gap = gap * 3 + 1;
    }
    for (gap; gap > 0; gap = Math.floor(gap/3)) {
        for (var i = gap; i < len; i++) {
            temp = arr[i];
            for (var j = i - gap; j >= 0 && arr[j] > temp; j -= gap) {
                arr[j + gap] = arr[j];
            }
            arr[j + gap] = temp;
        }
    }
    return arr;
}

下面是一个使用希尔排序对数组进行排序的演示示例。

var arr = [5, 3, 8, 4, 2];

console.log(shellSort(arr)); // 输出 [2, 3, 4, 5, 8]

以上就是JavaScript数组排序的六种常见算法的具体实现和应用场景。在实际开发中，我们可以根据不同场景选择不同的排序算法，以实现最佳性能。