9.sort_ideas.md

有趣的排序思想

计数排序

统计数字出现频率排序

比如这样的数据，统计1 2 3出现的频率，再把她们放到对应的位子上就好

应用场景-对单值进行排序

以往我们的排序基本上都是对一个字段，即key-value对里的一个元素进行排序，叫多值排序

比如我们要对全国人的年龄排序，那么计数排序就很有应用场景了。因为年龄的值域非常有限(0~150)

基数排序

一部份思想借用了计数排序

先根据个位的信息处理，再根据十位的信息处理

比如对于序列13, 21, 11, 32, 31, 22, 21

处理步骤:

1. 统计个位信息: 1-4个，2-2个，3-1个

   1	2	3
   4	2	1

   1. 对各位信息序列求个数前缀和，也就是按个位的大小确定位置

1	2	3
4(个位为1的尾坐标为4， 以此类推)	6	7

3. 从后向前扫描序列13, 21, 11, 32, 31, 22, 21

   21个位是1，放到1的尾坐标4的位置；22个位是2，放在2尾坐标6的位置，以此类推

   最后得到序列

   1	2	3	4	5	6	7
   21	11	31	21	32	22	13

   第一轮扫描完毕

4. 基数排序可以保证数据的相对稳定性:

   31, 21为例。31还是在21前面，数字相对位置不变。（只限于个位都一样的哈）

   这个性质很重要！ 因为相对稳定性才能保证最后你的序列是有序的 必入21和22间的关系

   之后对十位进行统计

   在改变的序列基础上

   1	2	3
   2	5	7

   扫描序列21-1, 11, 31, 21-2, 32, 22, 13

   1	2	3	4	5	6	7
   11	13	21-1	21-2	22	31	32

   对于有很多位的还是依次处理每位。

   #define LOW 0xffff
   #define HIGH 0xffff0000
   #define MAX_N 65536
   
   #define LOW16(a) ((a) & LOW)
   // #define HIGH16(a) (65535 - ((a) & HIGH) >> 16)
   
   // #define HIGH16(a) ((a & 0xffff0000) >> 16)
   
   #define __HIGH16(a) (((a) & 0xffff0000) >> 16)
   #define HIGH16(a) (__HIGH16(a) > INT16_MAX ? (__HIGH16(a) - 32768) : (__HIGH16(a) + 32768))
   // 修改之后对负数也能排序
   // 因为负数补码的表示形式
   // 负数的第一位肯定是1
   // 也就是高16位的值会大于 1000 0000 0000 0000 - 1 也就是INT16_MAX
   // 所以就要消除第一位符号位对排序的影响
   // 也就是负数减去符号位 正数加上符号位
   // 这样负数就变成了小于INT16_MAX的 正数变成了大于INT16_MAX的
   // 就相当于把 表示范围从有符号整型 -32768到+32767拉到了 0到65535
   // 因为-1 = 1111 1111 1111 1111 减去32768 = 0111 1111 1111 1111 依然是负数中最大的 不影响大小关系！
   
   
   // 负数怎么排序呢？
   // 因为负数补码的表示形式
   // 他是1开头的，所以会排到正数的后面
   // 不妨将负数看成-1和xx的结合
   // 正数看成是+1和xx的结合
   
   // n 是当前待排序数组的大小
   void radix_sort(int *arr, int n) {
       // 分别处理低16位和高16位
       // cnt数组为存储低16位每位出现频率的
       // 也就是存前缀和的
       // 这样知道了低16位是多少
       // 就能知道它在前缀和排第几
       // 也就是temp数组中的位置
       int cnt[MAX_N] = {0};
       int *temp = (int *)malloc(sizeof(int) * n);
       for (int i = 0; i < n; i++) cnt[LOW16(arr[i])] += 1;
       for (int i = 1; i < MAX_N; i++) cnt[i] += cnt[i - 1];
       // cnt 记录的是从1开始的
       // 然而temp是从0开始跌
       // 所以每次要--cnt
       for (int i = n - 1; i >= 0; --i) temp[--cnt[arr[i] & LOW]] = arr[i];
       for (int i = 0; i < MAX_N; i++) cnt[i] = 0;
   
       // HIGH16
       for (int i = 0; i < n; i++) cnt[HIGH16(temp[i])] += 1;
       for (int i = 1; i < MAX_N; i++) cnt[i] += cnt[i - 1];
       for (int i = n - 1; i >= 0; --i) arr[--cnt[HIGH16(temp[i])]] = temp[i];
       free(temp);
       return ;
   }
   
   int *getRandData(int n) {
       int *temp = (int *)malloc(sizeof(int) * n);
       for (int i = 0; i < n; i++) temp[i] = rand();
       return temp;
   }
   
   void output(int *arr, int n) {
       for (int i = 0; i < n; i++) {
           printf("%d ", arr[i]);
       }
       printf("\n");
       return ;
   }
   
   int main() {
       #define MAX_M 20
       int *arr = getRandData(MAX_M);
       output(arr, MAX_M);
       radix_sort(arr, MAX_M);
       output(arr, MAX_M);
       return 0;
   }

拓扑排序

图论算法的含义非常的广泛

因为边和点的含义完全是我们赋予他的哦！

难点：将问题转化为图所能表示的东西！

这个就叫建模

图本身没有含义，重要的是我们赋予它的含义

借助队列结构，存储点的入度，入度==0则点可以入队列了

借助队列实现拓扑排序

可能的拓扑排序A->E->B->C->F->D

每次找入度为0的点入队列 当然入度为0的点不唯一

所以拓扑排序的序列不一定唯一