创建一个函数，它将告诉我们在 C 编程中数组是否已排序

Question

C 编程新手 ^^.

我正在做一项作业，我必须创建一个函数来验证我的数组是否已排序。我必须使用预定义的代码模板并以某种方式解决它。

描述：

让我们创建一个函数来告诉我们数组是否已排序。排序的是什么？ :-)

编写一个函数，将整数数组作为参数（输入）和 returns 布尔值（true/false）。

如果整数数组按 ASC（升序）或 DESC（降序）顺序排序，您的函数应该 return 为真。如果整数数组未排序，您的函数应该 return false。

数字将从 -2_000_000 到 2_000_000 数组可能有重复项。

我必须用这个来解决我的问题。

#ifndef STRUCT_INTEGER_ARRAY
#define STRUCT_INTEGER_ARRAY
typedef struct s_integer_array
{
    int size;
    int* array;
} integer_array;
#endif


bool my_is_sort(integer_array* param_1)
{

}

The inputs that will be used to verify my code:

Exemple 0: 

Input: [1, 1, 2]
Output: 
Return Value: true 

Exemple 1: 
Input: [2, 1, -1]
Output: 
Return Value: true 

Exemple 2: 
Input: [4, 7, 0, 3]
Output: 
Return Value: false 

Exemple 3: 
Input: []
Output: 
Return Value: true

这是我的代码：

#include <stdbool.h>
#ifndef STRUCT_INTEGER_ARRAY
#define STRUCT_INTEGER_ARRAY
typedef struct s_integer_array
{
    int size;
    int* array;
} integer_array;
#endif


bool my_is_sort(integer_array* a)
{
    if (a->size == 1 || a-> size == 0)
    {
        return true;
    }

    int i;
    for (i=0;i<a->size;i++)
    {   //ascending order
        if (a->array[i] <= a->array[i+1]){
            return true;
        }else if (a->array[i] >= a->array[i+1]){
            return true;
        } else {
        return false;
    } 
    }
}

我验证代码的输出： The output failure i get

我的错误在输入 -> 输入：[4, 7, 0, 3] 我的代码 return 为真，而它应该 return 为假。它 return 是真的，因为前两个索引 4 小于 7，所以我的代码假定它是按升序排列的，但我不希望我的代码继续循环到它之前的下一个 return 是一个布尔值。检查 7 之后的数字是否大于 7。但我不知道如何在代码中执行此操作。

谢谢大家！

我知道这对很多人来说可能是个愚蠢的问题，但请帮忙。我是新手，我非常喜欢编程。

Answer 1

Write a function that takes an integer array as a parameter (input) and returns a boolean (true/false).

这个函数的参数

bool my_is_sort(integer_array* a)

不接受整数数组。

在这个for循环中

