【剑指offer-Java版】33把数组排成最小的数

本文主要是介绍【剑指offer-Java版】33把数组排成最小的数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

把数组排成最小的数

难点在于比较规则的确定以及比较规则的正确性证明
比如：仅仅是局部的两个数字的顺序较小，如何保证整个数组按此规则进行排序后达到全局的较小
书中关于这一点的证明直接用的反证法，忘的差不多了

public class _Q33<T> {public void PrintMinNumber(int nums[]){if(nums == null) return;Sort(nums, 0, nums.length - 1);for(int i=0; i<nums.length; i++)System.out.print(nums[i]);System.out.println();}// 基于快排的排列方式public void Sort(int nums[], int start, int end){if(nums == null) return;if (start < end) {int judge = nums[end];int small = start;for (int i = start; i < end; i++) {// 降序if (SmallThan(String.valueOf(nums[i]), String.valueOf(judge))) {int temp = nums[i];nums[i] = nums[small];nums[small] = temp;small++;}}nums[end] = nums[small];nums[small] = judge;Sort(nums, start, small - 1);Sort(nums, small + 1, end);}}// 比较规则： mn < nm 那么返回true 否则falseprivate boolean SmallThan(String m, String n){if(m == null || n == null) return false;String mn = m + n;String nm = n + m;for(int i=0; i<mn.length(); i++){if(mn.charAt(i) < nm.charAt(i)){ // 小于 truereturn true;}else if(mn.charAt(i) > nm.charAt(i)){ // 大于 falsereturn false;}// 其他 continue}return false;}}

测试代码：

public class _Q33Test extends TestCase {_Q33 min = new _Q33();public void test(){int nums1[] = {3, 32, 321};min.PrintMinNumber(nums1);int nums2[] = {1, 2, 5, 4, 3};min.PrintMinNumber(nums2);}}

这篇关于【剑指offer-Java版】33把数组排成最小的数的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---