今天闲得无聊，写了道题，写完后，我发现这道题让我对排序有了更加深刻的认识，如今在看来，排序的核心主要有两点：

  • 比较函数（也就是比较的结果），决定了以何种方式进行排序：从大到小抑或是从小到大，甚至是其他更为特殊的方式
  • 比较次数（也就是比较的方式），决定了排序的时间复杂度，也就是说，要想降低排序的时间复杂度，其重点就在于减少排序的次数。

排序总述

排序，在我看来，就是以给定的规则，对一组数（或者字符）进行重新排列，而规则是可变的，比如我们日常使用的：从大到小的顺序，从小到大的顺序，字典序等等等等。

那么，从底向上看排序，其最核心的部分，就在于两两比较，通过比较，就能确定两两之间的相对顺序——即谁先谁后。

而排序的效率，则取决于比较次数的多少，比如我们可以通过不重复比较，或者一些特殊的比较方式来缩短时间复杂度。

比较函数

总述

什么是比较函数？抽象来说，就是比较两个数，并确定其先后顺序的函数；具体来说，就是C语言 qsort() 函数中的 cmp 参数，是 java 中 Arrays.sort() 方法中的 Comparator 参数。

比较函数的一般写法是，对传入的两个参数（a, b）进行比较：

  • a 大于 b 返回 1
  • a 大于 b 返回 -1
  • a 大于 b 返回 0

规则进行返回，通过控制两个参数的传入，来控制从大到小排列或者从小到大排列。

比较

比较可以自己写规则，比如最为简单的数字的 从大到小，从小到大 等等，但是一些时候就不仅仅是简单的的从大到小或是从小到大了，比如我今天写的这个题（leetcode 179）：

题目如下：

给定一组非负整数，重新排列它们的顺序使之组成一个最大的整数。

示例 1:

1
2
输入: [10,2]
输出: 210

示例 2:

1
2
输入: [3,30,34,5,9]
输出: 9534330

说明: 输出结果可能非常大，所以你需要返回一个字符串而不是整数。

题目解答：

这题本质是一个排序问题，而排序的方式不再是简单的数字排序：

  • 数字从大到小排序：98 肯定在 9前面，但是此题则应该将顺序置反
  • 数字从小到大排序：2 肯定在 42 前面，但是此题则应该将顺序置反

所以此题的比较不能够按照常规方式写，而我们可以按照字符串的字典序来看，也就是说，将两个数字拼接，比较两种拼接方式的大小，从而选择排列顺序，比如：98 和 9

  • 两个数只有两种拼接方式：998 明显大于 989 ，所以 9 应该在 98 前面

便是以此种方式，来进行排序，排序后，将之依次拼贴为一字符串即可, java代码（参考了 leetcode 官方题解）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
     private class LargerNumberComparator implements Comparator<String> {
        @Override
        public int compare(String a, String b) {
            String order1 = a + b;
            String order2 = b + a;
            return order2.compareTo(order1);
        }
    }
    
    public String largestNumber(int[] nums) {
        String[] numsString = new String[nums.length];
        for (int i = 0; i < nums.length; i++)
            numsString[i] = String.valueOf(nums[i]);
        
        Arrays.sort(numsString, new LargerNumberComparator());
        
        if (numsString[0].equals("0"))
            return "0";
        
        String ret = new String();
        for (String numString:numsString)
            ret += numString;   
        return ret;
    }    
}

比较次数

这部分内容不算是重点，所以，大致说明即可：

  • 冒泡排序，每次循环都会比较，所以几乎每两个数字间都会进行比较，所以其时间复杂度为 \(O(N^2)\)
  • 而比较高级的排序，比如归并，快排甚至桶排，都是降低了比较次数，从而降低了时间复杂度；