c - 双向插入排序

Question

我正在尝试遵循以下条件的2种方式进行插入排序：


数组的第一个元素应放置为中间元素。
一旦数组中有一组连续的元素，则通过将所有较小的元素向左移动一个步骤，或将所有较大的元素向右移动一个步骤，来为新元素留出空间，并且每次都应对新元素进行比较和排序。


但是我无法从两边获得越来越大的元素。您的建议将不胜感激

我尝试使用2个数组。假设a和b是2个数组。我将a[0]放在b[mid]中，其中mid是数组b的中间元素，并将数组a的所有元素与b[mid]进行了比较，并尝试增加和减少。

我现在面临的问题是，如果将输入指定为5 6 7 4 3，则输出将变为3 4 5 6 7。但是，如果我将输入交换为5 7 6 3 4，则输出将为0 3 5 7 0。它超出范围了。我希望这是我没有得到的排序数组。任何人都可以帮助我，如何将逻辑用于排序以及不超出范围。

#include <stdio.h>

void main() {
    int a[20] = { 0 };
    int b[20] = { 0 };
    int mid1, mid2, n, i, low, high;

    printf("\nEnter Size of the array:\n");
    scanf("%d", &n);
    printf("Enter Array elements");

    for (i = 0; i < n; i++) {
        scanf("%d", &a[i]);
    }
    printf("Elements before sorting:");
    for (i = 0; i < n; i++) {
        printf("%d\t", a[i]);
    }
    low = 0;
    high = n;
    mid1 = (low + high) / 2;
    mid2 = (low + high) / 2;
    b[mid1] = a[0];

    printf("\n The middle element is : %d", b[mid1]);
    for (i = 1; i < n; i++) {
        if (a[i] <= b[mid1]) {
            mid1 = mid1 - 1;
            b[mid1] = a[i];
        }
    }
    b[mid2] = a[0];
    for (i = 1; i < n; i++) {
        if (a[i] > b[mid2]) {
            mid2 = mid2 + 1;
            b[mid2] = a[i];
        }
    }
    printf("\nSecond array is :");
    for (i = 0; i < n; i++) {
        printf("%d\t", b[i]);
    }
}

Answer 1

您的算法不起作用：


如果超过一半的数组元素与任一比较匹配，则将发生此情况，因为该数组已经在任一方向上进行了排序，则您将尝试存储超出b边界的元素。
一旦在b中有2个元素，则其他任何值在这2个元素之间的元素将根本不会存储到b中。


插入排序通常是在原地执行的，但是这是代码的修改版本，它在b中生成带有插入排序变体的排序数组：

#include <stdio.h>

int main() {
    int a[20], b[20];
    int n, i, j;

    printf("Enter Size of the array: ");
    if (scanf("%d", &n) != || n < 1 || n > 20)
        return 1;

    printf("Enter Array elements: ");
    for (i = 0; i < n; i++) {
        if (scanf("%d", &a[i]) != 1)
            return 1;
    }
    printf("Elements before sorting:");
    for (i = 0; i < n; i++) {
        printf("\t%d", a[i]);
    }
    printf("\n");

    b[0] = a[0];
    for (i = 1; i < n; i++) {
        int t = a[i];
        for (j = i; j > 0 && dest[j - 1] > t; j--) {
            b[j] = b[j - 1];
        }
        b[j] = t;
    }

    printf("Sorted array is:");
    for (i = 0; i < n; i++) {
        printf("\t%d", b[i]);
    }
    printf("\n");
    return 0;
}