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

Question

我正在尝试反转 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;
}

Answer 1

您应该在 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