极客笔记JavaScript 实现插入排序以按递增顺序对数字数组进行排序
排序数组的艺术对于编程领域非常重要，因为它允许对数据进行高效的组织和操作。在实现可靠的排序算法时，插入排序是一种多用途且有效的选择。在本文中，我们深入探索JavaScript的复杂世界，探讨如何使用插入排序将数字数组按递增顺序排列。通过理解算法的底层机制并利用JavaScript的能力，开发人员可以解锁高效地排序和组织数值数据的潜力，提升应用程序的性能和可用性。
问题陈述
目标是利用JavaScript实现插入排序算法，以按升序排列数字数组。主要目标是设计一个程序，能够智能地重新排列给定数组的元素，确保每个后续元素根据其数值与前面的元素相比将其放置在适当的位置。举个示例，假设我们提供一个数组
[9, 2, 7, 4, 1]
在执行插入排序算法后，预期的结果应该是一个遵循递增排序序列的数组，例如
[1, 2, 4, 7, 9]
方法
在本文中，我们将看到解决上述问题的多种不同方法，使用JavaScript实现-
- 基本插入排序
-
二进制插入排序
-
递归插入排序
方法1：基本插入排序
基本插入排序算法在数组中维护一个已排序子数组。从第二个元素开始，将每个元素与子数组中的前一个元素进行比较，并将较小的元素向右移动。该过程持续进行，直到找到正确的位置，并插入元素。对所有元素重复此过程，最终得到完全排序的数组。
示例
insertionSort函数将数组arr作为输入，并使用插入排序算法返回排序后的数组。它从第二个元素开始迭代，将其存储在当前变量中。while循环将当前元素与已排序子数组中的前一个元素进行比较，将较大的元素向右移动。循环继续，直到到达数组的开头或找到一个较小的元素。然后，将当前元素插入到已排序子数组的正确位置。对所有元素重复此过程，最终得到排序的数组。
function insertionSort(arr) {
for (let i = 1; i < arr.length; i++) {
let current = arr[i];
let j = i - 1;
while (j >= 0 && arr[j] > current) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = current;
}
return arr;
}
const arr = [9, 2, 7, 4, 1];
console.log(insertionSort(arr));
输出
以下是控制台输出−
[ 1, 2, 4, 7, 9 ]
方法2：二分插入排序
二分插入排序算法通过在已排序的子数组中利用二分搜索确定每个元素的正确位置，提高了基本插入排序的效率。不再线性搜索，而是通过将当前元素与子数组的中间元素进行比较来执行二分搜索，并相应调整搜索边界。一旦确定了插入点，就会将右侧的元素向右移动以腾出空间，并插入当前元素。这个过程对所有元素重复进行，最终得到一个完全排序的数组。
示例
binaryInsertionSort函数接受一个数组arr并使用二分插入排序算法返回已排序的数组。它从第二个元素开始迭代，假设第一个元素已经排序好。当前元素存储在current变量中。算法在已排序的子数组中执行二分搜索，通过将其与中间元素进行比较并调整搜索边界来找到当前元素的正确位置。一旦找到位置，算法将元素向右移动并插入当前元素到正确位置。这个过程对所有元素重复进行，最终得到一个已排序的数组。
function binaryInsertionSort(arr) {
for (let i = 1; i < arr.length; i++) {
let current = arr[i];
let left = 0;
let right = i - 1;
while (left <= right) {
let mid = Math.floor((left + right) / 2);
if (current < arr[mid]) {
right = mid - 1;
} else {
left = mid + 1;
}
}
for (let j = i - 1; j >= left; j--) {
arr[j + 1] = arr[j];
}
arr[left] = current;
}
return arr;
}
const arr = [9, 2, 7, 4, 1];
console.log(binaryInsertionSort(arr));
输出
以下是控制台输出结果 –
[ 1, 2, 4, 7, 9 ]
方法3：递归插入排序
递归插入排序算法是插入排序的递归版本，使用递归来对数组进行排序。对于大小为1或更小的子数组，它认为它们已经排序好了。对于较大的子数组，它递归调用自身来对不包含最后一个元素的子数组进行排序。在递归调用返回并且子数组已排序好后，算法将最后一个元素放置到已排序子数组中的正确位置。这是通过将最后一个元素与已排序子数组中的元素进行比较，并在需要时将它们向右移动来实现的。该过程重复进行，直到所有元素都插入到它们的正确位置，得到一个完全排序的数组。
示例
recursiveInsertionSort函数对输入数组递归应用插入排序算法。它检查数组是否已经排序好，如果是，则返回它。否则，它在一个大小为n-1的子数组上递归调用自身。在递归调用之后，函数使用while循环将最后一个元素与已排序子数组中的元素进行比较。如果一个元素较大，则将其向右移动。这个过程一直持续到循环到达数组的开头或者找到一个较小的元素为止。最后，最后一个元素被插入到正确的位置。这个过程对所有元素都重复进行，得到一个排序好的数组。
function recursiveInsertionSort(arr, n = arr.length) {
if (n <= 1) return arr;
recursiveInsertionSort(arr, n - 1);
let last = arr[n - 1];
let j = n - 2;
while (j >= 0 && arr[j] > last) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = last;
return arr;
}
const arr = [9, 2, 7, 4, 1];
console.log(recursiveInsertionSort(arr));
输出
以下是控制台输出结果-
[ 1, 2, 4, 7, 9 ]
结论
最终，使用JavaScript实现插入排序算法对数组进行升序排列是开发人员寻求高效排序方法的明智选择。通过迭代地将元素置于适当的位置，该算法展示了一种精明的处理数值数据的方法。虽然插入排序可能没有其他排序技术那么广为人知，但它的效率和简单性使其在某些情况下成为一种宝贵的工具。在JavaScript中使用这个算法可以使开发人员在编码中使用一个鲜为人知但强大的工具，从而实现数组的简化和有序化。总之，将插入排序算法与JavaScript结合使用，对于那些在数组排序工作中追求精确和优雅的人来说，是一个充满幻想的努力。