Java算法-排序（堆排序）

发表于 | 分类于

堆的定义

堆这种数据结构是一种完全二叉树，堆分为最大堆和最小堆

  • 最大堆：二叉树中的任一顶点大于等于它的左右子节点
  • 最小堆：二叉树中的任一顶点小于等于它的左右子节点
    堆可以用数组来存储表示

优先队列

优先队列（Priority Queue）：特殊的队列，取出元素的顺序按照元素的优先权或关键字的大小，不是元素入队的先后顺序。
优先队列（堆）的使用场景： 

1. 任何时候返回最值元素；  
2. 数据太大存不下，要找出一定的最值元素；  
3. 合并若干不同来源的已经排序的源（索引优先队列）

优先队列的实现方式：

基于堆的优先队列

用堆实现优先队列的方法：
注：以下代码存储数据时从数组的下标1开始
代码实现：
最大堆实现的最大优先队列

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
73
  
public class MaxPQ<T extends Comparable<T>>{
	private T[] pq;	 //存队列数据的数组
	private int N=0;  //最终元素的个数
	//构造函数
	public MaxPQ(int maxN){
		pq=(T[])new Comparable[maxN+1];
	}
	//判断队列是否为空
	public boolean isEmpty(){
		return N==0;
	}
	//返回队列元素个数
	public int size(){
		return N;
	}
	//插入数据
	public void insert(T v){
		pq[++N]=v;
		swim(N);
	}
	//删除队列中最大元素并返回最大值
	public T delMax(){
		T max=pq[1];
		exch(1,N--);
		pq[N+1]=null;
		sink(1);
		return max;
	}
	//上浮
	private void swim(int k){
		while(k>1 && less(k/2,k)){
			exch(k/2,k);
			k=k/2;
		}
	}
	//下沉
	private void sink(int k){
		while(2*k<=N){
			int t=2*k;
			if(t<N && less(t,t+1)){
				t++;
			}
			if(less(k,t)){
				exch(k,t);
			}else{
				break;
			}
			k=t;
		}
	}
	private boolean less(int i,int j){
		return pq[i].compareTo(pq[j])<0;
	}
	private void exch(int i,int j){
		T temp=pq[i];
		pq[i]=pq[j];
		pq[j]=temp;
	}	
	public static void main(String[] args){
		MaxPQ<Integer> p=new MaxPQ<Integer>(10);
		int n=5;
		p.insert(88);
		p.insert(2);
		p.insert(56);
		p.insert(3);
		p.insert(42);
		while(n>0){
			System.out.println(p.delMax());
			n--;
		}		
	}
}

