目录
- 递归
- 快速排序
- 资料
- 收获
一、递归
递归就是自己调用自己
递归递归，有递就要有归，只递不归导致程序崩溃。
为了避免程序崩溃，递归函数中一定要包含条件语句，在合适的时候终止递归。
如果逻辑上不知道，何时该退出递归，可以加个深度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
六、收获
- 理解了递归函数中多次触发递归的执行逻辑
- 理解了快速排序的原理，以及通过代码进行实现
感谢你的阅读
下一篇我们继续来学习实践另外一种排序算法：堆排序，欢迎关注公众号“音视频开发之旅”，一起学习成长。
欢迎交流
网友评论