数据结构与算法

发表于2022-09-15|更新于2022-09-30|数据结构

|字数总计:7.5k|阅读时长:27分钟|阅读量:

文章内容:

数据结构与算法之旅

（正在自学中，此笔记会不断更新完善）

如果这世界上真有奇迹

那只是努力的另一个名字

----《致美丽的你》----

视频链接

学奔溃后和大佬的对话：

哈哈，我最近没看到消息。不要迷茫同学，克服当下的困难，做自己害怕的事，你会感到十分充实。我刷题也是一直受打击，不过我最近一天硬着头皮刷5道，这其实就是一个熟能生巧的过程，万事开头难。正是因为有差距，才要一点一点追赶。我之前也是喜欢和别人比，其实你可以不用和别人比，因为比了也无法缩小差距，还不如和昨天的自己比进步，每日有更多的收获。慢慢地过段时间，通过你的坚持不懈，你会发现，你和别人的距离缩小了。即使你认为很厉害的人他们也和你有同样的心理，因为他们比较对象不同，为什么有些人能顶得住压力，继续奋勇向前，当你只在乎自己是否有提升的时候，你就是无所畏惧的。想做的事，考虑清楚之后，尽管去做。你要记住，凡是不能够打倒你的，都会使你更强大。迷茫是常态，在迷茫之后又能迅速找到方向才是正解。人生是长跑，现在比你强的，以后未必，现在没你强的，以后或许会超越你，但这件事不是发生在现在，而是一步一个脚印走向的未来。希望能帮到你！

时间复杂度：

看：N+N-1+N-2+N-3......

比：N+N-1+N-2+........

swap：N次

= aN^2+6N+C

只要高阶项，不要低阶项，如果剩下的部分为f(N)，那么时间复杂度为o(f(N))

如：选择排序每一次遍历只排序一个数，那么就是0~N-1,第二次遍历:0~N-2......那么等差数列就是:aN ^ 2+C,忽略掉高阶项和低阶项也就是忽略掉a和C,那么时间复杂度就是O(N^2);

异或：

相同为0,不同为1

如：a ^ b= ?

a=0,b=1;则=1;

a=0,b=0,则=0;

a=1,b=1,则=0;

a=10110,b=00111,则=10001;

那么可以推出结论：0^N=N（0跟任何数异或都是那个数本身） N^N=0（任何数跟任何数异或都是0）

a^b=b^a（交换） a^b^c=a^(b^c)（b和c先异或再异或a）(一堆数)^(同一堆数)=(同一堆数)（跟谁先异或的顺序无关，结果一定是一样的）

应用到选择排序上：

int a=17;int b=23;

a=a^b;（a=17^23, b=23）

b=a^b;（a=17^23  b=17^23^23（b=17^(23^23)=17^0）b=17）

a=a^b;（a=17^23^17(a=23^(17^17)=23^0)  a=23）

当上面的代码执行完以后a和b的值被交换了

注意：这样写的前提是a和b不能指向同一块区域

问题1：在一个整形数组中已知只有一种数出现了奇数次，其他的所有数出现了偶数次，怎么找到出现了奇数次的那个数？

答：创建一个变量等于0,把那个变量跟数组中的每一个数都依次遍历异或一次，最后那个变量就等于那个奇数

问题2：在一个整形数组中如果有两种数出现了奇数次，其他所有数都出现了偶数次，怎么找到那两种出现了奇数次的数？

答：创建一个变量eor，将数组所有的值遍历一遍，最后eor等于a ^ b(a和b就是那两种奇数)，创建一个变量right等于eor&(~eor+1(取反eor再加1)再&上eor)=数组中最右侧的1也就是被 ^ 后不是0的那些数，再创建一个变量eorl=0，再循环遍历数组,判断用right&上数组中的每一个数是否不等于0，判断成功进来之后用eorl去异或第8位上数组里不是0的那些数，也就是进来之后的数组arr[i]，然后erol就变成了那两个奇数中的一个（a or b），最后eor^eorl就可以得到另一个奇数……

插入排序：

