详解插入排序算法原理与使用方法

插入排序算法是一种简单直观的排序算法，其基本思路是从序列的第二个元素开始，逐个将每个元素插入到已排序的序列中，直到所有元素都被插入完成。它的时间复杂度是O(n²)，因此适用于小规模数据的排序。

下面我们来详细讲解一下插入排序算法的使用方法和实现过程：

算法思路

1. 从序列的第二个元素开始，逐个将每个元素插入到已排序的序列中
2. 对于未排序的元素，依次与已排序的元素进行比较，找到合适的位置插入
3. 重复以上两个步骤，直到所有元素都被插入完成

代码实现

以下是使用JavaScript语言实现插入排序的示例代码：

function insertionSort(arr) {
  for (let i = 1; i < arr.length; i++) {
    let j = i - 1;
    let temp = arr[i];
    while (j >= 0 && arr[j] > temp) {
      arr[j + 1] = arr[j];
      j--;
    }
    arr[j + 1] = temp;
  }
  return arr;
}

console.log(insertionSort([3, 2, 1])); // [1, 2, 3]
console.log(insertionSort([12, 45, 21, 8, 1])); // [1, 8, 12, 21, 45]

以上代码中，我们定义了一个insertionSort函数来实现插入排序。首先，我们从第二个元素开始遍历整个数组，假设当前要插入的元素为arr[i]。然后，我们找到arr[i]的合适位置，即将arr[i]插入到已排序的数组中。我们采用while循环从右往左遍历已排序的数组，如果已排序的数组中的元素比arr[i]大，就将这个元素往右移动一位，继续遍历。最后，将arr[i]插入到合适的位置即可。

示例说明

以下是两条插入排序的示例说明：

示例一

我们有一个数组[3, 2, 1]，对它进行插入排序。初始时，数组的第一个元素3已经是排好序的了（因为它是数组的第一个元素）。接下来，我们需要将数组中的元素2插入到已排序的数组中。由于2比3小，因此我们将3往右移动一位，把2插入到3的位置。此时数组变为[2, 3, 1]。接下来，我们需要将数组中的元素1插入到已排序的数组中。由于1比2小，因此我们将2往右移动一位，再将1插入到2的位置。此时数组变为[1, 2, 3]，排序完成。

示例二

我们有一个数组[12, 45, 21, 8, 1]，对它进行插入排序。初始时，数组的第一个元素12已经是排好序的了（因为它是数组的第一个元素）。接下来，我们需要将数组中的元素45插入到已排序的数组中。由于45比12大，因此45不需要移动。接下来，我们需要将数组中的元素21插入到已排序的数组中。由于21比45小，因此我们将45往右移动一位，再将21插入到45的位置。此时数组变为[12, 21, 45, 8, 1]。接下来，我们需要将数组中的元素8插入到已排序的数组中。由于8比45小，因此我们将45往右移动一位，接着我们将21往右移动一位，再将8插入到21的位置。此时数组变为[12, 8, 21, 45, 1]。最后，我们需要将数组中的元素1插入到已排序的数组中。由于1比45小、比21小、比8小，因此我们将45往右移动一位，接着我们将21往右移动一位，再将8往右移动一位，最后将1插入到8的位置。此时数组变为[1, 8, 12, 21, 45]，排序完成。

通过以上两个示例，我们可以更加深入地理解插入排序算法的过程和使用方式。