【算法】编写一个能将给定非负整数列表中的数字排列成最大数字的程序

问题描述：例如，给定[50，2，1,9]，最大数字为95021

问题分析：将输入的数字进行排列组合，使得最终得到的整数是最大的

问题实现需要注意

• 因为需要提取数列中每个数字的首位，并能够和本来的数字建立联系，所以这里采用结构体的知识。
• 有可能存在多个首位数字相同的情况，所以，我们需要对于对这种情况手动编写函数来甄别大小，同时还要采取以首位数字为依据的分片化操作处理数列。

程序代码特点

• 运用结构体知识实现数字联系
• 判断数字是否最大的思想
• 函数之间的调用

C语言代码

#include<stdio.h>
#include<time.h>
#include<Windows.h>
int num[20], number;

struct MyStruct
{
int x, y;
}MyStruct[20], temp_struct;

• 这里使用num[20]这个数组保存数列，number记录数字个数
• MyStruct为结构体名称，x保存数字，y保存首位数字。同时定义了MyStruct[20]，这个结构体数组。temp_struct为结构体数组排序时用的中间变量。

void Random()
{
for (int i = 0; i < 15; i++)
{
num[i] = rand() % 1000;
//scanf("%d", &num[i]);
MyStruct[i].x = num[i];
number += 1;
}
}

• 这里为输入函数。此刻默认生成3位及3位以下的15个随机数为一个数列。
• 将预处理的数组num中的数字保存到MyStruct[i].x里面

/*传入数字x，需要判断位数y，z==1 得到这个数字的总位数。返回分割后的数字*/
int Divide(int x, int y, int z)
{
int substitute_x = x, i = 1;
while (substitute_x>=10) {substitute_x /= 10;i += 1;}
int wei = i;
if (z == 1)
return wei;

for (int i = 1; i <= wei - y; i++) {x /= 10;}

return x;
}

• 这里为一个数字处理函数。
• 实现的功能是：传入数字x，y指需要该函数返回的位数的数字，默认从高位起，倘若z=1，则直接返回该数字总位数。列如：Divide(789,1,0)，则返回7。Divide(789,1,1)，则返回3。

/*分区处理函数,数组的起始位置x，结束位置y*/
void Piece(int x, int y)
{
for (int j = x; j < y ; j++)
{
for (int i = x; i < x + y - j; i++)
{
if (Divide(MyStruct[i].x, 1, 1) > Divide(MyStruct[i + 1].x, 1, 1))
{
if (Divide(MyStruct[i].x, Divide(MyStruct[i + 1].x, 1, 1), 0) < MyStruct[i + 1].x)
temp_struct = MyStruct[i], MyStruct[i] = MyStruct[i + 1], MyStruct[i + 1] = temp_struct;
else if (Divide(MyStruct[i].x, Divide(MyStruct[i + 1].x, 1, 1), 0) == MyStruct[i + 1].x)
{
if (MyStruct[i + 1].x * 10 + Divide(MyStruct[i].x, 1, 0) > Divide(MyStruct[i].x, (Divide(MyStruct[i + 1].x, 1, 1)) + 1, 0))
temp_struct = MyStruct[i], MyStruct[i] = MyStruct[i + 1], MyStruct[i + 1] = temp_struct;
}
}

else if (Divide(MyStruct[i].x, 1, 1) < Divide(MyStruct[i + 1].x, 1, 1))
{
if (MyStruct[i].x < Divide(MyStruct[i + 1].x, Divide(MyStruct[i].x, 1, 1), 0))
temp_struct = MyStruct[i], MyStruct[i] = MyStruct[i + 1], MyStruct[i + 1] = temp_struct;
else if (MyStruct[i].x == Divide(MyStruct[i + 1].x, Divide(MyStruct[i].x, 1, 1), 0))
{
if (MyStruct[i].x * 10 + Divide(MyStruct[i + 1].x, 1, 0) < Divide(MyStruct[i + 1].x, (Divide(MyStruct[i].x, 1, 1)) + 1, 0))
temp_struct = MyStruct[i], MyStruct[i] = MyStruct[i + 1], MyStruct[i + 1] = temp_struct;
}
}

else
{
if (MyStruct[i].x<MyStruct[i+1].x)
temp_struct = MyStruct[i], MyStruct[i] = MyStruct[i + 1], MyStruct[i + 1] = temp_struct;
}
}
}
}

• 这里仅是针对首位相同的数列进行的排列操作。
• Piece(int x, int y):这里的x为数组的首位下标，y为最后一个数字的下标。
• 本文将两个首位相同的数字之间的大小比较做了如下分类:1.前者数字的位数大于后者。2.后者数字的位数大于前者。3.两个数字位数相同。

