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(),对于原始数据类型使用三向切分的快速排序,对于引用类型使用归并排序