蓝桥杯---排序数组（leetcode第912题）

1.题目重述

题目的要求是不使用库函数或者是其他的内置的函数（就是已经实现好的函数），也就是这个排序的逻辑需要我们自己进行实现；

2.思路分析

其实这个例子也是很容易理解的，对吧，就是升序排列这个数组里面的元素罢了

思路的话：首先我们需要确定这个分类讨论的逻辑链，想要明白这个题目，你必须要明白那个颜色分类的题目，因为这两个题目的思路是完全一致的，可以看我之前对于颜色分类的那个题目的详细概述；

在那个颜色分类的题目里面，我们是0,1,2三个数字，但是在这个排序的数组里面，里面出现的数据很多，相当于是之前的那个题目的一个延伸，之前的颜色分类，我们使用三路划分，就是分为三个部分，定义了left,right和i对吧，然后这个i负责对于元素进行遍历，放到正确的位置上面去；

之前我们是使用大于1，等于1，小于1进行判断的，这个里面我们需要指定这个key，是按照大于key,小于key等于key进行判断的，当只有0,1,2三个元素的时候这个key就是1，也就是我们之前的那个颜色分类的题目了；

下面的这个里面的交换策略和指针的移动的策略和我们的颜色分类题目完全一致，不理解的话可以移步去看一下之前的那个文章；

其次，我们需要确定这个key应该如何进行选择和确定： 这个key实际上就是我们的数组里面的一个元素，但是他应该如何进行确定呢，这个答案就是：随机选择这个key的时候，他的时间复杂度是最低的，因此我们需要借助random函数随机从这个数组里面选择一个数据作为我们的key；

这个随机元素怎么求，下面的这个里面的nums后面的中括号里面的就是我们这个元素的下标：随机数模上数组元素的个数就是他的位置，加上我们的left就是对应数组位置的元素的小标，这个random%数组长度+left就是随机元素的下标的确定的方法；

3.代码解释

qsort是我们的自定义函数，实现这个数组元素的排序的功能，第9行确定我们的key的选择，之前颜色分类的时候left是-1,right是最后一个元素的下一个位置，但是在这个里面，我们的left是参数l-1，两个其实没区别，就是我们使用通式进行表示了；

qsort就是分别对于三个区域进行排序，这个while里面的逻辑和我们的颜色分类里面的逻辑是完全一致的，然后就是调用了下面的这个自定义的swap函数，仅此而已；