排序算法之堆排序
堆排序是利用堆的数据结构而设计的一种排序算法，堆排序是一种选择排序。可以利用数组的特点快速定位制定索引的元素。
大顶堆和小顶堆
堆分为大根堆和小根堆，是一种完全二叉树，大顶堆的要求是每个节点的值都不大于其父节点的值（如下左图所示）。小顶堆的要求是每个节点的值都不小于其父节点的值（如下右图所示）。对于非降序排列，一般使用大根堆。
image.png
按照从左到右，从上到下，对堆中的结点按层进行编号，将这种逻辑结构映射到数组中如下图所示。
image.png
该数组从逻辑上讲就是一个堆结构，也就是一个完全二叉树，通过用简单的数学公式可以描述一下堆的定义就是
大顶堆：arr[i]>=arr[2i+1]&&arr[i]>=arr[2i+2]
小顶堆：arr[i]<=arr[2i+1]&&arr[i]<=arr[2i+2]
堆排序基本思想
- 先将初始待排序序列建成一个大顶堆，此时序列的最大值就是大顶堆的根节点。
- 将大顶堆中的根节点元素与末尾元素交换，此时最大值就排在了末尾。
- 将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值，反复执行，便可将所有元素排序。
堆排序步骤
-
假定给定无序序列结构如下
image.png
-
此时从最后一个非叶子结点开始，即arr.length/2-1处开始，从右至左，从下至上进行调整。
image.png
-
找到第二个非叶节点4 ，由于[4,9,8]中9元素最大，4和9交换。
image.png
这时，由于交换导致了子根[4,5,6]结构混乱，继续调整，[4,5,6]中6最大，交换4和6。
image.png
此时将一个无序序列构造成了一个大顶堆。
-
将堆顶元素9与末尾元素4交换
image.png
-
重新调整结构，使其满足堆定义
image.png
-
再将堆顶元素8与末尾元素5进行交换，得到第二大元素8
image.png
后续依次进行调整，交换，反复执行，最终使得整个序列有序。
下面使用java程序实现该算法
import java.util.Arrays;
import java.util.Scanner;
public class testHeapSort {
public static void main(String[] args) {
System.out.print("请输入:\n");
Scanner scan = new Scanner(System.in);
int n = scan.nextInt();
int[] arr= new int[n];
for (int i=0;i<n;i++) {
arr[i]=scan.nextInt();
}
sort(arr);
System.out.println(Arrays.toString(arr));
}
public static void sort(int[] arr) {
for(int i=arr.length/2-1;i>=0;i--) {
adjustHeap(arr,i,arr.length);
}
for(int j=arr.length-1;j>0;j--) {
swap(arr,0,j);
adjustHeap(arr,0,j);
}
}
public static void adjustHeap(int[] arr, int i, int length) {
int temp=arr[i];
for(int k=i*2+1;k<length;k=k*2+1) {
if (k+1<length&&arr[k]<arr[k+1]) {
k++;
}
if(temp<arr[k]) {
arr[i]=arr[k];
i=k;
}
else {
break;
}
}
arr[i]=temp;
}
public static void swap(int[] arr, int a ,int b ) {
int temp=arr[a];
arr[a]=arr[b];
arr[b]=temp;
}
}
时间复杂度
堆的存储表示是顺序的。因为堆所对应的二叉树为完全二叉树，而完全二叉树通常采用顺序存储方式。当想得到一个序列中第k个最小的元素之前的部分排序序列，最好采用堆排序。因为堆排序的时间复杂度是O(n+klogn),若k<=n/logn, 则可得到的时间复杂度为O(n)。
网友评论