Java基础算法-排序-快排

快排神马的，就是各路考官最爱问的东西：

在我自己的理解中，快排是这样的：

实现原理

  • 1.先选择数组中的一个数，作为一个基准（一般情况下选第一个）
  • 2.然后对整个数组进行第一次遍历，把小于基准的数扔到及基准数的左边，大于的数扔到右边。
  • 3.一遍遍历结束后，基准左边的数都小于基准，右边都大于基准，然后以基准为界可以得到两个新数组，对新数组重复1、2步骤。
  • 4.不断递归调用之后得到的数组就是有序的。

时间复杂度

像一般java中Array.sort底层实现就是采用的快排，一般快排的效率都是蛮高的，但是快排最坏的情况下时间复杂度也为O(n^2)
,比说一组数组本身就是有序的，倒序，然后基准为第一个数，这样用快排排数组就是最坏情况下的时间复杂度，当然一般情况下平均事件复杂度都为：O(nlog(n))

代码实现

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 class QuicklySort {
	public int getMid(int[] num,int low,int high){
		int temp = num[low];
		while(low < high){
			while(low < high && num[high] >= temp){
				high--;
			}
			num[low] = num [high];
			while(low < high && num[low] <= temp){
				low ++;
			}
			num[high] = num[low];
		}
		num [low] = temp;
		return low;
	}
	
	public void QuickSort(int[] num,int low,int high){
		if(low < high){
			int mid = getMid(num, low, high);
			QuickSort(num,mid+1,high);
			QuickSort(num,low,mid-1);
		}
	}
	
	public void sort(int[] num){
		if(num.length > 0){
			QuickSort(num,0,num.length-1);
		}
	}
	
	@Test
	public void DoSort(){
		int num[] = {1,3,7,6,4,2,11};
		sort(num);
		for (int i = 0; i < num.length; i++) {
			System.out.println(num[i]);
		}
	}

其实针对最坏时间复杂度其实还有更好的解法：随机快排

随机定义那个基准数，就是大家所称的随机化快排，也是快排的一种变种，
我记得我曾看到一句戏言，这样的随机化快排遇到最坏的时间复杂度的几率只有1/(2^n),只够满足人一生的人品需求。

还有就是一种就是平衡化快排，就是把基准数尽量可能的取为中值—-即每次取值在第一个数，中间那个数，最后一个数做
比较，据说这样能提高尽两倍的性能，实际上我也没尝试过，不过算法书上这样写应该没错把= =。

最后说一句：算法这东西都是靠积累的，每天都要努力！come on everyone！

Algorithms