LeetCode-线性排序-(桶排序、计数排序、基数排序)

        《算法导论3rd-p112》

        将要排序的数据分到几个有序的桶里，每个桶里的数据再单独进行排序。桶内排完序之后，再把每个桶里的数据按照顺序依次取出，组成的序列就是有序的了。

        首先，要排序的数据需要很容易就能划分成 m 个桶(如何合理选择桶的数量？)，并且，桶与桶之间有着天然的大小顺序。这样每个桶内的数据都排序完之后，桶与桶之间的数据不需要再进行排序。

        其次，数据在各个桶之间的分布是比较均匀的。如果数据经过桶的划分之后，有些桶里的数据非常多，有些非常少，很不平均，那桶内数据排序的时间复杂度就不是常量级了。在极端情况下，如果数据都被划分到一个桶里，那就退化为 O(nlogn) 的排序算法了。

        桶排序比较适合用在外部排序中。所谓的外部排序就是数据存储在外部磁盘中，数据量比较大，内存有限，无法将数据全部加载到内存中。

        比如说我们有 10GB 的订单数据，我们希望按订单金额（假设金额都是正整数）进行排序，但是我们的内存有限，只有几百 MB，没办法一次性把 10GB 的数据都加载到内存中。这个时候该怎么办呢？如何借助桶排序的处理思想来解决这个问题？

        我们可以先扫描一遍文件，看订单金额所处的数据范围。假设经过扫描之后我们得到，订单金额最小是 1 元，最大是 10 万元。我们将所有订单根据金额划分到 100 个桶里，第一个桶我们存储金额在 1 元到 1000 元之内的订单，第二桶存储金额在 1001 元到 2000 元之内的订单，以此类推。每一个桶对应一个文件，并且按照金额范围的大小顺序编号命名（00，01，02...99）。

        理想的情况下，如果订单金额在 1 到 10 万之间均匀分布，那订单会被均匀划分到 100 个文件中，每个小文件中存储大约 100MB 的订单数据，我们就可以将这 100 个小文件依次放到内存中，用快排来排序。等所有文件都排好序之后，我们只需要按照文件编号，从小到大依次读取每个小文件中的订单数据，并将其写入到一个文件中，那这个文件中存储的就是按照金额从小到大排序的订单数据了。

        不过，订单按照金额在 1 元到 10 万元之间并不一定是均匀分布的 ，所以 10GB 订单数据是无法均匀地被划分到 100 个文件中的。有可能某个金额区间的数据特别多，划分之后对应的文件就会很大，没法一次性读入内存。这又该怎么办呢？针对这些划分之后还是比较大的文件，我们可以继续划分，比如，订单金额在 1 元到 1000 元之间的比较多，我们就将这个区间继续划分为 10 个小区间，1 元到 100 元，101 元到 200 元，201 元到 300 元....901 元到 1000 元。如果划分之后，101 元到 200 元之间的订单还是太多，无法一次性读入内存，那就继续再划分，直到所有的文件都能读入内存为止。

已知 vector nums，如何计算桶的数量
//方法一
int n = nums.size();
int minVal = *min_element(nums.begin(), nums.end());
int maxVal = *max_element(nums.begin(), nums.end());
//将最大值与最小值之差按照数据个数进行均分，这里的d就相当于单个桶的容量，也就是桶的大小
//求出的d用来求解桶的索引
int d = max(1, (maxVal - minVal) / (n - 1));
//桶的大小
int bucketSize = (maxVal - minVal) / d + 1;
//计算桶的索引
int idx = (nums[i] - minVal) / d;

//方法二
int n = nums.size();
int minVal = *min_element(nums.begin(), nums.end());
int maxVal = *max_element(nums.begin(), nums.end());
//桶的大小
int bucketSize = (maxVal - minVal) / n + 1;

        《算法导论3rd-p108》

        计数排序是特殊的桶排序，待排序的数据的取值范围都在[0,k]范围内，此时可把数据放入k+1个桶中，每个桶中的数据都是相同的，省掉了桶内排序。

        计数排序需要额外的空间来保存计数数据(下面代码中的counter)，故计数排序不是原地排序；计数排序是稳定的排序，代码中有体现。

        计数排序只能用在数据范围不大的场景中，如果数据范围 k 比要排序的数据 n 大很多，就不适合用计数排序了。而且，计数排序只能给非负整数排序，如果要排序的数据是其他类型的，要将其在不改变相对大小的情况下，转化为非负整数。