就跟斗地主时拿牌插牌再拿牌一样

通过for循环遍历数组，第一个for循环i=1;i < len;i++，第二个for循环里面创建一个变量j，j=i-1;j>=0&&arr[j] > arr[j+1];j--（i等于第二个数,j就等于比i小的前一个数,j+1就等于i,如果j所代表的前一个数大于j+1所代表的后一个数,则就把j和j+1进行交互,将较小的后一个数移到前面来,然后j--就代表j再等于更前一位的数,j+1就代表刚交换过来的那个数,然后再进行比较,一直到j减到第0位为止，也就是说一直在<=i的前面不停的比较，最终i循环完也就排序完了）因为要交换的是j与j+1，所以交换代码可以这样写：arr[j]=arr[j] ^ arr[j+1];arr[j+1]=arr[j] ^ arr[j+1];arr[j]=arr[j] ^ arr[j+1];

二分查找法:

用二分法查找的数组必须有序，其方法就是在中间找一个数X，然后判断中间的这个数X是否大于要查找的那个数num，如果大于则把数组中大于X的一堆数给砍掉，只在小于X的那堆数里找num，然后继续在小于X的那堆数里找中间数，继续判断砍掉另一半，最终找到num为止……

问题1：在一个有序数组中有一个num，要求找到这个数组中num的最左值，也就是num第一次出现的位置?

答：假设这个数是3，那么先在中间找一个数,假设这个中间的数是4,那么4>=3,满足则把4这个位置右边的数给省略掉，4这个位置用一个变量t记住，在这个位置左边找中间数，假设找到2，2不>=3,不满足，则在2这个位置的右边找，在2这个位置的右边取中间一个数，假设取到了3，3>=3满足，如果此时这个3的位置比之前那个4的位置往左了一点，也就是比t小了一点，那么就让t等于3那个位置，如果此时t的位置左边还有数则继续二分取中间数，假设又取到了3，3>=3满足，继续用t等于3的这个位置，如果此时继续往左只有之前那个不满足的2的位置则当前这个3的位置就是最左值……

问题2：在一个无序数组中任何两个相邻的数不相等，请找到一个该数组中局部最小的数？（局部最小的意思是这个数的左边和右边两个数都比它大，那么它就是局部最小，如果是0位则只需要比它右边的数小，如果是N-1则只需要比左边的N-2小）……

答：先判断0位置是不是局部最小，如果是则直接返回，如果不是则表示0位置的数比1位置的数要大，然后再判断N - 1是不是局部最小(N代表的是数组的最后那个数)，如果是则返回，如果不是则代表N-1比N-2要大，那么此时0位置 ~ N-1位置一定有一个局部最小值，这时直接用二分法取0 ~ N中间位置，假设取到了X，如果X比X-1位置要小并且比X+1位置也小则直接返回X，否则X就比X-1位置或者X+1位置要大，那么此时这个局部最小值就在位置0 ~ X-1之间，那么就继续在位置0 ~ X-1中取中间二分，直到找到那个局部最小值为止……

对数器：

针对一个题目需要准备两种不同的方法创建两个函数，一个是算法，一个是暴力解法，再创建一个随机样本产生器（通过随机产生数据的函数random()，random() * N，int(random() * N)）也就是创建两个一模一样的数组，数组里面的值和长度是随机的，然后两个函数分别调用一遍，看是否结果一样，如果不一样则人工干预把它改成一样的

day02

递归问题：

求数组中某一个范围上的最大值：

先把要求的范围L跟R给传进来，如果L==R，则直接返回L，否则创建一个变量mid=L+((R-L)>>1);(这里的意思是右移一位求中间数，也可以看作是(R-L)/2)

然后利用递归方法分别求出左边的最大值和右边的最大值：fun(arr,L,mid); fun(arr,mid+1,R); 然后返回两个最大值中较大的那个：return max(leftMax,rightMax);

