[题解] 《算法零基础100讲》(第37讲) 排序进阶 - 快速排序

• • 源码剖析
  • 539. 最小时间差
  • 977. 有序数组的平方

动画演示地址

void quick_sort(vector& n,int l,int r) {
    if(l>=r) return;
    //如果当前区间只有一个元素或者说已经不是一个区间了就直接退出
    int x=n[l+r>>1];
    //设置一个基准元素（这里以区间的中间元素作为基准）
    int i=l-1,j=r+1;
    //两根指针分别指向基准的左右两边
    while(ix);
        //同理右边的元素应该全部大于基准，所以循环找到第一个基准右边的小于基准的元素
        if(i 
539. 最小时间差 
 
 
所有时间全部统一单位（分）以后进行排序，然后计算相邻两个时间的差值即可。注意有可能一个时间与另一个时间的最小间隔是前一天和后一天，所以应该把1440+分钟表示的时间也放进数组
 
 
class Solution {
public:
    void quick_sort(vector& n,int l,int r) {
        if(l>=r) return;
        int x=n[l+r>>1];
        int i=l-1,j=r+1;
        while(ix);
            if(i& timePoints) {
        vectorres;
        int ans=0x3f3f3f3f;
        for(auto t:timePoints)
        {
            int h=t[0]-'0',m=t[3]-'0';
            h=h*10+(t[1]-'0');
            m=m*10+(t[4]-'0');
            res.push_back(h*60+m);
            res.push_back(1440+h*60+m);
        }
        quick_sort(res,0,res.size()-1);
        for(int i=0;i 
977. 有序数组的平方 
class Solution {
public:
    void quick_sort(vector& n,int l,int r) {
        if(l>=r) return;
        int x=n[l+r>>1];
        int i=l-1,j=r+1;
        while(ix);
            if(i sortedSquares(vector& nums) {
        for(int i=0;i