int i;
for (i=0;i<a->size;i++)
{   //ascending order
    if (a->array[i] <= a->array[i+1]){
        return true;
    }else if (a->array[i] >= a->array[i+1]){
        return true;
    } else {
    return false;
}

只检查类型 struct s_integer_array 对象的数据成员 array 指向的数组的前两个元素。由于 for 循环中的 return 语句，未检查所有其他元素。

我可以建议在下面的演示程序中显示以下简单的函数实现。

#include <stdio.h>
#include <stdbool.h>

bool is_sorted( const int a[], size_t n )
{
    bool sorted = true;
    
    size_t i = 1;
    
    while ( i < n && a[i-1] == a[i] ) ++i;
    
    if ( i < n )
    {
        if ( a[i-1] < a[i] )
        {
            while ( ( ++i < n ) && !( a[i] < a[i-1] ) ) { /* empty */ }
            sorted = i == n;
        }
        else
        {
            while ( ( ++i < n ) && !( a[i-1] < a[i] ) ) { /* empty */ }
            sorted = i == n;
        }
    }
    
    return sorted;
}

int main(void) 
{
    int a1[] = { 1, 1, 2 };
    size_t n = sizeof( a1 ) / sizeof( *a1 );
    
    for ( size_t i = 0; i < n; i++ )
    {
        printf( "%d ", a1[i] );
    }
    putchar( '\n' );
    
    printf( "The array is sorted is %s\n", is_sorted( a1, n ) ? "true" : "false" );
    putchar( '\n' );

    int a2[] = { 2, 1, -1 };
    n = sizeof( a2 ) / sizeof( *a2 );
    
    for ( size_t i = 0; i < n; i++ )
    {
        printf( "%d ", a2[i] );
    }
    putchar( '\n' );
    
    printf( "The array is sorted is %s\n", is_sorted( a2, n ) ? "true" : "false" );
    putchar( '\n' );

    int a3[] = { 4, 7, 0, 3 };
    n = sizeof( a3 ) / sizeof( *a3 );
    
    for ( size_t i = 0; i < n; i++ )
    {
        printf( "%d ", a3[i] );
    }
    putchar( '\n' );
    
    printf( "The array is sorted is %s\n", is_sorted( a3, n ) ? "true" : "false" );
    putchar( '\n' );

    return 0;
}

程序输出为

1 1 2 
The array is sorted is true

2 1 -1 
The array is sorted is true

4 7 0 3 
The array is sorted is false

Answer 2

这就是我处理此类问题的方式。它与您所要求的有所不同且更复杂，但我希望您可以将这个概念应用到您的代码中并完成您的作业。

问题中代码的问题在于它 returns 只比较了给定数组中的前两个值。相反，它需要比较足够多的值来确定值不相等的第一次比较是升序还是降序，然后继续直到比较打破该规则或到达数组末尾。

为此，我使用了一个标志变量来跟踪之前的比较。如果任何比较与先前的结果相反，则数组未排序。如果到达终点但没有找到相反的数组，则对数组进行排序。

我为此使用了 enum，但是 int 的值 0 表示未确定，-1 表示降序，1 表示升序（或您喜欢的任何其他 3 个值）也可以正常工作。

希望这能帮助您完成作业。祝你好运！

#include <stdio.h>

typedef enum
{
    sortUnknown = 0,
    sortAscending,
    sortDescending,
    sortUnsorted
} SortType;

const char *sortNames[] =
{
    "   Unknown",
    " Ascending",
    "Descending",
    "  Unsorted",
};

SortType is_sorted(int* arr, int size)
{
    if (size <= 1)
    {
        return sortUnknown;
    }

    SortType overallSortType = sortUnknown;
    for (int i = 0; i < size - 1; ++i)
    {
        if (arr[i] < arr[i + 1])
        {
            if (overallSortType == sortDescending)
            {
                return sortUnsorted;
            }
            overallSortType = sortAscending;
        }
        else if (arr[i] > arr[i + 1])
        {
            if (overallSortType == sortAscending)
            {
                return sortUnsorted;
            }
            overallSortType = sortDescending;
        }
    }
    return overallSortType;
}

void print(int *arr, int size, SortType st)
{
    printf("%s : ", sortNames[st]);
    for (int i = 0; i < size; ++i)
    {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

int main()
{
    int arr1[] = { 1, 1, 2 };
    SortType st = is_sorted(arr1, 3);
    print(arr1, 3, st);

    int arr2[] = { 2, 1, -1 };
    st = is_sorted(arr2, 3);
    print(arr2, 3, st);

    int arr3[] = { 4, 7, 0, 3 };
    st = is_sorted(arr3, 4);
    print(arr3, 4, st);

    int arr4[] = { 3 };
    st = is_sorted(arr4, 1);
    print(arr4, 1, st);

    int arr5[] = { 1, 1, 1, 1, 2, 2, 2, 3, 4, 5, 6, 6, 6, 6, 7, 8, 9 };
    st = is_sorted(arr5, 17);
    print(arr5, 17, st);

    return 0;
}

演示：https://ideone.com/RkfEWI

输出：

 Ascending : 1 1 2 
Descending : 2 1 -1 
  Unsorted : 4 7 0 3 
   Unknown : 3 
 Ascending : 1 1 1 1 2 2 2 3 4 5 6 6 6 6 7 8 9

Answer 3

此函数将检查数组是否已排序。

#ifndef STRUCT_INTEGER_ARRAY
#define STRUCT_INTEGER_ARRAY
typedef struct s_integer_array
{
    int size;
    int* array;
} integer_array;
#endif

typedef enum
{
    des,
    notdetermined;
    asc;
}SORT_TYPE;


bool my_is_sort(integer_array* a)
{
    bool result = true;
    SORT_TYPE sort = notdetermined; 
    if (a && a -> array && a -> size > 2)
    {
        for(int i = 0; i < a -> size - 1 && result; i++)
        {
            switch(sort)
            {
                case notdetermined:
                    if(a -> array[i] > a -> array[i + 1]) sort = des;
                    else if(a -> array[i] < a -> array[i + 1])) sort = asc;
                    break;
                case asc:
                    if(a -> array[i] > a -> array[i + 1])) result = false;
                    break;
                case des:
                    if(a -> array[i] < a -> array[i + 1])) result = false;
                    break;
            }
        }
    }
    return result;
}

