没有一身好内功,招式再多都是空;算法绝对是防身必备,面试时更是不可或缺;跟着算法渣一起从零学算法
定义
快速排序(Quicksort)是对冒泡排序的一种改进
快速排序由C. A. R. Hoare在1962年提出。
它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列
算法
设要排序的数组是A[0]……A[N-1],首先任意选取一个数据(通常选用数组的第一个数)作为关键数据,然后将所有比它小的数都放到它前面,所有比它大的数都放到它后面,这个过程称为一趟快速排序。值得注意的是,快速排序不是一种稳定的排序算法,也就是说,多个相同的值的相对位置也许会在算法结束时产生变动
一趟快速排序的算法是:
- 设置两个变量i、j,排序开始的时候:i=0,j=N-1;
- 以第一个数组元素作为关键数据,赋值给key,即key=A[0];
- 从j开始向前搜索,即由后开始向前搜索(j–),找到第一个小于key的值A[j],将A[j]和A[i]互换;
- 从i开始向后搜索,即由前开始向后搜索(i++),找到第一个大于key的A[i],将A[i]和A[j]互换;
- 重复第3、4步,直到i=j; (3,4步中,没找到符合条件的值,即3中A[j]不小于key,4中A[i]不大于key的时候改变j、i的值,使得j=j-1,i=i+1,直至找到为止。找到符合条件的值,进行交换的时候i, j指针位置不变。另外,i==j这一过程一定正好是i+或j-完成的时候,此时令循环结束)。
演示
上面的定义,算法都是很学术的表达,看得有点晕了,看一个示例:
对数组[2,10,8,22,34,5,12,28,21,11]进行快速排序
也可以通过动画更清晰了解整个排序过程
动画:http://www.zhuxingsheng.com/tools/sort/sort.html
实现
快速排序有好些实现手法,左右指针法、挖坑法、前后指针(快慢指针)法
左右指针法
算法过程与上面的演示图差不多
- 先从数列中取出一个数作为中轴基数。
- 分区过程,将比这个数大的数全放到它的右边,小于或等于它的数全放到它的左边。
- 再对左右区间重复第二步,直到各区间只有一个数
1 | /** |
挖坑法
挖坑填坑,也可以叫拆东墙补西墙
先演示一番,对[22,12,28,21,14]进行排序
index: | 0 | 1 | 2 | 3 | 4 |
---|---|---|---|---|---|
data: | 22 | 12 | 28 | 21 | 14 |
第一步:挖最右边的数为坑
坑: pit=array[right]=14;左索引: left=0,右索引: right=3,
index: | 0 | 1 | 2 | 3 | 4 |
---|---|---|---|---|---|
data: | 22 | 12 | 28 | 21 | X |
从left开始搜索,寻找比坑大的数,发现array[left=0]>14,那就用left=0 填 right=4的坑
array[right=4]=array[left=0];left++;
此时数组:
index: | 0 | 1 | 2 | 3 | 4 |
---|---|---|---|---|---|
data: | X | 12 | 28 | 21 | 22 |
left=1,right=3
第二步: 从right端开始找比pit小的数,发现array[1] < 14,那就用right=1 填 left=0的坑
array[left=0]= array[right=1];
此时数组:
index: | 0 | 1 | 2 | 3 | 4 |
---|---|---|---|---|---|
data: | 12 | X | 28 | 21 | 22 |
left=1,right=0; left>right,那此回合结束,用pit填回坑array[left=1]
结束时:
index: | 0 | 1 | 2 | 3 | 4 |
---|---|---|---|---|---|
data: | 12 | 14 | 28 | 21 | 22 |
发现14左都是小于它的数,右边都是大于它的数
以14为分界,两边数组进行递归下去,就行了
1 | int partion(int arr[], int begin, int end) |
前后指针法
大体思路:
- 定义两个指针,一前一后,cur(前)指向起始位置,prev(后)指向cur的前一个位置;选择数组最后一个元素作为key(right)
- cur找比key小的数,prev在cur没有找到的情况下,一直不动(即保证prev一直指向比key大的数);直到cur找到比key小的数(+ +prev && prev != cur时)然后++cur,prev仍然不动
- 直到cur走到right前一个位置,终止循环。最后++prev,交换prev和right的值。返回中间位置prev。最后再继续递归
1 | int partion(int arr[], int left, int right) |
分治
以上几个方法,不管怎样的思路,都是寻找一个标准数,让它成为一个分界,大于所有左边的数,小于所有右边的数,进行分而治之
复杂度
最好情况:最在最好的情况下,每次的划分都会恰好从中间将序列划分开来,那么只需要lgn次划分即可划分完成,是一个标准的分治算法Cn=2Cn/2+N,每一次划分都需要比较N次。时间复杂度O(nlogn)
最坏情况:在最坏的情况下,即序列已经排好序的情况下,每次划分都恰好把数组划分成了0,n两部分,那么需要n次划分,但是比较的次数则变成了n, n-1, n-2,….1, 所以整个比较次数约为n(n-1)/2~n2/2
比较和移动次数最少时间复杂度表示为O(nlogn);
比较和移动次数最多的时间复杂度表示为O(n^2);
使用的辅助存储空间最少为logn,最多为n^2;是不稳定的排序;
Best | Average | Worst | Memory | Stable |
---|---|---|---|---|
nlog(n) | nlog(n) | n^2 | log(n) | No |