说说算法那些事-快速排序

快速排序（Quicksort）是对冒泡排序的一种改进。查看完整代码

1.算法思想：通过一个基准值把将要排序的元素分成两部分，左边的元素都小于基准值，右边的元素都大于基准值，然后再按此方法对这两部分元素分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序。

2.算法步骤：(1)、设置开始变量值i，j，初始化值为 i = 0，j = count -1；

(2)、一般以第一个元素作为基准值temp，从j元素开始向前搜索，即j--，找到小于temp的值array[j]，然后在两个值互换array[i] = array[j];

(3)、从i元素开始向后搜索，即i++,找到大于temp的值array[i]，然后将两值互换即array[j] = array[i],

(4)、将temp赋值到array[I]，这样以后，temp左边值都小于temp，右边都大于temp，一次递归完成，然后左边 右边分成两部分，重复以上步骤。即可排成有序数组。

3.图解：

4.算法分析：

时间复杂度:最好的情况是 基准值是元素的中间值，时间复杂度为:O(nlog2n)(以2为底),最坏的情况是 基准值是最大或者最小值，时间复杂度为O(n2),平均时间复杂度：0(nlogn)。

空间复杂度：为O(log2n)(以2为底).

稳定性：.两个5的相对位置发生了改变，所是快速排序是一种不稳定排序。