By

文章目录
  1. 1. 快速排序

快速排序

思想：分治思想：

- 分解：数组A[p..r]被划分为两个(可能为空)子数组A[p..q-1]和A[q+1..r]，使得A[p..q-1]中的每一个元素都 <=A[q]，

        而A[q+1..r]中的每一个元素都都 >=A[q]。其中，计算下标q 也是划分过程的一部分。

- 解决：通过递归调用，对子数组A[p..q-1]和A[q+1..r]进行排序。

- 合并：子数组是原址排序的，所有不需要合并操作：数组A[p..r]已经有序。

应用场景：适用于大量数据排序，是原址排序。譬如找一堆数据的第K大(小)元素。

情景 时间复杂度 备注
理想 O(nlgn) 划分平衡(划分是常数比例的)
最坏 O(n^2) 划分非平衡

不稳定排序

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
//java code
public static void quickSort(int[] array,int start,int end){
	   if(start < end){
			//r位置元素是最终元素的位置；
			int r = partition(array,start,end);
			quickSort(array,start,r-1);
			quickSort(array,r+1,end);
	   }
}
//实现对A[p..r]原址排序
public static int partition(int[] array,int start,int end){
	   //选一个基准元素作为比较的元素，为方便，我们选最后一个元素；
	   int x = array[end];
	   
	   /*
	   * 将数组划分为3段：
	   * start~i：元素 <= x;
	   * i~j: 元素 > x;
	   * j~end：待处理的元素
	   */
	   int i = start - 1;
	   for(int j = start; j < end; j++){
			if(array[j] <= x){
				swap(array,++i,j);
			}
	   }
	   
	   //将基准元素放到自己的位置上；
	   swap(array,++i,end);
	   
	   return i;
}
public static void swap(int[] array,int i,int j){
		//异或交换注意 i！= j;否则 自己异或 将使结果为 0
		if(i == j){return;}
		array[i] ^= array[j];
		array[j] ^= array[i];
		array[i] ^= array[j];
}
public static void main(String[] args){
	  int[] array  = new int[]{2,8,45,0,7,5,99};
	  quickSort(array,0,array.length-1);
	  
	  for(int i = 0 ;i<array.length ;i++){
		  System.out.println(array[i]);
	  }
}
文章目录
  1. 1. 快速排序