JavaScript 插入排序详解及三种常见实现

JavaScript插入排序是一种简单直观的排序算法，它适用于小规模数据或部分已经有序的数据。其基本思想是通过构建一个有序序列，对于未排序的数据，将其插入到已排序序列的适当位置。以下是三种常见的JavaScript实现方法： 1. 通用实现： - 在这个版本中，插入排序从左到右遍历待排序数组（`arr`），设置一个指针 `j` 从当前元素的左侧开始向右扫描已排序区间。 - 对于每个待排序元素 `current`，从 `j` 开始，如果 `current` 小于 `arr[j]`，就将 `arr[j]` 向右移动一位，直到找到合适的位置插入 `current` 或 `j` 走到数组开头。 - 当找到合适的位置，将 `current` 放入，并更新 `j` 为下一个已排序元素。重复此过程，直到所有待排序元素处理完毕。 2. 利用 `splice` 方法实现： - 这种方法利用JavaScript的 `splice` 函数，可以一次操作完成元素的移动，避免了多次数组的遍历和插入操作。虽然代码量较少，但性能上可能与通用实现相近，因为它们本质上都在进行相同的元素移动。 3. 新建数组法与 `splice` 结合： - 这种方法首先创建一个新的数组，然后将已排序部分复制过去，对剩余的待排序部分进行插入操作。这种方法的优点是易于理解，但额外创建了一个新的数组，空间开销较大。 以下是标准版和通用版的源代码： ```javascript // 标准版 function insertSort(arr) { var current, l = arr.length, j; console.time('time'); for (var i = 0; i < l; i++) { j = i; current = arr[i]; while (j-- >= 0 && current < arr[j]) { arr[j + 1] = arr[j]; } arr[j + 1] = current; } console.timeEnd('time'); return arr; } // 标准通用版 function insertSort(arr) { var current, l = arr.length, j; console.time('time'); for (var i = 0; i < l; i++) { j = i - 1; current = arr[i]; while (j >= 0 && current < arr[j]) { arr[j + 1] = arr[j]; j--; } arr[j + 1] = current; } console.timeEnd('time'); return arr; } 示例： var arr = [4, 6, 2, 1, 8, 9, 7, 3, 5, 9, 4]; insertSort(arr); ``` 尽管插入排序在最坏情况下的时间复杂度为 O(n^2)，但由于其简单的实现和在部分有序数据上的优秀表现，它仍然在某些场景下被使用。然而，对于大规模数据或者需要高效排序的情况，快速排序、归并排序等更高级的排序算法通常更为适用。