master公式：T(N)=a T(N / b)+O(N ^ d)，所有的递归都可以用这个公式求，其中a等于要调用递归的次数，b等于二分的区域,如果是分成两半那就是2分之N,如果是分成3份那就是3分之N，O(N ^ d)表示除去所有子递归调用后剩下的代码的时间复杂度，这个d指的是决策过程如果只有一个则d=0，O(1)就是剩下代码的时间复杂度……其公式可以如下：log(b,a) < d： O(N ^ d)，log(b,a)> d：O(N ^ log(b,a))，log(b,a)==d：O(N ^ d logN)

归并排序：

利用二分的方法不断的递归调用，每次找一半排序，然后左一半和右一半排好序后进行比较，谁小拷贝谁，准备一个长度大小一模一样的数组，把左边右边比较后小的那个数拷贝进数组，拷贝完后就对下一个数进行比较拷贝(这里的左边和右边的比较都是从下标为最左边第一个数的位置开始比较的)，当有任意一半边越界时就不进行比较了，直接把剩余的数全部拷贝进数组，也就是合并两个有序数组，使合并后的数组有序……

例如：先创建一个函数fun，判断数组arr是否等于NULL或者数组长度是否小于2，如果是则直接return，否则就调用process函数：process(arr,0,len);

void process(int* arr,int L,int R){

//然后在函数里面判断L==R，如果等于则返回，否则创建一个变量等于数组长度的中间位置：

int mid=L+((R-L)>>1);

//然后将数组的左半边通过递归调用不停的二分排序，注意process只是调用，真正排序的功能代码在merge函数里面，因为每次递归都会调用自己和merge函数，所以可以实现一半有序：

process(arr,L,mid);

//再将数组的右半边通过递归调用不停的二分排序：

process(arr,mid+1,R);

//最后通过调用排序函数来将左边和右边的数传进去排序：merge(arr,L,mid,R);

}

void merge(int* arr,int L,int M,int R){

//创建一个新的数组用来存排好序的数长度跟原来的那个数组一样：

vector<int> help(R - L + 1);

//创建一个变量i专门给help使用：

int i=0;

//创建两个类似指针的变量一个指向L,一个指向右边的边界也就是右半边一开始的位置mid+1：

int p1=L;

int p2=M+1;

//然后创建一个循环，循环条件是左边和右边的指针变量都没有越界：

while(p1<=M&&p2<=R){

//如果都没有越界则左边和右边不停的进行比较，把小的那个拷贝进数组里：

if (arr[p1] <= arr[p2]){

help[i++] = arr[p1++];

  }  else {

   help[i++] = arr[p2++];

  }

}

//然后再创建两个循环判断是否越界,一定会有一个越界所以下面两个while循环只会中一个：

//如果p1没有越界则代表p2越界了,那么就把p1剩下的值拷贝到help数组里去：

while(p1<=M){

help[i++]=arr[p1++];

}

//如果p2没有越界则代表p1越界了,那么就把p2剩下的值拷贝到help数组里去：

while(p2<=R){

help[i++]=arr[p2++];

}

//执行完上面的循环之后help数组里就是已经排好序的新数组了，最后再将新数组把用来的数组拷贝替换掉，那么原来的数组就是排好序的数了：

for(i=0;i<help.size();i++){

	arr[L+i]=help[i];//L表示数组的左边第一个下标

	}

}

问题1：小和问题:在一个数组中，每一个数左边比当前数小的数累加起来，叫做这个数组的小和，求一个数组的小和：【1，3，4，2，5】……

例：每个数前面比它小的那个数加起来，如数组【1,3,4,2,5】1的前面没有，所以它的小和是0，3的前面有1，所以它的小和是1，4的前面有1，3，所以它的小和是1+3=4，2的前面只有1比它小，所以它的小和是1，5的前面有1,3,4,2比它小，所以它的小和是1+3+4+2=10；那么这个数组的小和就是全部小和加起来：0+1+4+1+10=16……

转换思路：求一个数左边有多少个数比它小其实也是求右边有多少个数比它大，如数组【1,3,4,2,5】

1的右边比它大的数有4个，那么就是4个1

3的右边比它大的数有2个，那么就是2个3