//out中是已经排序好的数据
//k表示nums中的数据的取值范围为[0, k],使用k+1个桶，每个桶内的数据都相同，省掉了桶内的排序
void countingSort(vector& nums, vector& out, int k)
{
	vector counter(k+1, 0);//保存数据出现的次数
	for (auto& i:nums)
	{
		counter[i]++;
	}
	//更新counter[i]，使得其内保存的是值小于等于i的总次数
	for (int i=1;i<=k;++i)
	{
		counter[i] += counter[i - 1];
	}

	//输出到out，逆序访问nums中的数据，保证稳定性
	out.resize(nums.size());
	for (auto it=nums.rbegin(); it != nums.rend(); ++it)
	{
		//注意索引比次数少一
		out[counter[*it]-1] = *it;
		counter[*it]--;
	}
}

        《算法导论3rd-p110》

        基数排序是基于计数排序的来实现的，所以基数排序也不是原地排序；由于计数排序是稳定的，所以基数排序也是稳定的。

        这里有一个新的排序问题。假设我们有 10 万个手机号码，希望将这 10 万个手机号码从小到大排序，你有什么比较快速的排序方法呢？

        如果使用快排，时间复杂度可以做到 O(nlogn)，还有更高效的排序算法吗？桶排序、计数排序能派上用场吗？手机号码有 11 位，范围太大，显然不适合用这两种排序算法。针对这个排序问题，有没有时间复杂度是 O(n) 的算法呢？

        现在就来介绍一种新的排序算法，基数排序。刚刚这个问题里有这样的规律：假设要比较两个手机号码 a，b 的大小，如果在前面几位中，a 手机号码已经比 b 手机号码大了，那后面的几位就不用看了。借助稳定排序算法，这里有一个巧妙的实现思路。先按照最后一位来排序手机号码，然后，再按照倒数第二位重新排序，以此类推，最后按照第一位重新排序。经过 11 次排序之后，手机号码就都有序了。一个简单的例子见下图：

        基数排序对要排序的数据是有要求的，需要可以分割出独立的“位”来比较，而且位之间有递进的关系，如果 a 数据的高位比 b 数据大，那剩下的低位就不用比较了。除此之外，每一位的数据范围不能太大，要可以用线性排序算法来排序，否则，基数排序的时间复杂度就无法做到 O(n) 了。

164. 最大间距

class Solution {
public:
    int maximumGap(vector& nums) {
        //方法一：基数排序，https://leetcode-cn.com/problems/maximum-gap/solution/zui-da-jian-ju-by-leetcode-solution/
        int n = nums.size();
        if (n < 2) {
            return 0;
        }
        int exp = 1;
        vector buf(n);
        int maxVal = *max_element(nums.begin(), nums.end());

        while (maxVal >= exp) 
        {
            //基数排序是基于计数排序的，会用到额外的空间来保存计数数据
            //由于十进制数每位的取值范围为[0,9]，对应于计数排序中的k=9，所以这里的cnt需要预留10个元素的存储空间
            vector cnt(10, 0);
            for (int i = 0; i < n; ++i) 
            {
                int digit = (nums[i] / exp) % 10;
                cnt[digit]++;
            }
            //更新cnt[i]，使得其内保存的是值小于等于i的总次数
            for (int i = 1; i < 10; i++) 
            {
                cnt[i] += cnt[i - 1];
            }
            //将排序后的数据保存到buf，逆序访问nums中的数据，保证稳定性
            for (int i = n - 1; i >= 0; i--) 
            {
                int digit = (nums[i] / exp) % 10;
                //索引比次数少一
                buf[cnt[digit] - 1] = nums[i];
                cnt[digit]--;
            }            

            //此时buf保存的是按位进行过一轮排序后的数据，需要对其进行下一轮的排序
            nums.swap(buf);
            exp *= 10;
        }

        int ret = 0;
        for (int i = 1; i < n; i++) 
        {
            ret = max(ret, nums[i] - nums[i - 1]);
        }
        return ret;
    }
};

//桶排序，https://leetcode-cn.com/problems/maximum-gap/solution/zui-da-jian-ju-by-leetcode-solution/
class Solution {
public:
    int maximumGap(vector& nums) {
        int n = nums.size();
        if (n < 2) {
            return 0;
        }
        int minVal = *min_element(nums.begin(), nums.end());
        int maxVal = *max_element(nums.begin(), nums.end());
        int d = max(1, (maxVal - minVal) / (n - 1));
        int bucketSize = (maxVal - minVal) / d + 1;

        vector> bucket(bucketSize, {-1, -1});  // 存储 (桶内最小值，桶内最大值) 对，(-1, -1) 表示该桶是空的
        for (int i = 0; i < n; i++) 
        {
            int idx = (nums[i] - minVal) / d;
            if (bucket[idx].first == -1) 
            {
                bucket[idx].first = bucket[idx].second = nums[i];
            } 
            else 
            {
                bucket[idx].first = min(bucket[idx].first, nums[i]);
                bucket[idx].second = max(bucket[idx].second, nums[i]);
            }
        }

        int ret = 0;
        int prev = -1;
        for (int i = 0; i < bucketSize; i++) 
        {
            if (bucket[i].first == -1) 
                continue;
            if (prev != -1) 
            {
                //相邻元素之间最大的差值
                ret = max(ret, bucket[i].first - bucket[prev].second);
            }
            prev = i;
        }
        return ret;
    }
};

2.2

2.3