快速排序

发表于   |   分类于   |  

快速排序

快速排序（quicksort）是在实践中最快的已知排序算法，平均运行时间是O(NlogN),最坏的性能为：O(N^2).

基本的算法思路（一个数组S）：

  • 如果S中的元素个数是0或1，返回
  • 取S中任一元素v，称之为枢纽元（pivot）
  • 将大于v的元素放在v的右边为S1，小于v的元素放在v的左边为S2
  • 返回quicksort(S1),然后quicksort(S2)

选取合适的枢纽元，能提高效率。

  • 取数组的第一个或最后一个（不推荐）
  • 随机(小几率最坏的性能)
  • 三数中值分割法（Median-of-Three Partitioning）
  • 三数中值+插入排序(快排的优化)—对于很小的数组，快排不如插入好。一种好的截至范围是N=10

简单的快排

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
/*
 * select unsorted[0] as pivot.This is not a better way!
 */
public class Quick_Sort {
	public static void quickSort(int[]unsorted,int left,int right){
		int pivot;
		if(left<right){
			pivot=partition(unsorted,left,right);
			quickSort(unsorted,left,pivot-1);
			quickSort(unsorted,pivot+1,right);
		}
	}
	public  static int partition(int[] unsorted, int left, int right) {

		int pivotkey=unsorted[left];
		while(left<right){
			while(left<right&&unsorted[right]>=pivotkey)
				right--;
			unsorted[left]=unsorted[right];
			while(left<right&&unsorted[left]<=pivotkey)
				left++;
			unsorted[right]=unsorted[left];
		}
		unsorted[left]=pivotkey;
		return left;
	}
	public static void main(String args[]){
		int []unsorted={1,3,5,4,2,5,2,5,4,6,7};
		quickSort(unsorted,0,unsorted.length-1);
		for(int i :unsorted){
			System.out.print(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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
public class Quick {
	/*
	 * Switch a and b
	 */
	public static void Swap(int[]a,int left,int right){
		int temp=a[left];
		a[left]=a[right];
		a[right]=temp;
	}
	/*
	 * return median of left ,center and right
	 * 
	 */
	public static int  Median3(int []a,int left ,int right){

		int center=(left+right)/2;
		if(a[left]>a[right])
			Swap(a,left,right);
		if(a[left]>a[center])
			Swap(a,left,center);
		if(a[center]>a[right])
			Swap(a,center,right);
		/*
		 * invariant: unsort[left]<=unsort[center]<=unsort[right]
		 */
	Swap(a,center,left);/* put pivot at unsorted[0] */	
		return a[left];/* return pivot*/
		
	}
	public static void quickSort(int[]unsort,int left,int right){
		int pivot;
		if(left<right){
			pivot=partition(unsort,left,right);
			quickSort(unsort,left,pivot-1);
			quickSort(unsort,pivot+1,right);
		}
	}
	public  static int partition(int[] unsort, int left, int right) {
		int pivotkey=Median3(unsort, left, right);
		while(left<right){
			while(left<right&&unsort[right]>=pivotkey)
				right--;
			unsort[left]=unsort[right];
			while(left<right&&unsort[left]<=pivotkey)
				left++;
			unsort[right]=unsort[left];
		}
		unsort[left]=pivotkey;
		return left;
		}
	public static void main(String args[]){
		int []unsorted={4,5,6,34,4,1,4,31,4};
		quickSort(unsorted,0,unsorted.length-1);
		for(int i :unsorted){
			System.out.print(i+" ");
		}
	}
}

三数中值+插入排序(快排的优化)

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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
public class QuickSort_Better {
	/*
	 * Switch a and b
	 */
	public static void Swap(int[]a,int left,int right){
		int temp=a[left];
		a[left]=a[right];
		a[right]=temp;
	}
	
	/*
	 * return median of left ,center and right
	 */
	public static int  Median3(int []a,int left ,int right){
		int center=(left+right)/2;
		if(a[left]>a[right])
			Swap(a,left,right);
		if(a[left]>a[center])
			Swap(a,left,center);
		if(a[center]>a[right])
			Swap(a,center,right);
		
		// invariant: unsort[left]<=unsort[center]<=unsort[right]
	Swap(a,center,left);/* put pivot at unsorted[0] */	
		return a[left];/* return pivot*/
	}
	public static void quickSort(int[]unsort,int left,int right){
		if(unsort==null||left<0||right<=0||right>=unsort.length||left>right){
			System.out.println("Invalid Parameters");
		}
	else{
		int pivot;
		if(left<right){
			if(right-left+1<=10)//unsort's length  is less than 10 than insertsort
				InserSort(unsort, left, right);
			else{
				pivot=partition(unsort,left,right);
				quickSort(unsort,left,pivot-1);
				quickSort(unsort,pivot+1,right);
		}
		}
	}
	}
	public static void InserSort(int[]unsort, int left, int right) {
		for(int i=left+1;i<right+1;i++){
			int temp=unsort[i],j;
			for(j=i-1;j>=left&&temp<unsort[j];j--)
				unsort[j+1]=unsort[j];
			unsort[j+1]=temp;
		}
	}
	public  static int partition(int[] unsort, int left, int right) {
		int pivotkey=Median3(unsort, left, right);
		while(left<right){
			while(left<right&&unsort[right]>=pivotkey)
				right--;
			unsort[left]=unsort[right];
			while(left<right&&unsort[left]<=pivotkey)
				left++;
			unsort[right]=unsort[left];
		}
		unsort[left]=pivotkey;
		return left;
		}
	public static void main(String args[]){
		int []unsorted={6,5,8,2,4,1,7,9,12,10,3,11,6,10,1,1,2,};
		quickSort(unsorted,0,unsorted.length-1);
		for(int i :unsorted){
			System.out.print(i+" ");
		}
	}
}

快排再优化（处理含有大量相同元素的情况）

…later…