c - 在 C 中按升序对数组的前 k 个元素进行排序，其余元素按降序排序

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 时第二个(排序递减)循环的限制。

此代码采用问题中的 Material 并创建代码的检测版本。

#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 个两位数值进行了测试。

错误跟踪

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 

固定轨迹

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 

请注意，明智的打印如何使问题变得容易发现，并且修复是有效的。

极端情况(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