快速排序时间复杂度 递归算法的时间复杂度=递归次数*每次递归遍历的次数
我们来看一下快速排序算法的时间复杂度需要怎么来算呢？
代码实现:
//左右指针法 不断缩放 //思路 begin 找大的 end 找小的 //还要注意 如果是选end为key 则begin先走 否则end先走 //当选择end时候 因为当最后一次 end和begin差一个距离时候 如果先走end那会导致 //把实际较小的没有交换 因为换之前 大小是左边小右边大 如果end先走 等于把begin所在的较小的换到最后去 int PartSort1(int* a, int begin, int end) { int& key = a[end]; while (begin < end) { //begin找大 while (begin < end&&a[begin] <= key)//这里注意的是<= 小心有重复数字 begin++; //end找小 while (begin < end&&a[end] >= key) end--; if(begin<end) swap(a[begin], a[end]); } //最好出来begin位置 一定是大于key的 swap(a[begin], key); return begin; } void QuickSort(int* a, int begin,int end) { if (begin >= end) return; else { int div = PartSort1(a, begin, end); QuickSort(a, begin, div - 1); QuickSort(a, div+1, end); } }
快速排序我们可以近似的想成一个完全二叉树
一个数组的容量是N,第一层递归遍历的次数是N,因为数组里每个数字都需要和key比较,那么接下来遍历分出来的两个区间，总的遍历次数还会是近似是N,以此类推,直到分为最后一个,也就是说树的高度是lgn,也就是递归次数,所以时间复杂度是N*lgN.
进阶:
问题:
有100万个数字,找出第10万个大的,这个问题,首先不是大数据问题，内存是可以放下的,这是快速排序的变形问题,第10万个大的其实是让我们找div=10万,(快速排序返回的div,其实就是下标,也就是数字在数组的准确序号[序号指的是第几个大])下面给出实现代码
int PartSort1(int* a, int begin, int end) { int& key = a[end]; while (begin < end) { //begin找大 while (begin < end&&a[begin] <= key)//这里注意的是<= 小心有重复数字 begin++; //end找小 while (begin < end&&a[end] >= key) end--; if(begin<end) swap(a[begin], a[end]); } //最好出来begin位置 一定是大于key的 swap(a[begin], key); return begin; } void QuickSort(int* a, int begin,int end) { if (begin >= end) return; else { int div = PartSort1(a, begin, end); if(div==100000) return a[div] else if(div>100000) QuickSort(a, begin, div - 1); else QuickSort(a, div+1, end); } }
那这个代码的时间复杂度是多少呢？
我们可以用数形结合的方法，这个算法相当于一直走的是树的左枝,其余的都没有走,这其实就相当于变成了单链表,那遍历单链表的时间复杂度其实就是O(n),同理这个代码的时间复杂度也是O（n),
通过这个题我们可以看出数形结合有时候非常的清晰直观