javascript如何用数组实现冒泡排序的算法，不用sort函数怎么实现？

在 JavaScript 中，冒泡排序是一种简单的排序算法，其核心思想是通过多次遍历待排序的数组，相邻元素之间进行比较并交换，直到整个数组有序。冒泡排序的基本实现不使用 JavaScript 内置的 sort 函数。

冒泡排序算法步骤

1. 比较相邻元素：遍历数组，将相邻的两个元素进行比较。
2. 交换元素：如果第一个元素大于第二个元素，则交换它们的位置。
3. 重复过程：继续遍历剩下的元素，每次遍历结束后，最大的元素会被移动到数组的末尾。
4. 优化：如果在某次遍历中没有进行任何交换，说明数组已经有序，可以提前结束排序过程。

实现代码

以下是一个 JavaScript 示例，演示如何用数组实现冒泡排序：

javascript
复制代码
function bubbleSort(arr) {
    let n = arr.length;
    let swapped;
    
    // 遍历数组
    for (let i = 0; i < n - 1; i++) {
        swapped = false;
        
        // 在每次遍历中，比较相邻的元素
        for (let j = 0; j < n - i - 1; j++) {
            // 如果当前元素大于下一个元素，则交换
            if (arr[j] > arr[j + 1]) {
                // 交换元素
                [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
                swapped = true;
            }
        }
        
        // 如果没有进行交换，数组已经有序，提前结束排序
        if (!swapped) break;
    }
    
    return arr;
}

// 示例
const array = [64, 34, 25, 12, 22, 11, 90];
console.log("Original array:", array);
const sortedArray = bubbleSort(array);
console.log("Sorted array:", sortedArray);

代码解析

1. 初始化：

   • n：数组的长度。
   • swapped：用于标记是否进行了元素交换。

2. 外层循环：

   • 遍历数组 n-1 次，因为每次遍历都会将最大的元素放到正确的位置。

3. 内层循环：

   • 遍历未排序部分的元素进行比较和交换。
   • 如果 arr[j] > arr[j + 1]，则交换两个元素的位置。

4. 优化：

   • 如果在某次遍历中没有进行交换，说明数组已经排序完成，使用 swapped 标记提前退出排序。

5. 返回结果：

   • 最终返回排序后的数组。

优化和复杂度

• 时间复杂度：

  • 最坏情况和平均情况时间复杂度为 O(n²)，其中 n 是数组的长度。
  • 最佳情况（数组已经有序）时间复杂度为 O(n)（通过优化的冒泡排序实现）。

• 空间复杂度：

  • 冒泡排序是就地排序算法，空间复杂度为 O(1)，不需要额外的存储空间。

总结

冒泡排序是一种简单的排序算法，通过多次比较和交换相邻元素，将最大（或最小）元素逐步移动到数组的末尾。上述 JavaScript 实现展示了如何用数组实现冒泡排序，同时包括了优化措施以提高效率。