21天打卡挑战 - 经典算法之快速排序

​​​​CSDN打卡活动产出
​

活动地址：CSDN21天学习挑战赛

学习的最大理由是想摆脱平庸，早一天就多一份人生的精彩；迟一天就多一天平庸的困扰。各位小伙伴，如果您：
想系统/深入学习某技术知识点…
一个人摸索学习很难坚持，想组团高效学习…
想写博客但无从下手，急需写作干货注入能量…
热爱写作，愿意让自己成为更好的人…
…

创作计划

**
机缘

实战项目中的经验分享
日常学习过程中的记录
通过文章进行技术交流
…

收获

希望以此结交到志同道合的朋友

提升个人算法基础水平
…

日常

平均每周产出2-3篇文章

有限的精力下，只能少一些玩游戏的时间，陪女朋友的时间不敢少

憧憬

期待粉丝上万 浏览过百万！！

**

学习计划

**
学习目标

永远充满热情，坚持21天学习打卡

学习内容

快速排序

学习日记

**
学习知识点

冒泡排序介绍

       又叫气泡排序，是经典的交换排序方法。整个过程就是在无序区中对相邻元素进行两两比较，将不满足相对顺序的一对儿元素进行交换,再进行下一对儿元素的比较。每一趟冒泡后，就会送一个最小的元素达到最上端。在无序区中重复这个过程，直到所有的元素有序。

快速排序

        快速排序是冒泡排序的改进算法，主要思想是在待排序列中取一个元素（通常为第一个)作为参照，将序列分为两个子序列，比参照值小的元素和比参照值大的元素各自组成一个子序列。每趟排序会使参照元素归位，并得到两个子序列。在子序列中继续执行该步骤，直到子序列的长度为0或1。

 

算法说明

        快速排序是一种划分交换排序方法，采用了分治策略。首先将原问题划分成若干个规模更小、与原问题相似的子问题，然后用递归方法解决这些子问题，最后再将它们组合成原问题的解。
        第一趟排好序列中的一个数，放在它应该在的位置上，同时得到两个子序列，左侧都是比它小的数，右侧都是比它大的数(升序排序时)。接下来在每个子序列中不断重复归位一个元素、得到子序列这个过程，直到子序列的长度为1或0，此时整体的序列已经有序。

复杂度

空间复杂度 ：logn
主要是由于递归造成的栈空间的使用，
最好的情况下其树的深度为：log2(n)
空间复杂度为 O(logn)
而最坏的情况下:需要n-1次调用，每2个数都需要交换，此时退化为冒泡排序
空间复杂度为 O(n)
平均时间复杂度为：O(logn)

时间复杂度 :  O(nlogn)
由于快速排序用到了递归调用，因此计算其时间复杂度也需要用到递归算法计算

平均时间复杂度O（nlogn），最坏时间复杂度O（n*n）,辅助空间O（logn）<每次都要分给一个额外空间，而总共有logn次> 
每次分成两段，那么分的次数就是logn了，每一次处理需要n次计算，那么时间复杂度就是nlogn了！
根据平均情况来说是O(nlogn),因为在数据分布等概率的情况下对于单个数据来说在logn次移动后就会被放到正确的位置上了。 
最坏是O(n^2).这种情况就是数组刚好的倒序，然后每次去中间元的时候都是取最大或者最小。