剑指offer之简单排序——快排

快速排序

今天剑指做到排序的题，好像可以直接调用 sort() 函数的。但之前面试 也碰到过要我手写快排的，所以用到排序的题目，能够手写快排 应该是一个程序员的基本素养，所以在此总结一二。如何理解那些个函数，在本文后半篇学习总结。

以简单题 扑克牌中的顺子 为例 解析一下。

Q： 从若干副扑克牌中随机抽 5 张牌，判断是不是一个顺子，即这5张牌是不是连续的。2～10为数字本身，A为1，J为11，Q为12，K为13，而大、小王为 0 ，可以看成任意数字。A 不能视为 14。

示例：

输入: [1,2,3,4,5]
输出: True

想法就是先把5张牌排序嘛，就像拿到牌第一时间就是理牌...

快速排序

算法通过多次比较和交换来实现排序，其排序流程如下：

1. 首先设定一个 分界值 （pivot）：通过该分界值将数组分成左右两部分。如果我们以最左边的元素为pivot：

   int pivot = nums[l];

2. Compare and Swap：将大于或等于分界值的数据集中到数组右边，小于分界值的数据集中到数组的左边。此时，左边部分中各元素都小于或等于分界值，而右边部分中各元素都大于或等于分界值。

这具体要怎么做呢？ 我们设置两个指针i，j,分别从最左边和最右边来。这时第一个关键点 > 循环条件是什么？

很显然 就是i<j，因为当二者相遇时循环就结束了。

指针何时移动？先移动谁？

• 移动条件很好理解，就是 指针所指元素 本来就在他应该在的分区内 ，就移动指针。

  另外！！需要注意的是！！一定要加个条件 i<j，否则会出现越界！！

• 结论是如果指定最左边的元素为pivot，则应该先移动j，也就是右侧指针。为啥咧？

  注意，快排最后是要将ij所在元素与第一个元素交换的，而这个元素必须比我们的 pivot 小！

  j先来的话，j此时最后指向的就是 小于 pivot 的元素，与 i 相遇时， 就正好满足条件。

  而试想，先让i来， i会指向一个大于pivot的元素而与j相遇，不是我们想要的情况。

int i = l, j = r;
int pivot = nums[l]; # 指定最左侧元素为pivot
while(i<j){
            while(nums[j]>=pivot && i<j) j--;
            while(nums[i]<=pivot && i<j) i++;
            if(i<j){
                int tmp = nums[i];
                nums[i] = nums[j];
                nums[j] = tmp;
            }

        }
# ij相遇时 使pivot与i元素交换
nums[l] = nums[i];
nums[i] = pivot;

3. Recursive：然后，左边和右边的数据可以独立排序。对于左侧的数组数据，又可以取一个分界值，将该部分数据分成左右两部分，同样在左边放置较小值，右边放置较大值。右侧的数组数据也可以做类似处理。

4. 重复上述过程，可以看出，这是一个 递归 定义。通过递归将左侧部分排好序后，再递归排好右侧部分的顺序。当左、右两个部分各数据排序完成后，整个数组的排序也就完成了。

这个好说

quicksort(nums,l,i-1);
quicksort(nums,i+1,r);

后续处理就简单了

int joker = 0;
        for(int i =0 ; i<nums.size() ; i++){
            if(nums[i] == 0) ++joker;
            else if(i>=1 && nums[i]==nums[i-1])
                return false;
        }
        return (nums[nums.size()-1] - nums[joker] < 5);
    }

不一样的快排

快排其实分治的思想，而比较的条件可以不是简单的大于小于。

就比如 剑指 Offer 45. 把数组排成最小的数

Q ： 输入一个非负整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。

示例：

输入: [3,30,34,5,9]
输出: "3033459"

这里的比较方法是什么呢？

首先要把这里的整形数当作字符串来处理。看到一个很帅的方法，这题如此做就行。

bool compare(string &a, string &b){
       return a+b<b+a;
   }

其余处理

string minNumber(vector<int>& nums) {
        vector<string> strs;
        string res;
        for(auto num:nums){
            strs.push_back(to_string(num));
        }
        quicksort(strs, 0,strs.size()-1);
        for(auto str:strs){
            res+=str;
        }
        return res;
    }

最后学习一下sort排序函数

sort(first_pointer,first_pointer+n,cmp)

实现原理：sort并不是简单的 快速排序，它对普通的快速排序进行了优化，此外，它还结合了插入排序和堆排序。

系统会根据你的数据形式和数据量自动选择合适的排序方法，这并不是说它每次排序只选择一种方法，它是在一次完整排序中不同的情况选用不同方法，比如给一个 数据量较大 的数组排序，开始采用快速排序，分段递归，分段之后每一段的数据量达到一个较小值后它就不继续往下递归，而是选择插入排序，如果递归的太深，他会选择推排序。

碎碎念：这不知道STL源码解析有没有，那时候再看看。

此函数有3个参数：

参数1：第一个参数是数组的首地址，一般写上数组名就可以，因为数组名是一个指针常量。

参数2：第二个参数相对较好理解，即首地址加上数组的长度n（代表尾地址的下一地址）。

参数3：默认可以不填，如果不填sort会默认按数组升序排序。也就是1,2,3,4排序。也可以自定义一个排序函数，改排序方式为降序什么的，也就是4,3,2,1这样。

定义比较函数（最常用） //比如数组排列

int A[100];
bool cmp1(int a,int b)//int为数组数据类型
{
return a>b;//降序排列
//return a<b;//默认的升序排列
}
sort(A,A+100,cmp1);

所以上题也可以用sort()做一定简化。。