音视频开发之旅（24) 算法系列-快速排序

vlambda
2021-01-25

音视频开发之旅（24) 算法系列-快速排序

一、递归

递归就是自己调用自己
递归递归，有递就要有归，只递不归导致程序崩溃。
为了避免程序崩溃，递归函数中一定要包含条件语句，在合适的时候终止递归。
如果逻辑上不知道，何时该退出递归，可以加个深度depth的判断。

如果递归中有多个递归自己，该如何
比如，我们来看下下面这个函数的输出结果是多少？

#include <iostream>

using namespace std;

int fx(int x)
{
    if(x>0)
    {
        int a=0;
        int b=0;
        a = x+fx(x-1);
        b = x+fx(x-2);
        return a+b;
    } else {
        return 0;
    }
}

int main(void) {

   cout<<"fx(2)="<<fx(2)<<endl;
   return 0;
}

有了函数栈帧的概念，我们在回到上面的实例代码，画下递归函数的调用，看下它的执行过程

通过编译器运行结果和我们分析的一样

@"fx(2)=6\r\n"

因为下面要讲的快速排序算法以及堆排序算法都会用到递归调用，特别是递归函数中有多处调用递归的场景，通过这一小节的学习实践，我们从函数栈帧上来分析递归函数的调用。
下面我们开始快速排序算法的学习。

二、快速排序

快速排序和冒泡排序一样都属于交换排序，不同在于，快速排序不是通过两两相邻比较每一轮只把一个元素冒泡到顶端，而是引入了基准元素的概念，每一轮挑选一个基准元素（一般把第数组的第一个作为基准元素），让比它大的元素移动到一端，比它小的元素移动到另外一端。然后在不断的递归调用，从而实现快速排序。

冒泡排序是每次遍历都要相邻元素对比，且每一轮只把一个元素冒泡到顶端，时间复杂度是O(n^2)。而快速排序采用加入基准元素pivot （一般把第数组的第一个作为基准元素），有两个游标分别指向right和left，先从right开始和基准元素进行对比，如果大于等于基准元素，则游标减一移动，否则就赋值给left元素，接着left元素和基准元素进行对比，如果小于等于基准元素，则游标加一向后移动，否则把left游标指向的值赋值给right游标指向的值。直到left和right重叠，把基准元素赋值给重叠后游标指向的值。这样就把小于等于基准元素的值聚集左侧，大于等于基准元素的值聚集在右侧，然后进行迭代。直到剩下左右都是只有一个元素为止，从而实现快速排序
每一轮的比较和交换，需要把数组中全部元素都遍历一遍，时间复杂度是O(n),假设有n个元素，那么平均情况下需要O(logn)轮，总体对应的时间复杂度是O(nlogn)

为了更好的理解快速排序的原理，我们来画下具体的执行流程

通过上图所示的执行流程，我们知道了如何实现快速排序，原理懂了，那么代码该如何实现呐？下面我们通过代码实现快速排序

#include <iostream>
#include<array>
#include<algorithm>

using namespace std;


void printSortArray(int myarray[],int size){

        for(int k=0; k<size; k++)
        {
            cout<<myarray[k]<<" ";
        }
        cout<<endl;
}


void quickSort(int *a,int start,int end){
    //为了递归调用是能够正常结束
    if(start>=end)
    {
        return;
    }
    //不能改变start end本事的值，原因是递归判断是要用于左右区间
    int left = start ;
    int right= end ;

    //用第一个位置的元素作为 基准元素
    int pivot = a[left];

   // 一次遍历 对应的时间复杂度是O(n),
   // 后续要递归logn轮，对应的时间复杂度是O（logn），总的时间复杂度为O（nlogn）
    while (left < right)
    {
        //先从右侧游标位置开始和pivot进行对比，如果大于等于pivot，则向前移动游标，如果小于则把该位置的值赋值给a[left],此时a[right]的值和a[left]相等，但是没关系，左侧游标对应位置大于pivot时，会给a[right赋值]
        while (left<right && a[right]>=pivot)
        {
            right--;
        }
        a[left] = a[right];

        //然后从左侧游标位置开始和pivot进行大小对比，如果小于等于pivot，则游标向后移动；如果大于则把该值赋值给a[right]，同理此时a[left]和a[right]值相等，等待后续处理（如果左右游标位置重叠了，把pivot赋值给他们）
    
        while (left<right && a[left]<=pivot)
        {
            left++;
        }
        a[right] = a[left];
    }

    //left 和right重叠，此时把pivot赋值给left位置的值
    a[left]  = pivot;

    //递归调用左边和右边
    quickSort(a,start,left-1);
    quickSort(a,left+1,end);
}


int main(void) {
   int myarray[] ={3,4,2,1,6,5,9,8,7};
   int size = sizeof(myarray)/sizeof(myarray[0]) ;

   cout<<"size="<<size<<endl;
   quickSort(myarray,0,size-1);

   printSortArray(myarray,size);

    return 0;
}

---》输出结果如下

@"size=9\r\n"
@"1 2 3 4 5 6 7 8 9 \r\n"

这篇就到这里了，最耗时的是原理的理解，通过画图一步一步的分析执行流程，帮助我们更好的对递归和快速排序原理的理解。下一篇我们继续来学习实践另外一种排序算法：堆排序。来一起学习成长吧。

五、资料

《漫画算法》
《算法》
[【一听就懂】什么是递归？] : https://www.bilibili.com/video/BV194411f71o?p=2

六、收获

理解了递归函数中多次触发递归的执行逻辑
理解了快速排序的原理，以及通过代码进行实现

感谢你的阅读

欢迎交流

vlambda博客
学习文章列表