以前者位数大于后者位数为例进行分析

if (Divide(MyStruct[i].x, 1, 1) > Divide(MyStruct[i + 1].x, 1, 1))
{
if (Divide(MyStruct[i].x, Divide(MyStruct[i + 1].x, 1, 1), 0) < MyStruct[i + 1].x)
temp_struct = MyStruct[i], MyStruct[i] = MyStruct[i + 1], MyStruct[i + 1] = temp_struct;
else if (Divide(MyStruct[i].x, Divide(MyStruct[i + 1].x, 1, 1), 0) == MyStruct[i + 1].x)
{
if (MyStruct[i + 1].x * 10 + Divide(MyStruct[i].x, 1, 0) > Divide(MyStruct[i].x, (Divide(MyStruct[i + 1].x, 1, 1)) + 1, 0))
temp_struct = MyStruct[i], MyStruct[i] = MyStruct[i + 1], MyStruct[i + 1] = temp_struct;
}
}

• Divide(MyStruct[i].x, 1, 1) 引用Divide(int x,int y，int z)函数。传入当前数字MyStruct[i].x，需要判断位数为1位，z=1。说明需要返回MyStruct[i].x数字的位数。

if (Divide(MyStruct[i].x, Divide(MyStruct[i + 1].x, 1, 1), 0) < MyStruct[i + 1].x)

• 这里是将位数较多的那一个数字选取与位数较小的数字的位数与位数较小的数字进行比较。列如：779与78比较。Divide(MyStruct[i].x, Divide(MyStruct[i + 1].x, 1, 1)返回77，MyStruct[i + 1].x为78

temp_struct = MyStruct[i], MyStruct[i] = MyStruct[i + 1], MyStruct[i + 1] = temp_struct;

• 这里是两个结构体变量的交换

else if (Divide(MyStruct[i].x, Divide(MyStruct[i + 1].x, 1, 1), 0) == MyStruct[i + 1].x)
{
if (MyStruct[i + 1].x * 10 + Divide(MyStruct[i].x, 1, 0) > Divide(MyStruct[i].x, (Divide(MyStruct[i + 1].x, 1, 1)) + 1, 0))
temp_struct = MyStruct[i], MyStruct[i] = MyStruct[i + 1], MyStruct[i + 1] = temp_struct;
}

• 当两个返回值相同时怎么办？比如：778和77

if (MyStruct[i + 1].x * 10 + Divide(MyStruct[i].x, 1, 0) > Divide(MyStruct[i].x, (Divide(MyStruct[i + 1].x, 1, 1)) + 1, 0))

• 这条语句即是精华部分。意思是：将77*10得到770再加上778的首位7，得到777，然后与778比较。

/*处理函数*/
void Operate()
{
for (int i = 0; i < number; i++) { MyStruct[i].y = Divide(num[i], 1, 0); }

for (int j = 0; j < number - 1; j++)
{
for (int i = 0; i < number - 1 - j; i++)
{
if (MyStruct[i].y < MyStruct[i + 1].y)
temp_struct = MyStruct[i], MyStruct[i] = MyStruct[i + 1], MyStruct[i + 1] = temp_struct;
}
}
for (int i = 0; i < number;)
{
int get = MyStruct[i].y, xx = i;

while (MyStruct[i].y == get)
i++;

int yy = i - 1;
Piece(xx, yy);
}
}

• 这个函数的目的是得到不同数字的首位，并从大到小排序，并针对相同首位进行分片，并传入Piece()

for (int i = 0; i < number; i++) { MyStruct[i].y = Divide(num[i], 1, 0); }

• 调用Divide函数，将预处理的数组num中的数字的首位保存到MyStruct[i].y里面。

for (int j = 0; j < number - 1; j++)
{
for (int i = 0; i < number - 1 - j; i++)
{
if (MyStruct[i].y < MyStruct[i + 1].y)
temp_struct = MyStruct[i], MyStruct[i] = MyStruct[i + 1], MyStruct[i + 1] = temp_struct;
}
}

• 这里用到了冒泡排序，将首位数字从大到小排序

for (int i = 0; i < number;)
{
int get = MyStruct[i].y, xx = i;

while (MyStruct[i].y == get)
i++;

int yy = i - 1;
Piece(xx, yy);
}

• 将同一片的数据首尾下标传入Piece中处理。

void Print()
{
for (int i = 0; i < number; i++)
printf("%d ", MyStruct[i].x);
printf("\n---------------------------------------------\n");
}

• 打印函数

int main()
{
for (int i = 0; i < 100 ; i++)
{
Random();
Operate();
Print();
number = 0;
}
return 0;
}

• 主函数。这里要注意，如果使用随机生成方式。number=0语句很重要。