algorithm - 插入方向相反。右侧的已排序部分，左侧的未排序

我正在尝试反转clr中描述的插入排序逻辑中的已排序部分和未排序部分。输出完全错误。有人能指出我代码中的错误或逻辑错误吗。

#include<stdio.h>
#include<stdlib.h>

int main()
{   int a[] = {67,7,3,2,1,9,45,5};
    int k;
    int n = sizeof(a)/sizeof(a[0]);
    insert(a,n);
    for(k = 0;k < n; k++)
        printf("%d %d\n",k,a[k]);
    return 0;
}

void insert(int *a,int n)
{
    int i,j,val;
    for(i=n-2;i>=0;i--){
        val=a[i];
        for(j=i+1;j<n && a[j]<val;j++){
            a[j-1]=a[j];
        }
        a[j--]=val;
}

最佳答案

您应该在a[j - 1]处插入最后一个元素。可以使用减量来实现这一点，但在这种情况下，必须使用前缀减量，这将在引用该值之前更改该值：a[--j] = val;。
以下是更正版本：

void insertion_sort_backwards(int *a, int n)
{
    int i = n - 1;

    while (i--) {
        int val = a[i];
        int j;

        for (j = i + 1; j < n && a[j] < val; j++) {
            a[j - 1] = a[j];
        }

        a[j - 1] = val;
    }
}

这将从右侧对数组进行排序：

67, 7, 3, 2, 1, 9, 5, 45
67, 7, 3, 2, 1, 5, 9, 45
67, 7, 3, 2, 1, 5, 9, 45
67, 7, 3, 1, 2, 5, 9, 45
67, 7, 1, 2, 3, 5, 9, 45
67, 1, 2, 3, 5, 7, 9, 45
1, 2, 3, 5, 7, 9, 45, 67

关于algorithm - 插入方向相反。右侧的已排序部分，左侧的未排序，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/34736486/