Fork me on GitHub

算法-快速排序算法

发表于 | 分类于 | 阅读次数
面试算法之----快速排序算法（摘自数据结构与算法经典问题解析264页问题10.11 ）

快速排序算法是分治算法技术的一个实例，也称为分区交换排序。快速排序采用递归调用对元素进行排序，是基于比较的排序算法中的一个著名算法，也是面试常考的一个算法。

本文主要思想借鉴于这篇文章：

白话经典算法系列之六 快速排序 快速搞定
http://blog.csdn.net/morewindows/article/details/6684558

时间复杂度：

  • 时间复杂度：O(nlogn)
  • 空间复杂度：O（1）
    性能：

假设快速排序的复杂度为T(n) 且所有元素都不相同。T(n) 取决于两个子问题的规模，而规模又取决于中枢点。

  • 最好情况：每个划分把数组分成相等的两部分。时间复杂度为（nlogn）；
  • 最坏情况：每个划分把数组分成不相等的两部分。时间复杂度为（n^2）,最坏情况发生在序列已经排序且选择最后一个元素作为中枢点。
  • 平均情况下的时间复杂度与最好情况一样也为（nlogn）；

基本思想：

书上说该算法主要由以下四步组成：

  1. 如果数组中仅有一个元素或者没有元素需要排序，则返回。
  2. 选择数组中的一个元素作为中枢点（通常选择数组最左边的元素）。
  3. 把数组分成两部分，一部分元素大于中枢点，一部分元素小于中枢点。
  4. 对两部分数组递归调用该算法。

借鉴参考文章，在这里我们巧妙的把它翻译为这样一种思想：

挖坑填数、分而治之。

操作过程如下：

假设有如下数组，且拟定有一个数组 A[4,6,2,9,1,17] ，下标为index，和两个指针 left 和 right，和一个保存中枢点的变量 temp。

初始时，取第一个元素为中枢点，此时：left = 0; right = 5; temp = A[left] = 4;
这里写图片描述
由于已经将A[0]中的数保存到temp中，可以理解成在数组A[0]上挖了个坑，可以将其它数据填充到这来。

1、首先从右向左，寻找第一个比temp小的数，准备填充到A[0]的位置上。
当right=4时满足情况，于是将A[4] 挖走，填充到上一个坑A[0]处，并且left++；此时：left=1；right=4；temp=4；形成新坑A[4]。
这里写图片描述
2、开始从左往右，寻找第一个比temp大的数，准备填充到A[4]的位置上。当left=1时，便满足条件，于是将A[1]挖走，填到上一个坑A[4]处，并且right–；此时：left=1；right=3；temp=4；形成新坑A[1];
这里写图片描述
3、开始从右往左，寻找第二个比temp小的数，准备填充到A[1]的位置上。
当right=2时满足情况，于是将A[2] 挖走，填充到上一个坑A[1]处，并且left++；此时：left=2；right=2；temp=4；形成新坑A[2]。
这里写图片描述
4、此时left=right，则第一趟排序结束，将temp填充到中枢点index=2的位置上，可以看到，4的左边都比4小，右边都比4大。
这里写图片描述
5、得到新的中枢点后，递归对左边和右边重复上述过程即可完成整个排序。

对挖坑填数进行总结（引用自上述参考文章）：

1．i =L; j = R; 将基准数挖出形成第一个坑a[i]。
2．j–由后向前找比它小的数，找到后挖出此数填前一个坑a[i]中。
3．i++由前向后找比它大的数，找到后也挖出此数填到前一个坑a[j]中。
4．再重复执行2，3二步，直到i==j，将基准数填入a[i]中。

算法实现（java）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
public static void sort(int[] A,int l,int r){
	int left=l;
	int right=r;
	// index为下标，temp用来保存中枢位置的值，无关数组A,只是一个临时变量而已
	int index,temp;
	
	if(A.length==0 || A.length==1){return;}
	if(left>right){return;}
	//选取中枢，通常选择最左边的元素
	temp=A[left];	
	while(left < right){
	//先从右向左找不大于temp的元素
	 while(left < right && A[right] > temp){  
		 right--;
	 }	
	 if(left < right){
		//挖right，填left
		A[left]=A[right];  
		//填完之后，left右移一位        
		left++;                   
	 }
	 //再从左向右找不小于temp的元素来填上一个坑
	 while(left < right && A[left] <= temp){  
		 left++;
	 }
	 if(left < right){
		 //挖left，填上一次的right
		 A[right]=A[left];   
		 //填完之后，right左移一位        
		 right--;					
	 }
	}
	//走到这一步，必然left==right，得到中枢位置，将temp插入中枢位置
	A[left]=temp; 	
	//下标index						
	index=left;					
	//执行完一次排序操作，再对左边和右边分别递归
	sort(A,l,index-1);
	sort(A,index+1,r);
}

测试程序：

1
2
3
4
5
6
7
8
9
10
11
public static void  main(String[] arg){
		// TODO Auto-generated method stub
		int[] A=new int[]{1,4,2,8,5,9,477,25,1};
		
		long time=System.nanoTime();
		sort(A, 0, A.length-1);
		System.out.println("耗时："System.nanoTime()-time);
		for (int i : A) {
			System.out.println(i);	
		}
	}

打印内容如下：

1
2
3
4
5
6
7
8
9
10
耗时：9659
1
1
2
4
5
8
9
25
477

csdn地址：http://blog.csdn.net/u012534831
github地址：https://github.com/qht1003077897
个人博客地址：https://qht1003077897.github.io
QQ：1003077897