选择排序—堆排序(Heap Sort)

发布时间:2018-04-19作者:laosun阅读(494)

选择排序—堆排序(Heap

java选择排序—堆排序(Heap Sort),堆排序是一种树形选择排序,是对直接选择排序的有效改进。堆的定义如下:具有n个元素的序列(k1,k2,...,kn),当且仅当满足

    堆排序是一种树形选择排序,是对直接选择排序的有效改进。

    基本思想:

    堆的定义如下:具有n个元素的序列(k1,k2,...,kn),当且仅当满足

    1524121285616038774.jpg

    时称之为堆。由堆的定义可以看出,堆顶元素(即第一个元素)必为最小项(小顶堆)。
    若以一维数组存储一个堆,则堆对应一棵完全二叉树,且所有非叶结点的值均不大于(或不小于)其子女的值,根结点(堆顶元素)的值是最小(或最大)的。如:

    (a)大顶堆序列:(96, 83,27,38,11,09)

      (b)  小顶堆序列:(12,36,24,85,47,30,53,91)

    1524121297006052860.jpg

    初始时把要排序的n个数的序列看作是一棵顺序存储的二叉树(一维数组存储二叉树),调整它们的存储序,使之成为一个堆,将堆顶元素输出,得到n 个元素中最小(或最大)的元素,这时堆的根节点的数最小(或者最大)。然后对前面(n-1)个元素重新调整使之成为堆,输出堆顶元素,得到n 个元素中次小(或次大)的元素。依此类推,直到只有两个节点的堆,并对它们作交换,最后得到有n个节点的有序序列。称这个过程为堆排序

    因此,实现堆排序需解决两个问题:
    1. 如何将n 个待排序的数建成堆;
    2. 输出堆顶元素后,怎样调整剩余n-1 个元素,使其成为一个新堆。


    首先讨论第二个问题:输出堆顶元素后,对剩余n-1元素重新建成堆的调整过程。
    调整小顶堆的方法:

    1)设有m 个元素的堆,输出堆顶元素后,剩下m-1 个元素。将堆底元素送入堆顶((最后一个元素与堆顶进行交换),堆被破坏,其原因仅是根结点不满足堆的性质。

    2)将根结点与左、右子树中较小元素的进行交换。

    3)若与左子树交换:如果左子树堆被破坏,即左子树的根结点不满足堆的性质,则重复方法 (2).

    4)若与右子树交换,如果右子树堆被破坏,即右子树的根结点不满足堆的性质。则重复方法 (2).

    5)继续对不满足堆性质的子树进行上述交换操作,直到叶子结点,堆被建成。

    称这个自根结点到叶子结点的调整过程为筛选。如图:

    1524121313211006547.jpg

    再讨论对n 个元素初始建堆的过程。
    建堆方法:对初始序列建堆的过程,就是一个反复进行筛选的过程。

    1)n 个结点的完全二叉树,则最后一个结点是第1524121464496057448.jpg个结点的子树。

    2)筛选从第1524121473207081285.jpg个结点为根的子树开始,该子树成为堆。

    3)之后向前依次对各结点为根的子树进行筛选,使之成为堆,直到根结点。

    如图建堆初始过程:无序序列:(49,38,65,97,76,13,27,49)
                                  1524121327298056890.jpg


                                  1524121387655054538.jpg

     算法的实现:

    从算法描述来看,堆排序需要两个过程,一是建立堆,二是堆顶与堆的最后一个元素交换位置。所以堆排序有两个函数组成。一是建堆的渗透函数,二是反复调用渗透函数实现排序的函数。

    /**
     * Java实现快速排序算法 
     * 由大到小排序 
     * 两个步骤:1,建堆  2,对顶与堆的最后一个元素交换位置 
     */
    public class HeapSort {
    
    	public static void main(String[] args) {
    		int a[] = { 3, 1, 5, 7, 2, 4, 9, 6, 10, 8 };
    		HeapSort obj = new HeapSort();
    		System.out.println("初始值:");
    		obj.print(a);
    
    		for (int i = 0; i < a.length; i++) {
    			obj.createLittleHeap(a, a.length - 1 - i);// 创建堆,创建的是小顶堆。每次循环完,二叉树的根节点都是最小值,所以与此时的未排好部分最后一个值交换位置
    			obj.swap(a, 0, a.length - 1 - i);// 与最后一个值交换位置,最小值找到了位置
    			obj.print(a);
    			System.out.println();
    
    		}
    
    		System.out.println("\n排序后:");
    		obj.print(a);
    
    	}
    
    	/*
    	 * 创建小顶堆:双亲节点小于子节点的值。从叶子节点开始,直到根节点。这样建立的堆定位最小值
    	 */
    	private void createLittleHeap(int[] data, int last) {
    		for (int i = (last - 1) / 2; i >= 0; i--) { // 找到最后一个叶子节点的双亲节点
    			// 保存当前正在判断的节点
    			int parent = i;
    			// 若当前节点的左子节点存在,即子节点存在
    			while (2 * parent + 1 <= last) {
    				// biggerIndex总是记录较大节点的值,先赋值为当前判断节点的左子节点
    				int bigger = 2 * parent + 1;// bigger指向左子节点
    				if (bigger < last) { // 说明存在右子节点
    
    					if (data[bigger] > data[bigger + 1]) { // 右子节点>左子节点时
    
    						bigger = bigger + 1;
    					}
    				}
    				if (data[parent] > data[bigger]) { // 若双亲节点值大于子节点中最大的
    					// 若当前节点值比子节点最大值小,则交换2者得值,交换后将biggerIndex值赋值给k
    					swap(data, parent, bigger);
    					parent = bigger;
    				} else {
    					break;
    				}
    			}
    		}
    	}
    
    	public void print(int a[]) {
    		for (int i = 0; i < a.length; i++) {
    			System.out.print(a[i] + " ");
    		}
    	}
    
    	public void swap(int[] data, int i, int j) {
    		if (i == j) {
    			return;
    		}
    		data[i] = data[i] + data[j];
    		data[j] = data[i] - data[j];
    		data[i] = data[i] - data[j];
    	}
    }

    堆排序需要双层循环,第一层控制循环多少次,第二层得到每次的最小值(小顶堆)

    import java.util.ArrayList;
    
    public class Solution32 {
    	/*
    	 * 输入n个整数,找出其中最小的K个数。 例如输入4,5,1,6,2,7,3,8这8个数字, 则最小的4个数字是1,2,3,4,。
    	 */
    	public ArrayList<Integer> GetLeastNumbers_Solution(int[] input, int k) {
    		ArrayList<Integer> result = new ArrayList<Integer>();
    		if (k > input.length)
    			return result;
    		for (int i = 0; i < k; i++) {// 只排前k次
    			heapSort(input, i, input.length);// 进行第i次排序
    			result.add(input[i]);
    		}
    		return result;
    	}
    
    	private void heapSort(int[] input, int root, int end) {// 小顶堆实现
    		for (int j = end - 1; j >= root; j--) {
    			int parent = (j + root - 1) / 2;// 算出j节点的双亲节点的序号
    			if (input[parent] > input[j]) {// 双亲节点大于当前节点,交换位置。
    				int temp = input[j];
    				input[j] = input[parent];
    				input[parent] = temp;
    			}
    		}
    	}
    
    	public static void main(String[] args) {
    		int[] str = { 4, 5, 1, 6, 2, 7, 3, 8 };
    		Solution32 s = new Solution32();
    		System.out.print(s.GetLeastNumbers_Solution(str, 4));
    
    	}
    }
    /**
     * Java实现堆排序算法(改进)  
     * 由大到小排序 
     * 两个步骤:1,建堆  2,对顶与堆的最后一个元素交换位置
     */
    public class HeapSort {
    
    	public static void main(String[] args) {
    		int a[] = { 3, 1, 5, 7, 2, 4, 9, 6, 10, 8 };
    		HeapSort obj = new HeapSort();
    		System.out.println("初始值:");
    		obj.print(a);
    
    		for (int i = 0; i < a.length; i++) {
    			obj.createLittleHeap(a, a.length - 1 - i);// 创建堆,创建的是小顶堆。每次循环完,二叉树的根节点都是最小值,所以与此时的未排好部分最后一个值交换位置
    			obj.swap(a, 0, a.length - 1 - i);// 与最后一个值交换位置,最小值找到了位置
    			obj.print(a);
    			System.out.println();
    
    		}
    
    		System.out.println("\n排序后:");
    		obj.print(a);
    
    	}
    
    	/*
    	 * 创建小顶堆:双亲节点小于子节点的值。从叶子节点开始,直到根节点。这样建立的堆定位最小值
    	 */
    	private void createLittleHeap(int[] data, int last) {
    		for (int i = last; i > 0; i--) {
    			int parent = (i - 1) / 2;// 当前节点的双亲节点
    			if (data[parent] > data[i])
    				swap(data, parent, i);
    		}
    	}
    
    	public void print(int a[]) {
    		for (int i = 0; i < a.length; i++) {
    			System.out.print(a[i] + " ");
    		}
    	}
    
    	public void swap(int[] data, int i, int j) {
    		if (i == j) {
    			return;
    		}
    		data[i] = data[i] + data[j];
    		data[j] = data[i] - data[j];
    		data[i] = data[i] - data[j];
    	}
    }

    分析:

    设树深度为k,1524121346063041868.jpg。从根到叶的筛选,元素比较次数至多2(k-1)次,交换记录至多k 次。所以,在建好堆后,排序过程中的筛选次数不超过下式: 

                                    1524121353574080475.jpg

    而建堆时的比较次数不超过4n 次,因此堆排序最坏情况下,时间复杂度也为:O(nlogn )。


0 +1

版权声明

 Java  源码  算法

 请文明留言

0 条评论