排序

一：剑指45把数组组成最小的数。

1.题目描述

2.代码

自己暴力

这个代码没有参考意义，因为不会使用sort和自己写关于字符串的比较怎么比价的排序算法，算是暴力破解的。

class Solution {
public:
    string minNumber(vector<int>& nums) {
        vector<string> arr;
        for (int i = 0; i < nums.size(); i++)
        {
            arr.push_back(to_string(nums[i]));
        }
        sort(arr.begin(), arr.end());
        string str = "";
        for (int i = 1; i < nums.size(); i++)
        {
            if((arr[i - 1] + arr[i]).size() > 10) {
                // 防止两个数字太大，int最多10位，
                //超过10位截断，下面的if很可能不应该进去，反而进去了，必须提前杜绝过大的数字
                continue;
            }
            int a = atoi((arr[i - 1] + arr[i]).c_str());
            // atoi函数接收的参数必须是c字符数组的形式，所以必须c_str函数把cpp字符串变成字符数组，
            //传给atoi
            int b = atoi((arr[i] + arr[i - 1]).c_str());
            if (a > b) {
                for (int j = 0; j <= i; j++) // 3----3 --- 30,30一定得到第一个3的前面才行
                {
                    if (arr[i - 1] == arr[j]) 
                    {
                        swap(arr[j], arr[i]);
                        break;
                    }
                } 
            }
        }
        for (int i = 0; i < arr.size(); i++)
        {
            str += arr[i];
        }
        return str;
    }
};

自己排序的版本：

• 其实自己写关于字符串的排序比较，最难的地方就是不明白如何排序，根据什么排序。如何定义大于和如何定义小于。https://leetcode-cn.com/problems/ba-shu-zu-pai-cheng-zui-xiao-de-shu-lcof/solution/mian-shi-ti-45-ba-shu-zu-pai-cheng-zui-xiao-de-s-4/
• 上面的网址说的很清楚怎么比较，其实sort第三个参数写的时候，也得明白上面网址的原理，不然还是不会写，所以自己才用上面比较麻烦的。

• K神是上交大的，上面网址就是他写的

  class Solution {
  public:
    string minNumber(vector<int>& nums) {
        vector<string> arr;
        for (int i = 0; i < nums.size(); i++)
        {
            arr.push_back(to_string(nums[i]));
        }
        quick_sort(arr, 0, arr.size() - 1);
        string str = "";
        for (int i = 0; i < arr.size(); i++)
        {
            str += arr[i];
        }
        return str;
    }
    void quick_sort(vector<string>& arr, int l, int r)
    {
        if (l >= r) return;
        int i = l - 1, j = r + 1;
        string x = arr[i + j >> 1];
        while (i < j)
        {
            while (arr[++i] + x < x + arr[i]);
            while (arr[--j] + x > x + arr[j]);
            if (i < j) swap(arr[i], arr[j]);
        }
        quick_sort(arr, l, j);
        quick_sort(arr, j + 1, r);
    }
  };

• 研究sort函数,sort函数第三个参数的构造，之前在结构体上见过那种特殊的排序，题目在y总第五章贪心算法那里有涉及，代码如下，本质我们就是对Range的结构体进行排序，我们就在结构体里面写这个结构体的比较运算符，相当于就是运算符的重载，重载< 的时候，参数之能有一个,sort函数第三个参数不用写内容，是局部的一种函数写法

• 一定比较两种写法的不同，暂且叫做一个局部，一个全局的写法，局部的写法也就是代码1部分，参数只需要一个，全局的写法，代码2部分，参数也需要两个。

代码1：

struct Range
{
    int  l,r;
    bool operator <(const Range &W)const
    {
        return l<W.l;
    }
}range[N];
sort(range,range+n); // 不是全局写法，直接类内部对运算符重载

代码2：

struct Range
{
    int  l,r;
    bool operator() (const Range &W, const Range& s)const 
    {
        return W.l < s.l;
    }
} rg,range[N];
sort(range,range+n, rg); // 如果是两个参数，可以叫做全局的写法的时候，第三个参数需要传递一个对象

系统提供的sort函数

class Solution {
public:
    bool operator() (string& a, string& b) const
    {
        return a + b < b + a; 
        // 这里就是全局的写法，因为比较的内容并不是Solution的写法， 所以operator<不能用
    }
    string minNumber(vector<int>& nums) {
        vector<string> arr;
        for (int i = 0; i < nums.size(); i++)
        {
            arr.push_back(to_string(nums[i]));
        }
        sort(arr.begin(), arr.end(), Solution()); // Solution()就是创造一个对象
        string str = "";
        for (auto& c : arr)
        {
            str += c;
        }
        return str;
    }
};

一对元素，先按照第一个从大到小，第二个从小到大

struct op1{
    bool operator() (const vector<int>& s1, const vector<int>& s2) const
    {
        return (s1[0] > s2[0]) || (s1[0] == s2[0] && s1[1] < s2[1]); 
    }
};