4的右边比它大的数有1个，那么就是1个4

2的右边比它大的数有1个，那么就是1个2

5的右边比它大的数没有，那么就是0个5

那么( 4 个 1 ) 4 + ( 2 个 3 ) 6 + ( 1 个 4 ) 4 + ( 1 个 2 ) 2 = 16

代码：

//创建一个fun函数判断arr是否等于NULL或者len<2，是则返回0否则返回调用process函数的结果:

 int fun(int *arr, int len)

    {

        if (arr == NULL || len < 2)

        {

            return 0;

        }

        return process(arr, 0, len);

    }

//创建一个process函数在函数里不停的递归二分：

   int process(int *arr, int L, int R)

    {

        if (L == R)//如果左边和右边长度相同则直接返回0

        {

            return 0;

        }

        int mid = L + ((R - L) >> 1);//找到数组中间位置



        return process(arr, L, mid) +  //左侧排序求小和的数量

process(arr, mid + 1, R) +//右侧排序求小和的数量

 merge(arr, L, mid, R);//左侧排好和右侧排好合并之后加上merge求小和的数量

    }

//创建一个merge函数求每次递归过来的数的小和数量

 int merge(int *arr, int L, int M, int R)

    {

        vector<int> help(R - L + 1);//创建一个和每次递归传过来的数组长度一模一样的动态数组

        int i = 0;//创建一个变量i专门用来给help数组使用

        int p1 = L;//创建一个指针变量等于最左边的下标

        int p2 = M + 1;//创建一个指针变量等于右边的边界

        int res = 0;//创建一个变量用来累加小和

        while (p1 <= M && p2 <= R)

        {//如果左边的下标指针变量和右边的下标指针变量都没有越界则进行比较

            if (arr[p1] < arr[p2])//如果左边的比右边的小

            {

//求小和的数量，R-p2+1代表右边界减去右边变量所指的下标后还剩下多少个数比左边的下标的数大再乘arr[p1]也就是左边下标所指的那个数得到多少个数比左边的数大就是多少个左边的数，如4个数比1大那就是4个1，然后用创建的变量累加起来

                res += (R - p2 + 1) * arr[p1];

//得到小和的数之后再将小的那个数存进新创建的数组里面，这样最后数组里的数也排序好了

                help[i++] = arr[p1++];

            }

            else			//如果左边的不比右边的小

            {

//则表示没有小和，res变量就不累加任何数

                res += 0;

//也是将小的那个数存进变量里，进来这里则表示右边比左边的小

                help[i++] = arr[p2++];

            }

        }

//判断右边指针变量是否越界，如果越界则把左边剩余排序好的数给全部放进新数组里

        while (p1 <= M)

        {

            help[i++] = arr[p1++];

        }

//判断左边指针变量是否越界，如果越界则把右边剩余排序好的数给全部放进新数组里

        while (p2 <= R)

        {

            help[i++] = arr[p2++];

        }

//把新数组拷贝替换回原数组，这样原数组就是排好序的数了

        for (i = 0; i < help.size(); i++)

        {

            arr[L + i] = help[i];

        }

        return res;

    }

问题2：逆序对问题:在一个数组中，左边的数如果比右边的数大，则这两个数构成一个逆序对，请打印所有逆序对和数量。

例子：【3,2,4,5,9,1,0】的逆序对是12

1. 3,2

2. 3,1

3. 3,0

4. 2,1 	

5. 2,0

6. 4,1 

7. 4,0

8. 5,1  

9. 5,0

10. 9,1

11. 9,0

12. 1,0

代码：

