剑指offer面试题33 把数组排成最小的数

考察点

大数，快排

知识点

题目

分析
本题目给一个整型数组，要求他能排出来的最小的数字。这道题目我们大可以通过排列的方式枚举出所有的数字然后求一个最小的，只不过这种方式时间复杂度非常高。接下来我们通过举例的方式观察我们的思维和数字规律：假如数组有3个元素12，23，34，我们的正常思路肯定是依次遍历元素，观察俩俩元素之间谁放在前面组成的数字更小就把哪个元素放在那个元素的前面，比如我们发现1234要比3412小，所以12这个元素肯定在34的前面，所以其实这就是个快排的思维，只不过比较元素的方式变了，不再是简单的直接比较俩个元素的大小，而是比较俩个元素拼接后的大小。同时一定要注意数组元素是int类型，拼接以后不排除溢出，所以整个算法都需要用对应的string类型来实现

interface CompareFunctionInterface {
	public boolean compare(String a,String b);
}
public class CompareFunction implements CompareFunctionInterface {
	@Override
	public boolean compare(String a,String b) {
		if (a.compareTo(b) >= 0) {
			return true;
		}
		return false;
	}
}
public class ThirtyThree {
	public static void main(String[] args) {
		int arr[] = {3,32,321};
		getMin(arr);
	}
	public static void getMin(int[] arr) {
		if (arr == null || arr.length <= 0) {
			return;
		}
		String[] str = new String[arr.length];
		for (int i = 0;i<arr.length;i++) {
			str[i] = String.valueOf(arr[i]);
		}
		CompareFunction compareFunction = new CompareFunction();
		quickSort(str,0,arr.length-1,compareFunction);
		String res = "";
		for (int i = 0;i<arr.length;i++) {
			res = res + str[i];
		}
		System.out.println(res);
	}
	static void quickSort(String[] arr,int start,int end,CompareFunctionInterface func) {
		if (end <= start) {
			return;
		}
		int mid = partition(arr,start,end,func);
		quickSort(arr,start,mid-1,func);
		quickSort(arr,mid+1,end,func);
	}
	static int partition(String[] arr,int start,int end,CompareFunctionInterface func) {
		String privot = arr[end];
		int index = start - 1;
		for (int i = start;i<end;i++) {
			if (func.compare(arr[i],privot)) {
				index ++;
				String tmp = arr[i];
				arr[i] = arr[index];
				arr[index] = tmp;
			}
		}
		arr[end] = arr[index + 1];
		arr[index + 1] = privot;
		return index + 1;
	}
}