https://godbolt.org/z/xnM7MYz6b

Answer 4

这很简单。检查 ascending/descending 排序是否可以一次性完成。

我们通过两个标志变量来做到这一点，一个用于升序排序[仍然]为真，一个用于降序排序[仍然]为真。

在循环中，如果当前被比较的元素不相等，方向之一必须失序

这里是一些重构代码。注释为：

#include <stdbool.h>

#ifndef STRUCT_INTEGER_ARRAY
#define STRUCT_INTEGER_ARRAY

typedef struct s_integer_array {
    int size;
    int *array;
} integer_array;
#endif

bool
my_is_sort(integer_array *a)
{

    if (a->size <= 1)
        return true;

    int i;

    // true if [still] have ascending sort
    int ascend = 1;

    // true if [still] have descending sort
    int descend = 1;

    // the value of the "previous" array element
    int prev = a->array[0];

    // the value of the "current" array element
    int cur;

    for (i = 1;  i < a->size;  ++i, prev = cur) {
        // early escape -- neither direction is in sort
        if (! (ascend || descend))
            break;

        // get current array value
        cur = a->array[i];

        // compare against previous value
        int dif = cur - prev;

        // elements are the same -- no change in status
        if (dif == 0)
            continue;

        // one of the directions has to be out-of-sort
        if (dif < 0)
            ascend = 0;
        else
            descend = 0;
    }

    return (ascend || descend) ? true : false;
}

更新：

这是一个稍微快一点的版本：

bool
insort_fix1c(integer_array *a)
{
    const int *arr = a->array;
    int size = a->size;

    if (size <= 1)
        return true;

    int i;

    // true if [still] have ascending sort
    int ascend = 1;

    // true if [still] have descending sort
    int descend = 1;

    // the value of the "previous" array element
    int prev = arr[0];

    // the value of the "current" array element
    int cur;

    for (i = 1;  i < size;  ++i, prev = cur) {
        // get current array value
        cur = arr[i];

        // compare against previous value
        int dif = cur - prev;

        // elements are the same -- no change in status
        if (dif == 0)
            continue;

        // one of the directions has to be out-of-sort
        if (dif < 0)
            ascend = 0;
        else
            descend = 0;

        // early escape -- neither direction is in sort
        if ((ascend | descend) == 0)
            break;
    }

    return (ascend | descend) ? true : false;
}

创建一个函数，它将告诉我们在 C 编程中数组是否已排序

Create a Function which will tell us if an array is sorted or not in C programming

c

arrays

sorting

pointers

structure