3.5 快速排序
3.5.1 简介
快速排序是通过比较和交换位置来排序的排序算法,是对冒泡算法的一种优化。当数据量比较大的时候,推荐使用快速排序。快速排序的思想是:通过一次排序将无序的数据分为两个独立部分,其中一部分数据的值均比另一部分要小,再对这两部分分别进行排序,使得整个序列有序。简单来说,就是从所有数据中取一个基准值,不大于该基准值的为一部分,大于基准值的为一部分,再在这两部分中分别取基准值再继续分别分为两部分,以此类推,直到剩下的部分只有一个元素,则结束。
3.5.2 步骤
快速排序的两种方法:填坑法和前后指针法
填坑法步骤:
取序列A中第一个元素为基准值,并且取两个索引i=0,j=n-1,准备临时变量temp = A[i];
从右开始寻找小于基准值temp的数(j– && j > i),得到值A[j],填坑:A[i]=A[j]
从左开始寻找不小于基准值temp的数(i++ && j>i),得到值A[i],填坑:A[j]=A[i]
重复操作2和操作3,直到i==j,则A[i]=temp
将序列分为0 ~ i-1 和i+1 ~ n-1两部分,继续重复步骤1、2、3、4,直到最后的序列只剩下一个元素。
填坑法的重点:不动的指针所指的位置是坑位
如图:
前后指针法的步骤:
取序列A中第一个元素为基准值,并且取两个索引i=0,j=n-1,准备临时变量begin= i;
从右开始寻找不大于基准值temp的数(j– && j > i),得到值A[j]
从左开始寻找大于基准值temp的数(i++ && j>i),得到值A[i],交换值A[i]和值A[j]
重复操作2和操作3,直到i==j,交换A[i]和A[begin]的值
将序列分为0 ~ i-1 和i+1 ~ n-1两部分,继续重复步骤1、2、3、4,直到最后的序列只剩下一个元素。
如图:
3.5.3 总结
快速排序是一种分而治之的思想,通过基准值将序列划分为两段小序列,然后继续划分,直到划分到只有一个元素或者为空的序列,结束继续划分。其最坏时间复杂度是O(n²),平均的时间复杂度为O(nlogn),空间复杂度为O(logn),是一种不稳定算法。
3.5.4 快速查找
和快速排序是一个思想
1.确定一个分界点
2.调整区间
3.递归处理左右两段
问题是,现在只要找到第k个数,所以不需要完全做完左右两个区间的调整。
于是判断第k个数在左边还是右边,只需要处理一边即可
引用:
1.快速排序详解