C程序对两个连续数组元素的差进行升序排序

Question

我需要编写一个程序，以升序对连续数组元素的差异进行排序。例如:第一个和第二个元素之间的差异最小，第二个和第三个元素之间的差异较大，依此类推。我无法想出一个好的算法来以所需的方式对数组进行排序。我唯一想到的是交换两个元素的位置，然后如果顺序不正确，再次切换并保持它直到排序。我很确定它也执行得不好。

这是我的代码:

#include<stdio.h>
void InputArray(int a[], int size);
void PrintArray(int a[], int size);
void sort(int a[], int size);

void main(){
    int a[100], i, n;
do{
    printf("Number of elements: ");
    scanf("%d", &n);
} while (n < 1 || n > 100);

InputArray(a, n);
sort(a, n);
PrintArray(a, n);
printf("\n");
}

void InputArray(int a[], int size){
    printf("Enter array elements:\n");
for (int i = 0; i < size; i++)
    scanf("%d", &a[i]);
}
void sort(int a[], int size){
    int i, temp;
for (i = 0; ;i++){
    if ((a[i] - a[i + 1]) < (a[i + 1] - a[i + 2]))
        break;
    temp = a[i];
    a[i] = a[i + 1];
    a[i + 1] = temp;

    if (i == size - 1){
        temp = a[size - 1];
        a[size - 1] = a[0];
        a[0] = temp;
        i = -1;
    }
 }
 }
  void PrintArray(int a[], int size){
    printf("Sorted array:\n");
    for (int i = 0; i < size; i++)
    printf("%d ", a[i]);
}

示例输出:

 Number of elements: 4
 Enter array elements:
 1 3 7 12
 Sorted array:
 1 7 12 3

但是我在测试过程中得到了 3 1 7 12。

Answer 1

起点可以是创建一个包含所有元素之间的所有差异的 N^2 2D 矩阵，然后使用回溯解决方案。

您有一组已采用的元素和候选元素。最初采取= []候选人=[1,3,7,12]

您选择两个元素来创建第一个差异。然后选择满足升序要求的第三个元素。

如果找到，则继续，如果没有找到，则停止并返回到可以更改所取元素的位置。

如果您找到了满足要求的解决方案，则将其返回，否则您将继续搜索搜索空间。