int fun(int *arr, int len)

    {

        if (arr == NULL || len < 2)

        {

            return 0;

        }

        return process(arr, 0, len - 1);

    }

    int process(int *arr, int L, int R)

    {

        if (L == R)

        {

            return 0;

        }

        int mid = L + ((R - L) >> 1);

        return process(arr, L, mid) + process(arr, mid + 1, R) + merge(arr, L, mid, R);

    }

    int merge(int *arr, int L, int M, int R)

    {

        //如果左边的数比右边的数大，则这两个数构成一个逆序对

        vector<int> help(R - L + 1);

        int i = 0;

        int p1 = L; 

        int p2 = M + 1;

        int res = 0;

        while (p1 <= M && p2 <= R)

        {

            if (arr[p1] > arr[p2])

            {

//最重要的就是这条，通过减p2的下标位置而知道有多少个右边的数比左边的数小

                res += (R - p2 + 1);

                help[i++] = arr[p1++];

            }

            else

            {

                res += 0;

                help[i++] = arr[p2++];

            }

        }

        while (p1 <= M)

        {

            help[i++] = arr[p1++];

        }

        while (p2 <= R)

        {

            help[i++] = arr[p2++];

        }

        for (i = 0; i < help.size(); i++)

        {

            arr[L + i] = help[i];

        }

        return res;

    }

day03

荷兰国旗问题：

问题1：给定一个数组arr，和一个数num，请把小于等于num的数放在数组的左边，大于num的数放在数组的右边。

答：创建一个指针变量i，从左边遍历数组，当[ i ] < = num时，[ i ]和小于区域的下一个变量也就是还没进入小于区域的后一个变量交换，i++。

当[i] > num时,i++;最后遍历完数组最后一个数时就完成了比num小的数在左边，比num大的数在右边。

问题2：给定一个数组arr，和一个数num，请把小于num的数放在数组的左边，等于num的数放在数组的中间，大于num的数放在数组的右边。

答：创建一个i指针变量，当[i] < num时,[i]和小于区域也就是还没进入小于区域的下一个数交换，小于区域向右扩将刚交换完的那个数扩进小于区域，i++。

当[ i ] = = num时,i++。

当[ i ] > num时,[ i ]和大于区域前一个也就是还没进入大于区域的前一个数交换，大于区域左扩将刚交换的数扩进去，i原地不变继续执行逻辑1，如果小于num则和小于区域的后一个数交换左边区域继续扩。如果等于num则i++。

快速排序：

1.0版本：将排序问题拆分为将数组划分成大于Num的右子序列与小于等于Num的左子序列，即每次num位置都是相对正确的。递归让所有问题规模的数组都有序。

2.0版本：Num区域是已经排序好的，不断递归增加排序好的范围。

复杂度都是最坏情况O(n ^ 2)，最好情况就是划分值在中值附近。

day04

堆排序：

堆结构其实是一颗完全二叉树结构，根据下标把数据从零到末尾依次按二叉树排好,优先级队列其实就是堆结构，堆结构比堆排序重要的多

排好后这时任意一个节点的左右孩子位置可以通过公式求得：左孩子： 2 i + 1，右孩子：2 i + 2

它们的父亲可以通过：( i - 1 ) / 2 得到

堆排序跟完全二叉树不同的是堆结构分为大根堆和小根堆，大根堆是二叉树的头结点必须得是数组中最大的那个数，从大往小排，而小根堆是从小往大排。

代码：

void fun(int* arr, int len)

    {

        if (arr == NULL || len < 2)

        {

            return;

        }

        for (int i = 0; i < len; i++)

        {

            heapInsert(arr, i);

        }

    }

    void heapInsert(int* arr, int index)//大根堆

    {

        while (arr[index] > arr[(index - 1) / 2])

        {

            swap(arr[index] , arr[(index - 1) / 2]);//交换函数

            index = (index - 1) / 2;

        }

    }

问题1：找到堆中的最大值然后把它去掉

答：找一个变量存储根节点的值，把根节点取出来和最后一个节点交换，将数组的长度len减一，这样最后一个节点的值就自动和堆断开连接了，然后交换后的根节点自动跟它的子节点里最大的比较，如果比子节点小自动换位。

代码：