代码实现的最主要的功能是实现元素的优先级，快速找到并删除最大元素，插入元素（自动调整）
算法分析：

  1. 一颗大小为N的完全二叉树的高度为lgN；
  2. 含有N个元素的基于堆的优先队列，插入元素需要不超过lgN+1次比较，删除最大元素需要不超过2lgN次比较；
    最小堆实现的最小优先队列 
    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
    public class MinPQ<T extends Comparable<T>> {
    	private T[] pq;
    	private int N;
    	public MinPQ(int maxN){
    		pq=(T[])new Comparable[maxN+1];
    	}
    	public boolean isEmpty(){
    		return N==0;
    	}
    	public int size(){
    		return N;
    	}
    	public void insert(T v){
    		pq[++N]=v;
    		swim(N);
    	}
    	private void swim(int k){
    		while(k>1 && less(k,k/2)){
    			exch(k,k/2);
    			k=k/2;
    		}
    	}
    	public T deleteMin(){
    		T min=pq[1];
    		exch(1,N--);
    		sink(1);
    		return min;
    	}
    	private void sink(int k){
    		while(2*k<N){
    			int t=2*k;
    			if(t<k && less(t+1,t)){
    				t++;
    			}
    			if(less(t,k)){
    				exch(t,k);
    			}else{
    				break;
    			}
    			k=t;
    		}
    	}
    	private boolean less(int v,int w){
    		return pq[v].compareTo(pq[w])<0;
    	}
    	private void exch(int v,int w){
    		T temp=pq[v];
    		pq[v]=pq[w];
    		pq[w]=temp;
    	}
    }

    索引优先队列

    优先队列的一个缺点是无法直接访问队列中的元素(除了直接找到最大或最小的元素)，对其更新修改。
    用过建立索引优先队列来实现快速索引。创建两个数组：elements[]用来存储队列中的对象(不需要按连续存储)，pq[]用来存储队列中每个对象在elements[]中的索引。 通过这两个数组建立的映射关系，在构建优先队列的时候，不需要变动elements[]，只需要维护改变pq中的元素即可。当向队列中插入一个新的对象时，在elements中存储该对象，将其索引存储在pq中，并对这个索引值进行上浮操作维护优先队列

    在操作队列时，如果想更改队列中某个对象，比如像将索引为3的位置改为”b”，那么直接操作elements[3]=”b”，这时需要重新调整维护优先队列，在pq数组中队值为3的元素操作，但是并不知道pq中那个位置的值是3，只能通过顺序遍历查找。为了方便查找pq中的元素，创建一个qp数组，将pq中元素作为索引在qp中存储该元素在pq中的索引。

    在队列的操作中经常要交换两个元素，交换pq中的两个元素的同事也要交换qp中相应位置的元素。

    索引最小优先队列 
    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
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101
    102
    103
    public class IndexMinPQ<Key extends Comparable<Key>> {
    	private int pq[];
    	private int qp[];
    	private Key keys[];
    	private int maxN;
    	private int N;
    	public IndexMinPQ(int maxN){
    		this.maxN=maxN;
    		N=0;
    		pq=new int[maxN+1];//这些数组中0索引处不存储值
    		qp=new int[maxN+1];
    		keys=(Key[])new Comparable[maxN];
    		for(int i=0;i<=maxN;i++){
    			qp[i]=-1;
    		}
    	}
    	public boolean isEmpty(){
    		return N==0;
    	}
    	public int size(){
    		return N;
    	}
    	public boolean contains(int i){
    		//这里的i检查的是keys在索引i处是否有值
    		if(i<0 || i>maxN){
    			throw new IllegalArgumentException();
    		}
    		return qp[i]!=-1;
    	}
    	public void insert(int k,Key key){
            if ( k< 0 || k> maxN) throw new IllegalArgumentException();
            if (contains(k)) throw new IllegalArgumentException("index is already in the priority queue");
    		keys[k]=key;
    		pq[++N]=k;
    		qp[k]=N;
    		swim(N);
    	}
    	//返回队列中的最小值
    	public Key minKey(){
    		return keys[pq[1]];
    	}
    	//删除并返回队列中的最小值
    	public Key deleteMin(){
    		if (N == 0) throw new NoSuchElementException("Priority queue underflow");
    		Key min=keys[pq[1]];
    		pq[1]=pq[N--];
    		sink(1);
    		return min;
    	}
    	//删除并返回队列中的某个值
    	public void delete(int k){
    		if (k < 0 || k > maxN) throw new IllegalArgumentException();
    	    if (!contains(k)) throw new NoSuchElementException("index is not in the priority queue");
    	    int index=qp[k];	   
    	    pq[index]=pq[N--];
    	    swim(index);
    	    sink(index); 
    	    keys[k]=null;
    	    qp[k]=-1;
    	}
    	//改变队列中某个对象的值
    	public void changeKey(int k,Key key){
    		if (k < 0 || k > maxN) throw new IllegalArgumentException();
    	    if (!contains(k)) throw new NoSuchElementException("index is not in the priority queue");
    		keys[k]=key;
    		swim(qp[k]);
    		sink(qp[k]);
    	}
    	//上浮调整
    	private void swim(int k){
    		while(k>1){
    			if(less(k,k/2)){
    				exch(k,k/2);
    			}
    			k=k/2;
    		}
    	}
    	//下沉调整
    	private void sink(int k){
    		while(2*k<=N){
    			int t=2*k;
    			if(t<N && less(t+1,t)){
    				t=t+1;
    			}
    			if(less(k,t)){
    				exch(k,t);
    			}else{
    				break;
    			}
    			k=t;
    		}
    	}
    	private boolean less(int k,int v){
    		return keys[pq[k]].compareTo(keys[pq[v]])<0;
    	}
    	private void exch(int k,int v){
    		int temp=pq[k];
    		pq[k]=pq[v];
    		pq[v]=temp;
    		qp[pq[k]]=k;
    		qp[pq[v]]=v;
    	}
    }

堆排序

堆排序分为两个阶段，给定一个无序的数组，首先要做的事构造堆。
a.将无需序列构建成一个堆，根据升序降序需求选择最大堆或最小堆;
b.将堆顶元素与末尾元素交换，将最大元素”沉”到数组末端，N–将最大的元素固定,再次调整不在去管它;
c.重新调整结构，使其满足堆定义，然后继续交换堆顶元素与当前末尾元素，反复执行调整+交换步骤，直到整个序列有序。
对于给定的无序构造堆的一个高效方法就是从右向左进行sink下沉操作，不需要管叶子结点（叶子结点已经算作一个有堆，无法进行下沉操作），所以只需要扫描一半的数组元素。
示意图：

堆排序算法实现：

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
  
public class HeapSort<T extends Comparable<T>> extends Sort<T> {
	@Override
	public void sort(T[] a){
		//数组a[0]不存储哨兵，a[0]的值一般用作，从a[1]开始
		int N=a.length-1;
		//构建堆
		for(int k=N/2;k>=1;k--){
			sink(a,k,N);
		}
		//堆排序
		while(N>1){
			exch(a,1,N--);
			sink(a,1,N);
		}	
	}
	private void sink(T[] a,int k,int N){
		while(2*k<=N){
			int j=2*k;
			if(j<N && less(a[j],a[j+1])){
				j++;
			}
			if(less(a[k],a[j])){
				exch(a,k,j);
			}else{
				break;
			}
			k=j;
		}
	}
	public static void main(String[] args){
		HeapSort<String> b=new HeapSort<String>();
		String[] str={"q","sss","aaa","ccc","qqq","bbb"};
		b.sort(str);
		for(int i=1;i<=str.length-1;i++){
			System.out.println(str[i]);
		}
	}
}

算法分析：

  1. 用下沉法构建堆（N个元素）只需少于2N次比较和少于N次的交换；
  2. 对N个元素的堆排序，需要少于（2NlgN+2N)次比较，一半次数的交换；

  3. 多种算法比较



    快速排序是最快的通用排序方法
    因为快速排序内循环指令少，他还能利用缓存（因为总是顺序访问数组），时间复杂度都是~cNlgN,使用三向切分后可能将某些时间复杂度变为线性级的。

Java 主要排序方法为 java.util.Arrays.sort()，对于原始数据类型使用三向切分的快速排序，对于引用类型使用归并排序