发布时间:2018-04-19作者:laosun阅读(1787)
java选择排序—堆排序(Heap Sort),堆排序是一种树形选择排序,是对直接选择排序的有效改进。堆的定义如下:具有n个元素的序列(k1,k2,...,kn),当且仅当满足
堆排序是一种树形选择排序,是对直接选择排序的有效改进。
基本思想:
堆的定义如下:具有n个元素的序列(k1,k2,...,kn),当且仅当满足
时称之为堆。由堆的定义可以看出,堆顶元素(即第一个元素)必为最小项(小顶堆)。
若以一维数组存储一个堆,则堆对应一棵完全二叉树,且所有非叶结点的值均不大于(或不小于)其子女的值,根结点(堆顶元素)的值是最小(或最大)的。如:
(a)大顶堆序列:(96, 83,27,38,11,09)
(b) 小顶堆序列:(12,36,24,85,47,30,53,91)
初始时把要排序的n个数的序列看作是一棵顺序存储的二叉树(一维数组存储二叉树),调整它们的存储序,使之成为一个堆,将堆顶元素输出,得到n 个元素中最小(或最大)的元素,这时堆的根节点的数最小(或者最大)。然后对前面(n-1)个元素重新调整使之成为堆,输出堆顶元素,得到n 个元素中次小(或次大)的元素。依此类推,直到只有两个节点的堆,并对它们作交换,最后得到有n个节点的有序序列。称这个过程为堆排序。
因此,实现堆排序需解决两个问题:
1. 如何将n 个待排序的数建成堆;
2. 输出堆顶元素后,怎样调整剩余n-1 个元素,使其成为一个新堆。
首先讨论第二个问题:输出堆顶元素后,对剩余n-1元素重新建成堆的调整过程。
调整小顶堆的方法:
1)设有m 个元素的堆,输出堆顶元素后,剩下m-1 个元素。将堆底元素送入堆顶((最后一个元素与堆顶进行交换),堆被破坏,其原因仅是根结点不满足堆的性质。
2)将根结点与左、右子树中较小元素的进行交换。
3)若与左子树交换:如果左子树堆被破坏,即左子树的根结点不满足堆的性质,则重复方法 (2).
4)若与右子树交换,如果右子树堆被破坏,即右子树的根结点不满足堆的性质。则重复方法 (2).
5)继续对不满足堆性质的子树进行上述交换操作,直到叶子结点,堆被建成。
称这个自根结点到叶子结点的调整过程为筛选。如图:
再讨论对n 个元素初始建堆的过程。
建堆方法:对初始序列建堆的过程,就是一个反复进行筛选的过程。
1)n 个结点的完全二叉树,则最后一个结点是第个结点的子树。
2)筛选从第个结点为根的子树开始,该子树成为堆。
3)之后向前依次对各结点为根的子树进行筛选,使之成为堆,直到根结点。
如图建堆初始过程:无序序列:(49,38,65,97,76,13,27,49)
算法的实现:
从算法描述来看,堆排序需要两个过程,一是建立堆,二是堆顶与堆的最后一个元素交换位置。所以堆排序有两个函数组成。一是建堆的渗透函数,二是反复调用渗透函数实现排序的函数。
/** * 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,。从根到叶的筛选,元素比较次数至多2(k-1)次,交换记录至多k 次。所以,在建好堆后,排序过程中的筛选次数不超过下式:
而建堆时的比较次数不超过4n 次,因此堆排序最坏情况下,时间复杂度也为:O(nlogn )。
版权属于: 技术客
原文地址: https://www.sunjs.com/article/detail/35fc6825dff141059b6c7d16571cf6fb.html
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。