void fun(int *arr, int len)

    {

        if (arr == NULL || len < 2)

        {

            return;

        }

        // for (int i = 0; i < len; i++) //此时数组里的数已全变成大根堆

        // {

        //     heapInsert(arr, i);

        // }

        for(int i=len-1;i>=0;i--){//自低向上的不停进入heapify找子节点比大小，当这个过程完了之后也是大根堆跟上面是等价的

            heapify(arr,i,len);//如果用户不是一个一个的往数组里加数而是一堆数给你那么这个方法是最好的

        }

        swap(arr[0], arr[--len]); //这里单独交换的意思其实就是等价于len-1，

        //因为下面的循环是从10~0,一共有11次，所以要在这里减一次并将第一个和最后一个交换



        while (len > 0) //通过遍历左右孩子来实现排序

        {

            heapify(arr, 0, len); // O(logN)

            swap(arr[0], arr[--len]);

        }

    }

    void heapInsert(int *arr, int index) //大根堆

    {

        while (arr[index] > arr[(index - 1) / 2])

        {

            swap(arr[index], arr[(index - 1) / 2]);

            index = (index - 1) / 2;

        }

    }

    void heapify(int *arr, int index, int heapSize) //判断左右子节点是否越界需要长度也就是heapSize

    {

        int left = index * 2 + 1; //左孩子

        int largest;

        while (left < heapSize) //当下方还有孩子的时候

        {

            //两个孩子中谁的值大，把谁的下标给largest

            if (left + 1 < heapSize && arr[left + 1] > arr[left]) // left+1是右孩子的下标，因为左孩子是i*2+1，右孩子是i*2+2

            {                                                     //如果右孩子存在且右孩子的值大于左孩子

                largest = left + 1;                               // largest等于右孩子的下标

            }

            else

            {

                largest = left; // largest等于左孩子的下标

            }



            if (arr[largest] > arr[index]) //较大孩子的值和父亲的值比较

            {

                largest = largest; //如果较大孩子比父亲大则largest不变

            }

            else

            {

                largest = index; //如果较大孩子没有比过父亲则largest等于父亲的下标

            }



            if (largest == index) //如果largest(孩子)==index(父亲)则表示父节点下面已经没有比父节点大的孩子了，父节点就是最大的了，则退出循环

            {

                break;

            }

            swap(arr[largest], arr[index]); //如果largest!=index则表示largest(较大孩子)干过了index(父亲),则把孩子和父亲的值交换

            index = largest;                //交换过后index(父亲)=largest(较大孩子)也就是现在index(父亲)变成了原先的较大孩子继续往下走进行比较

            left = index * 2 + 1;           //这时左孩子就等于了原先较大孩子的左孩子继续循环，如果没有孩子了则会退出循环，如果有孩子但孩子都不比它大则也会退出循环

        }

    }

问题2：

答：假设k=6，创建一个小根堆排序，排完后0位置上放的就是小根堆的最小值，然后把0位置弹出，放入第7个数字也就是新输入的第一个数字，这时小根堆的最小值在1位置上，然后继续弹出位置1上的最小值，再加入第8个数字，这时最小值在2位置上，这样依次弹出，最后数组临近结束的时候只要依次把小根堆弹出的数停好数组就有序了。

利用黑盒priority_queue创建堆排序代码：

#include <bits/stdc++.h>

using namespace std;

int main()

{

    //priority_queue<int> a;  //这个就是堆排序的封装函数,默认是大顶堆

    priority_queue<int, vector<int>, greater<int>> heap; //这样就是小顶堆

    priority_queue<pair<int, int> > a;//pair用来比较元素，返回一整个数组的值,第一个数组里的值比较完比较第二个

    // priority_queue<string> b;

    heap.push(8);

    heap.push(4);

    heap.push(9);

    heap.push(1);

    while (!heap.empty()) //如果队内元素不为空

    {

        cout << heap.top() << " "; //输出头元素然后用pop()弹出

        heap.pop();//一直循环弹出到没有元素为止

    }

    cout<<"\n";

    pair<int, int> b(1, 2);

    pair<int, int> c(1, 3);

    pair<int, int> d(2, 5);

    a.push(d);//2，5

    a.push(c);//1，3

    a.push(b);//1，2

    while (!a.empty())

    {

        cout << a.top().first << ' ' << a.top().second << '\n';//first代表第一个,second代表最后一个，它们代表数组里的两个值

        a.pop();

    }

    return 0;

}

