发布时间:2024-08-16 18:01
1,堆排序是利用堆这种数据结构而设计的一种排序算法,堆排序是一种选择排序,他的最好,最坏复杂度均为O(nlogn),他也是一种不稳定排序
2,堆是具有一下性质的完全二叉树:每个结点的值都大于或等于其左右孩子结点的值,称为大顶堆,注意:没有要求结点的做孩子的值和右孩子的值得大小关系
3,每个结点的值都小于或等于其左右孩子结点的值,叫做小顶堆
大顶堆特点:arr[i] >=arr[i2+1]&&arr[i]>=arr[2i+2]
小顶堆特点:arr[i] <=arr[i2+1]&&arr[i]<=arr[2i+2]
堆排序基本思想:
(1)将待排序序列构造成一个大顶堆
(2)此时,整个序列的最大值就是堆顶的根节点
(3)将其余末尾元素进行交换,此时末尾就为最大值
(4)然后将剩下n-1个元素重新构造成一个堆,这样会得到n个元素的次小值,如此反复便能得到有序序列了
public static void HeapSortTable(int[] arr) {
//先把这个无需的数组,按要求构造成一个大顶堆
for(int i = arr.length/2-1;i > 0;i--) {
HeapSort(arr,i,arr.length);
}
//在对大顶堆进行排序,每次去掉大顶堆的堆顶,在重新构造大顶堆,实现堆排序
for(int i = arr.length-1;i > 0;i--) {
//将大顶堆堆顶(最大)的值去除,代表已经找到该元素的位置
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
//重新构造大顶堆
HeapSort(arr,0,i);
}
}
public static void HeapSort(int[] arr,int i,int length) {
//记录该点的值是多少
int temp = arr[i];
//在去找他的左右子节点中最大的来使以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(arr[i] < arr[k]) {
arr[i] = arr[k];
i = k;//儿子去占了父亲的位置,那么就要把儿子先前的位置记录下来,等后面才可以让父亲找到它自己应该去哪
}else {//如果发现它本来就是大顶堆,那么就不用换了
break;
}
}
//如果我们把父亲的位置让给了他的子节点,那么原来子节点的位置应该让给原先的父亲来做
arr[i] = temp;
}
还有更多排序算法等你来发现