快速排序(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的相对位置发生了改变,所是快速排序是一种不稳定排序。