/*

top 访问队头元素

empty 队列是否为空

size 返回队列内元素个数

push 插入元素到队尾 (并排序)

emplace 原地构造一个元素并插入队列

pop 弹出队头元素

swap 交换内容

*/

利用黑盒解决问题2，代码：

void sortArr(vector<int> &arr, int k)

    {

        priority_queue<int, vector<int>, greater<int>> heap;

        int index = 0;

        int len = arr.size();

        for (; index < min(len, k); index++)

        {

            heap.push(arr[index]);

        }

        int i = 0;

        for (; index < len; i++, index++)

        {

            heap.push(arr[index]);

            arr[i] = heap.top();

        }

        while (!heap.empty())

        {

            arr[i++] = heap.top();

        }

    }

比较器：给定数据调用语言内部的比较器sort，默认就会用快速排序来排。

代码：

#include <iostream>

#include <algorithm>

#include <vector>

using namespace std;



bool complare(int a,int b)

{

 return a>b;

}

int main()

{

    int arr[] = {5, 4, 9, 1, 6, 2};

    int len = sizeof(arr) / sizeof(arr[0]);

    //sort(arr, arr + len); //默认从小到大

    // sort(arr,arr+len,greater<int>());//从大到小

    //sort(str, str + 10, greater<char>());//对字符串从大到小排序

    sort(arr,arr+len,complare);//通过在方法里改变函数的返回值也可以实现从大到小排序

    return 0;

}

day05

桶排序

找到数组里位数最多的那个数，然后把数组里其它数通过在前面补零的方式让它们的位数跟数组里位数最多的那位数位数相等，然后准备跟位数里最大值一样多的桶(容器)，第一遍按个位数开始装桶，比如 100 就装进零号桶，072 就装进2号桶，017 就装进 7 号桶，当全部装完后就从左往右把桶里的数重新放进数组里，比如 0 号桶是 100 ， 2 号桶是 072 ， 3 号桶是 013 ，那么倒出来就是【 100，072，013 】，又比如2号桶装了两个数分别是 072 和 012 ，那么就按从上往下的顺序倒：【 100，072，012，013 】，当倒完个位数后就从十位数开始重新进桶，然后再从桶倒出到数组，然后再按百位数进桶再出桶，当最后一个位数出桶后数组就变成有序，因为是从左往右出桶，所以是从小到大

代码：

void fun(vector<int> &arr)

    {

        if (arr.size() < 2)

        {

            return;

        }

        radixSort(arr, 0, arr.size() - 1, maxbits(arr));

    }

    int maxbits(vector<int> &arr)

    {

        int maxs = INT_MIN;

        for (int i = 0; i < arr.size(); i++)

        {

            maxs = max(maxs, arr[i]);

        }

        int res = 0; //这里res=res==0?1:res;否则最大数是0的时候就会有问题

        while (maxs != 0)

        {

            res++;

            maxs /= 10;

        }

        return res;

    }

    //实现1~17范围上排序

    void radixSort(vector<int> &arr, int L, int R, int digit) // digit代表这一批数的最大值

    {

        const int radix = 10;

        int i = 0, j = 0;

        vector<int> bucket(R - L + 1);

        for (int d = 1; d <= digit; d++)

        {

            vector<int> count(radix);

            for (i = L; i <= R; i++)

            {

                j = getDigit(arr[i], d);

                count[j]++;

            }

            for (i = 1; i < radix; i++)

            {

                count[i] = count[i] + count[i - 1];

            }

            for (i = R; i >= L; i--)

            {

                j = getDigit(arr[i], d);

                bucket[count[j] - 1] = arr[i];

                count[j]--;

            }

            for (i = L, j = 0; i <= R; i++, j++)

            {

                arr[i] = bucket[j];

            }

        }

    }

    int getDigit(int x, int d)

    {

        return ((x / ((int)pow(10, d - 1))) % 10);

    }