c - 试图实现插入排序公司

Question

我正在尝试实现插入排序，但我似乎无法正确地将值交换到正确的位置。

这是我到目前为止所拥有的：

void insertion(int ar[], int n) {
    for (int i = 1; i < n; i++) {
        int temp = ar[i];
        int j = i;
        while (ar[j - 1] > ar[i] && (j - 1) >= 0) {
            ar[i] = ar[j - 1];
            ar[j - 1] = temp;
        }
    }
}

标签： calgorithmsortinginsertion-sort

Answer 1

该源码总结了插入排序算法的步骤如下：

算法：按升序对大小为 n 的数组进行排序：1
：遍历数组。 2：将当前元素（键）与其前身进行比较。 3：如果关键元素小于它的前一个元素，则将其与之前的元素进行比较。将较大的元素向上移动一位，为交换的元素腾出空间。arr[1]arr[n]

第一步你做对了：

void insertion(int ar[], int n) {
    for (int i = 1; i < n; i++) {
        // ..
    }
}

但是您完全错过了第二步，以及您的 while 循环：

int j = i;
while (ar[j - 1] > ar[i] && (j - 1) >= 0) {
    ar[i] = ar[j - 1];
    ar[j - 1] = temp;
}

有一些问题，即1）它陷入无限循环，因为变量j永远不会递减；2）它的条件应该被交换，所以ar[j - 1] > ar[i] && (j - 1) >= 0应该是(j - 1) >= 0 && ar[j - 1] > ar[i]. 否则，您将访问-1数组的位置ar

---

剧透

插入排序的可能实现如下所示：

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

让我们看看它是如何与输入一起工作的[8, 6, 4, 20, 10]（键由 '()' 表示）

1. i = 1，j = 0，键 = 6；在内循环中[<8>, (6), 4, 20, 10]；6 < 8 为真arr[j + 1] = arr[j];，这导致[<8>, (8), 4, 20, 10]. j = -1，内部循环停止并且 arr[j + 1] = key; 将数组变成[(6), 8, 4, 20, 10].

至此，我们知道最小的元素在第一个位置。因此，我们不必在接下来的迭代中考虑它

2. [6, <8>, (4), 20, 10]; 4 < 8 为真，所以让我们将 4 移到 6 之前；-> [(4), 6, 8, 20, 10];

至此，我们知道最小的两个元素在前两个位置。因此，我们不必在下一次迭代中考虑它们

3. [4, 6, <8>, (20), 10]; 20 < 8 false 所以让我们继续；

至此，我们知道最小的三个元素在前三个位置。因此，我们不必在下一次迭代中考虑它们

4. [4, 6, 8, <20>, (10)]; 10 < 20 true 所以让我们将 20 移到 10 -> 之前[4, 6, 8, (10), 20]；

至此，我们知道最小的四个元素在前四个位置。因此，我们不必在下一次迭代中考虑它们

5. i < n为假，我们退出外循环并对数组进行排序。