按升序对数组的第1个k元素进行排序，并在C中按降序排列[关闭]

Question

这是按递增顺序排列数组的代码：

for(i=0; i<k-1; i++)
    {
        xchanges = 0;
        for(j=0; j<k-1-i; j++)
        {
            if(arr[j] > arr[j+1])
            {
                temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
                xchanges++;
            }
        }
        if(xchanges == 0)
            break;
    }

这是按递减顺序排列数组的代码：

for(i=k; i<n-1; i++)
    {
        xchanges = 0;
        for(j=k; j<n-1-i; j++)
        {
            if(arr[j] < arr[j+1])
            {
                temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
                xchanges++;
            }
        }
        if(xchanges == 0)
            break;
    }

这两个部件在整个阵列上都能正常工作。但是当代码一个接一个地放置时，代码的第二部分就不起作用了。这两个片段在sort_array()。这是从这样的主函数调用的：

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

int main(void)
{
    int *arr, n, i, k;
    scanf("%d %d", &n, &k);
    arr = (int*)malloc(n*sizeof(int));
    for(i=0; i<n; i++)
    {
        scanf("%d", &arr[i]);
    }
    int* res = sort_array(arr,n,k);
    for(i=0; i<n; i++)
    {
        printf("%d ", res[i]);
    }
    return 0;
}

Answer 1

当k既不是0也不是n时，问题在于第二个（排序减少）循环的限制。

此代码获取问题中的材料并创建代码的检测版本。

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

static void sort_array(int *arr, int n, int k)
{
    int i;
    int j;
    int xchanges;
    int temp;
    printf("n = %d; k = %d\n", n, k);

    for (i = 0; i < k; i++)
    {
        printf("Loop 1: i = %d (L = %d)\n", i, k - 1 - i);
        xchanges = 0;
        for (j = 0; j < k - 1 - i; j++)
        {
            if (arr[j] > arr[j + 1])
            {
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                xchanges++;
            }
        }
        if (xchanges == 0)
            break;
    }

    printf("n = %d; k = %d\n", n, k);
    for (i = k; i < n; i++)
    {
        printf("Loop 2: i = %d (L = %d)\n", i, n - 1 - i);
        xchanges = 0;
        // for (j = k; j < n - 1 - i; j++)      // Buggy!
        for (j = k; j < n - 1 - i + k; j++)     // Fixed!
        {
            if (arr[j] < arr[j + 1])
            {
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
                xchanges++;
            }
        }
        if (xchanges == 0)
            break;
    }
    printf("n = %d; k = %d\n", n, k);
}

static void dump_array(const char *tag, int n, int *arr)
{
    printf("%s:\n", tag);
    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);
    putchar('\n');
}

int main(void)
{
    int *arr, n, i, k;
    scanf("%d %d", &n, &k);
    arr = (int *)malloc(n * sizeof(int));
    for (i = 0; i < n; i++)
    {
        scanf("%d", &arr[i]);
    }

    dump_array("Before", n, arr);
    sort_array(arr, n, k);
    dump_array("After", n, arr);

    return 0;
}

错误修复已明确标记。我使用随机数生成器测试但是使用固定种子，在10到99之间的20个两位数值的集合上。

Buggy trace

Before:
15 31 62 60 42 24 38 73 52 13 23 47 36 28 54 62 19 99 68 73 
n = 20; k = 10
Loop 1: i = 0 (L = 9)
Loop 1: i = 1 (L = 8)
Loop 1: i = 2 (L = 7)
Loop 1: i = 3 (L = 6)
Loop 1: i = 4 (L = 5)
Loop 1: i = 5 (L = 4)
Loop 1: i = 6 (L = 3)
Loop 1: i = 7 (L = 2)
Loop 1: i = 8 (L = 1)
Loop 1: i = 9 (L = 0)
n = 20; k = 10
Loop 2: i = 10 (L = 9)
n = 20; k = 10
After:
13 15 24 31 38 42 52 60 62 73 23 47 36 28 54 62 19 99 68 73 

Fixed trace

Before:
15 31 62 60 42 24 38 73 52 13 23 47 36 28 54 62 19 99 68 73 
n = 20; k = 10
Loop 1: i = 0 (L = 9)
Loop 1: i = 1 (L = 8)
Loop 1: i = 2 (L = 7)
Loop 1: i = 3 (L = 6)
Loop 1: i = 4 (L = 5)
Loop 1: i = 5 (L = 4)
Loop 1: i = 6 (L = 3)
Loop 1: i = 7 (L = 2)
Loop 1: i = 8 (L = 1)
Loop 1: i = 9 (L = 0)
n = 20; k = 10
Loop 2: i = 10 (L = 9)
Loop 2: i = 11 (L = 8)
Loop 2: i = 12 (L = 7)
Loop 2: i = 13 (L = 6)
Loop 2: i = 14 (L = 5)
Loop 2: i = 15 (L = 4)
Loop 2: i = 16 (L = 3)
Loop 2: i = 17 (L = 2)
Loop 2: i = 18 (L = 1)
n = 20; k = 10
After:
13 15 24 31 38 42 52 60 62 73 99 73 68 62 54 47 36 28 23 19 

请注意，明智的打印如何轻松发现问题，并且修复工作正常。

Extreme cases (k = 0, k = 20)

在k = 0和k = 20（又名n）的极端情况下，固定版本和未固定版本都产生相同的输出。

Before:
15 31 62 60 42 24 38 73 52 13 23 47 36 28 54 62 19 99 68 73 
n = 20; k = 20
Loop 1: i = 0 (L = 19)
Loop 1: i = 1 (L = 18)
Loop 1: i = 2 (L = 17)
Loop 1: i = 3 (L = 16)
Loop 1: i = 4 (L = 15)
Loop 1: i = 5 (L = 14)
Loop 1: i = 6 (L = 13)
Loop 1: i = 7 (L = 12)
Loop 1: i = 8 (L = 11)
Loop 1: i = 9 (L = 10)
Loop 1: i = 10 (L = 9)
Loop 1: i = 11 (L = 8)
Loop 1: i = 12 (L = 7)
Loop 1: i = 13 (L = 6)
Loop 1: i = 14 (L = 5)
n = 20; k = 20
n = 20; k = 20
After:
13 15 19 23 24 28 31 36 38 42 47 52 54 60 62 62 68 73 73 99 

Before:
15 31 62 60 42 24 38 73 52 13 23 47 36 28 54 62 19 99 68 73 
n = 20; k = 0
n = 20; k = 0
Loop 2: i = 0 (L = 19)
Loop 2: i = 1 (L = 18)
Loop 2: i = 2 (L = 17)
Loop 2: i = 3 (L = 16)
Loop 2: i = 4 (L = 15)
Loop 2: i = 5 (L = 14)
Loop 2: i = 6 (L = 13)
Loop 2: i = 7 (L = 12)
Loop 2: i = 8 (L = 11)
Loop 2: i = 9 (L = 10)
Loop 2: i = 10 (L = 9)
Loop 2: i = 11 (L = 8)
Loop 2: i = 12 (L = 7)
Loop 2: i = 13 (L = 6)
Loop 2: i = 14 (L = 5)
Loop 2: i = 15 (L = 4)
Loop 2: i = 16 (L = 3)
Loop 2: i = 17 (L = 2)
n = 20; k = 0
After:
99 73 73 68 62 62 60 54 52 47 42 38 36 31 28 24 23 19 15 13