排序专题

发表于   |   更新于 | 分类于

对堆排序和快速排序进行更新和整理

1. 堆排序（O(nlog(n))）

目的：构建一个大顶堆或小顶堆（堆顶元素为最大或最小）

其实堆的空间结构实际上就是一棵完全二叉树，不过堆有它自己的限定条件。大堆就是树中每个父亲节点都要比孩子节点大，并且两个兄弟之间是没有大小区分的。小堆与之相反，就是每个父亲节点都要比孩子节点小。

堆的空间结构虽然是个完全二叉树，但是这样的结构也是我们为了好理解才想出来的，实际上堆是通过数组的下标进行相应的排序，因为完全二叉树中的结点的编号可以算出来，这样就能与数组进行对应。

操作过程如下：

  • 初始化堆：构造成一棵完全二叉树
  • 从堆底的子树开始向上，保证每颗子树的根都是大根或小根（因为向上的时候子树的根可能也会被换走，所以每一次调整都要调整到底部），调整结束后，初始堆建立！

大顶堆：arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2]

小顶堆：arr[i] <= arr[2i+1] && arr[i] <= arr[2i+2]

上述的两个公式就是大根堆的建立的基础：

1.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
//构建大根堆
private int[] buildMaxHeap(int[] array){
    //从最底部的根节点开始（(array.length-2)/2）
    for(int i=(array.length-2)/2; i>=0; i--){
        adjustDownToUp(array, i, array.length);
    }
    return a
}
//将元素array[k]自下往上逐步调整树形结构
private void adjustDownToUp(int[] array, int k, int length){
    int temp = array[k];
    //对k为根的子树从上到下依次进行调整
    for(int i=2*k+1; i<length; i=2*i+1){
        //先比较左右子节点，大的才有资格和根进行比较
        if(i<length-1 && array[i]<array[i+1]){
            //如果是右节点大，则取右节点的下标
            ++i;
        }
        //如果子节点比根大，将两者进行调换。
        //如果根节点大，则停止调整(因为下面的都是调整过的)
        if(temp>=array[i]){
            break;
        }else{
            array[k] = array[i];//（这里会导致i的位置有个缺，需要被下面的大子节点或temp填上）
            k = i;//【关键】修改k值，以便继续向下调整
        }
    }
    array[k] = temp;//被调整的结点的值放人最终位置
}

1.2 堆排序

根和数组的尾部元素互换；

对排除尾部元素的剩余数组从0开始进行调整；

1
2
3
4
5
6
7
8
9
10
11
//堆排序
    public int[] heapSort(int[] array){
        array = buildMaxHeap(array); //初始建堆，array[0]为第一趟值最大的元素
        for(int i=array.length-1;i>1;i--){  
            int temp = array[0];  //将堆顶元素和堆低元素交换，即得到当前最大元素正确的排序位置
            array[0] = array[i];
            array[i] = temp;
            adjustDownToUp(array, 0,i);  //整理，将剩余的元素整理成堆
        }
        return array;
    }

1.3 移除数组最大值

1
2
3
4
5
6
7
8
9
//删除堆顶元素操作
    public int[] deleteMax(int[] array){
        //将堆的最后一个元素与堆顶元素交换，堆底元素值设为-99999
        array[0] = array[array.length-1];
        array[array.length-1] = -99999;
        //对此时的根节点进行向下调整
        adjustDownToUp(array, 0, array.length);
        return array;
    }

1.4 插入操作(在上一步的基础上)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
//插入操作:向大根堆array中插入数据data
    public int[] insertData(int[] array, int data){
        array[array.length-1] = data; //将新节点放在堆的末端
        int k = array.length-1;  //需要调整的节点
        int parent = (k-1)/2;    //双亲节点
        while(parent >=0 && data>array[parent]){
            array[k] = array[parent];  //双亲节点下调
            k = parent;
            if(parent != 0){
                parent = (parent-1)/2;  //继续向上比较
            }else{  //根节点已调整完毕，跳出循环
                break;
            }
        }
        array[k] = data;  //将插入的结点放到正确的位置
        return array;
    }