写一个数组的插入排序算法

插入排序是一种简单直观的排序算法，它的基本思想是将未排序的元素一个一个插入到已排序的序列中，构建有序的序列。

以下是一个用 JavaScript 实现的数组插入排序算法：

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;
}

算法的基本思路是将数组分为已排序和未排序两部分，初始时已排序部分只有第一个元素，将后续未排序元素一个一个插入到已排序部分中。每次迭代，取出未排序部分的第一个元素作为当前元素，将它与已排序部分的元素从后往前比较，直到找到第一个比它小的元素或已经到达已排序部分的首位。然后将当前元素插入到该元素之后，已排序部分的长度加一。

时间复杂度为 O(n^2)，空间复杂度为 O(1)。

相关问题

一维数组插入排序

一维数组插入排序的实现思路如下：

1. 从第二个元素开始，将该元素插入到已排序的序列中，使得插入后仍然保持有序。

2. 对于每一个未排序的元素，在已排序的序列中从后往前扫描，找到相应的位置并插入。

以下是一维数组插入排序的示例代码（使用 C++ 语言实现）：

void insertionSort(int arr[], int n) {
    int i, key, j;
    for (i = 1; i < n; i++) {
        key = arr[i];
        j = i - 1;

        /* Move elements of arr[0..i-1], that are greater than key, to one position ahead of their current position */
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j = j - 1;
        }
        arr[j + 1] = key;
    }
}

在这个示例代码中，`arr` 是待排序的一维数组，`n` 是数组的大小。函数 `insertionSort` 实现了一维数组插入排序的算法。

用Java写一个直接插入排序算法

好的，以下是Java代码实现直接插入排序算法：

public class InsertionSort {
    public static void main(String[] args) {
        int[] arr = {5, 2, 8, 3, 9, 1};
        insertionSort(arr);
        System.out.println(Arrays.toString(arr));
    }
    
    public static void insertionSort(int[] arr) {
        int n = arr.length;
        for (int i = 1; i < n; i++) {
            int key = arr[i];
            int j = i - 1;
            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j];
                j--;
            }
            arr[j + 1] = key;
        }
    }
}

这段代码中，首先定义了一个 `main` 方法来测试 `insertionSort` 方法。在 `insertionSort` 方法中，我们从第二个元素开始遍历数组，将当前元素 `key` 存储在一个变量中。然后，我们使用另一个变量 `j` 来遍历已经排序好的子数组。如果子数组中的元素比 `key` 大，则将它们向右移动一位。最后，将 `key` 插入到正确的位置。这样，通过遍历整个数组，我们可以将其排序。