尝试实现插入排序公司

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

Answer 1

这篇source总结了插入排序算法的步骤如下：

Algorithm : To sort an array of size n in ascending order:
1: Iterate from arr[1] to arr[n] over the array.
2: Compare the current element (key) to its predecessor.
3: If the key element is smaller than its predecessor, compare it to the elements before. Move the greater elements one position up to make space for the swapped element.

你做对的第一步：

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]。否则，您将访问数组 ar

的位置 -1

剧透

insertion sort 的可能实现如下所示：

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]（密钥由 '()' 表示）

i = 1, j = 0, key = 6;在内循环中[<8>, (6), 4, 20, 10]； 6 < 8 true arr[j + 1] = arr[j]; 导致 [<8>, (8), 4, 20, 10]。 j = -1，内层循环停止，arr[j + 1] = key；将数组变成 [(6), 8, 4, 20, 10].

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

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

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

[4, 6, <8>, (20), 10]； 20 < 8 false 让我们继续；

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

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

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

i < n为false，退出外层循环，对数组进行排序。

尝试实现插入排序公司

Trying to implement insertion sort inc

c

algorithm

sorting

insertion-sort