首页 > 代码库 > 整数数组排序--各个元素拼接所得结果最小

整数数组排序--各个元素拼接所得结果最小

总之将相邻的两个数m、n进行比较大小的方法修改为mn和nm比较大小即可

#include "stdafx.h"
#include <time.h>
#include <stack>
#include <string>
#include <iostream>
using namespace std;

bool comp(int num1,int num2)
{
	int temp1=num1;
	int temp2=num2;
	int sum1=num1;
	int sum2=num2;

	if(num1+num2==91)
	{
		num1=num1;
	}

	while(temp2!=0)
	{
		sum1*=10;
		temp2/=10;
	}
	sum1+=num2;
	while(temp1!=0)
	{
		sum2*=10;
		temp1/=10;
	}
	sum2+=num1;

	if(sum1<=sum2)
	{
		return true;
	}
	else
	{
		return false;
	}
}

void merge(int *s,int start,int med,int end)
{
	int i=start;
	int j=med+1;
	int k=0;
	int* temp=new int[end-start+1];

	while(i<med+1 && j<=end)
	{
		if(comp(s[i],s[j]))
		{
			temp[k++]=s[i];
			i++;
		}
		else
		{
			temp[k++]=s[j];
			j++;
		}
	}

	if(i<med+1)
	{
		while(i<med+1)
		{
			temp[k++]=s[i];
			i++;
		}
	}
	if(j<=end)
	{
		while(j<=end)
		{
			temp[k++]=s[j];
			j++;
		}
	}

	for(k=0;k<=end-start;k++)
	{
		s[start+k]=temp[k];
	}
	delete temp;
	return;
}

void mergeSort(int*s,int start,int end)
{
	if(start<end)
	{
		int med=(start+end)/2;
		mergeSort(s,start,med);
		mergeSort(s,med+1,end);
		merge(s,start,med,end);
	}
	return;
}

void showSet(int *s,int n)
{
	for(int i=0;i<n;i++)
	{
		cout<<s[i]<<" ";
	}
	cout<<endl;
}

int main()
{
	int s[5]={3,83,8,13,1};

	showSet(s,5);
	mergeSort(s,0,4);
	showSet(s,5);

	 system("pause");
	 return 0;
}


整数数组排序--各个元素拼接所得结果最小