c语言 - 如何对一个下降然后上升的数组进行排序，以对一直下降的数组进行排序?

Question

我有一个任务来创建一个函数，该函数将向下然后上升的数组(例如：9, 8, 7, 6, 5, 7, 11, 13)排序为一直向下的数组(例如：13, 11, 9, 8, 7, 7, 6, 5)。

我在在线编译器(programiz)中写了这个，但它对我不起作用。

#include <stdio.h>
#include <stdlib.h>
#define N 10
void sort_dec_inc(int a[], int n) {
int pivot, i, q = 0;
int c[n];
for (i=0; i<n; i++) {
c[i] = 0;
}
for (i=0; i<n-1; i++) {
if (a[i]<a[i+1]) {
pivot=i+1;
break;
}
}
if (pivot == n-1) {
return;
}
for (i=0; i<pivot && n>=pivot; q++) {
if (a[i]>=a[n]) {
c[q] = a[i];
i++;
}
else {
c[q] = a[n];
n--;
}
}


if (n==pivot) {
while(i<pivot) {
c[q] = a[i];
q++;
i++;
}
}
else {
while (n>=pivot) {
c[q] = a[n];
q++;
n--;
}
}

for(i=0; i<n; i++) {
a[i] = c[i];
}


}
int main()
{
int num_arr[N] = {9, 7, 5, 3, 1, 2, 4, 6, 8, 10};
sort_dec_inc(num_arr, N);
int i;
for(i = 0; i < N; i++) {
printf("%d ", num_arr[i]);
}
return 0;
}

输出(大多数时候)：9 7 5 3 1 2 4 6 8 10

有时输出是不同的，例如：(410878976 10 9 8 1 2 4 6 8 10)

如果有人可以用简单的代码回答，那是最好的，我还不明白 C 中的所有选项。

(如果这是一个笨拙的代码，我很抱歉，我是新手。 多谢！

Answer 1

基于以下注释的解决方案：

#include <stdio.h>
#include <stdlib.h>
#define N 10
void sort_dec_inc(int a[], int n) {
int left, i = 0;
int right = n-1;
int c[n];
while (i<n) {
if (a[left] >= a[right]) {
c[i] = a[left];
left++;
}
else {
c[i] = a[right];
right--;
}
i++;
}

for(i=0; i<n; i++) {
a[i] = c[i];
}

}
int main()
{
int num_arr[N] = {9, 7, 5, 3, 1, 2, 4, 6, 8, 10};
sort_dec_inc(num_arr, N);
int i;
for(i = 0; i < N; i++) {
printf("%d ", num_arr[i]);
}
return 0;
}

输出：10 9 8 7 5 5 4 3 2 1

Answer 2

对于初学者来说，定义一个辅助可变长度数组是一个坏主意。这种方法是不安全的，因为程序可以报告没有足够的内存来分配数组。

至少这个代码片段

for (i=0; i<n-1; i++) {
if (a[i]<a[i+1]) {
pivot=i+1;
break;
}
}
if (pivot == n-1) {
return;
}

包含逻辑错误。

考虑一个仅包含两个元素的数组{ 1, 2 }。在这种情况下，a[0]小于a[i+1]小于a[1]。所以 if 语句的条件

if (pivot == n-1) {
return;
}

计算结果为逻辑 true，并且该函数返回控件，尽管数组未按降序排序。它保持不变。

或者考虑这个代码片段

if (a[i]>=a[n]) {
c[q] = a[i];
i++;
}

表达式a[n]访问数组之外的内存，从而导致未定义的行为。

一种简单的方法是使用方法插入排序。

这是一个演示程序。

#include <stdio.h>
#include <string.h>
void insertion_sort( int a[], size_t n )
{
size_t i = 1;
while ( i < n && !( a[i-1] < a[i] ) ) i++;
for ( ; i < n; i++ )
{
size_t j = i;
while ( j != 0 && a[j-1] < a[i] ) --j;
if ( i != j )
{
int tmp = a[i];
memmove( a + j + 1, a + j, ( i - j ) * sizeof( int ) );
a[j] = tmp;
}
}
}
int main( void )
{
int a[] = { 9, 7, 5, 3, 1, 2, 4, 6, 8, 10 };
const size_t N = sizeof( a ) / sizeof( *a );
for ( size_t i = 0; i < N; i++ )
{
printf( "%d ", a[i] );
}
putchar( 'n' );
insertion_sort( a, N );
for ( size_t i = 0; i < N; i++ )
{
printf( "%d ", a[i] );
}
putchar( 'n' );
}

程序输出为

9 7 5 3 1 2 4 6 8 10 
10 9 8 7 6 5 4 3 2 1 

Answer 3

我会推荐一个气泡排序。 这是一种按数字顺序对数字进行排序的简单方法：

for (int i = 0; i < quant; i++)
{
for (int j = 0; j < quant-1; j++)
{
if (Array[j] < Array[j + 1])
{
int temp = Array[j];
Array[j] = Array[j + 1];
Array[j + 1] = temp;
}
}
}

quant是要排序的数字数量。 不要忘记为排序过程定义一个长度quant的整数数组。

要访问数组，只需使用 for 循环返回所有结果。