选择排序之堆排序

目录

• • 基本知识
  • 代码实现思路

基本知识

堆排序 是属于 简单选择排序

时间复杂度为：O(nlogn)
空间复杂度：O(1)
是不稳定的算法

堆排序
首先初始化建立堆
这个堆分为大根堆和小根堆
初始化堆的代码
知识点：
完全二叉树的枝节点i
其左孩子节点为2i，右孩子节点为2i+1；

代码实现思路

• 建立初始堆代码实现 :BuildMaxHelper
• 调整堆代码实现 :HeadAdjust
• 堆排序代码实现 :HeapSort
• 主函数测试代码实现：main

void BuildMaxHelper(int A[],int len){//参数为待排序列和其长度
	for(int i=len/2;i>0;i--){//根据完全二叉树的性质，从len/2之后，就是叶子节点了
		HeadAdjust(A;i;len);	//调整数组A[]，从第i个开始，长度为len
	}
}

调整代码：

void HeadAdjust(int A[],int k,int len){//将以k为根的子树调整 为大根堆
	A[0] = A[k];	//第0个数的位置，用来存以k为根的树的根节点了
	for(int i=2*k;i<=len;i*2){		//for循环开始调整，关键字key，其左孩子节点为2k，
	//i*2，是每次都看的是其孩子节点
		//条件语句判断，如果i的长度小于len，同时，其左孩子节点值小于右孩子
		if(i<len&&A[i]<A[i+1]){
			i++;	//则i指向其右子树，就是取key较大的子节点的下标
		}
		if(A[0]>=A[i]){
			break; //如果key（要比的关键字）的值比其孩子节点的值大，那么就结束for循环，
					//就不用换了,直接返回
		}else	//否则
		{
			A[k]=A[i];	//关键字k位置的值变为较大的其子节点的值，此时k就是根位置
			k=i;	//然后k位置变为其孩子节点的位置，然后继续for循环，就是为了
			  	 	//找k应该放到哪里
			  	 	//关键字key其值变为较大子节点的值，并修改key的下标，以便继续向下筛选
		}
	} 	
}

当开启二轮循环，继续找其子节点，A[0]此时存放的是第一轮的关键值，其关键值的位置已经被替换值占了，要为其找新家

若if(A[0]>=A[i])	//就是key大于其孩子节点的值
	break;
然后，A[k]=A[0];  //把A[K]放到应该的位置
else{
	//否则
	A[k]=A[i];//就是A[k]目前在第二层，然后将A[k]的值为其子节点，
	k=i; //将k的索引变为其子节点的索引
	//就是k继续向下走了
	//然后此时，k到了下一层，若不满足循环条件
	//那么就结束循环，然后A[k]=A[0],将A[0]本次要找的元素放到其应该待的位置上
}

初始化堆，
调整堆都完成
最后就是堆排序了

void HeapSort(int A[],int len){
	BuildMaxHeap(A,len); 	//初始建堆，这时的堆，也是大根堆
	for(int i=len;i>1;i--){		//n-1趟的交换和建堆过程
			//i=len，len指向最后一个元素，然后每次都把堆底元素，和第一个元素互换位置
		swap(A[i],A[1]);	//堆顶元素和堆底元素交换，A[0],用来存放key，要 *** 作的值
							//换完之后，之后的堆排序就会将其排除之外了
		HeadAdjust(A,1,i-1); //把剩余的待排元素整理成堆，每次都从第一个元素开始
	}
}

方法2

始终比较一个节点和其两个孩子进行对比
对于上图，要将43210，每个位置都要进行筛选

package sort323;

public class duiSort {
    public static void main(String[] args) {
        //10个数，high就是最后一个元素的下标=9，length=10；
//        int[] array = {0,1,2,3,4,5,6,7,8,9};
        int[] array = {7,4,8,2,5,9,0,1,3,6,5};
        swap(array,0,1);//java交换函数的书写
         heapSort(array);
        for (int i=0;i<array.length;i++){
            System.out.print(array[i]+",");
        }
    }

    public static void heapSort(int[] array){
        
        //建堆
        for(int i=(array.length-2)/2;i>=0;i--){
            sift(array,i,array.length-1);
        }
        
        //堆排序
        for(int i=0;i<array.length-1;i++){
            //将每次调整好的大根堆，堆顶元素和最后一个元素互换
            swap(array,0,array.length-1-i);
            //之后将剩余元素继续调整
           // print();这里输出每次建堆的结果
            sift(array,0, array.length-2-i);//重新建堆的时候，首先减去最后一个元素，再减去倒数第二个元素
        }

    }

    //首先是筛选调整过程
    /**
     *
     * @param array 待排序列
     * @param low
     * @param high
     * high和len的区别，high是最后一个元素的下标，下标从0开始
     * length：长度，从1开始
     * @return void
     * @author pineapple
     * @creed: Talk is cheap,show me the code
     * @date 2022/3/24 15:35
     */
//筛选代码
    public static void sift(int array[],int low,int high){
       int k = low;
       //由画树知，2k+1是其第一个孩子
       while(2*k+1<=high){              //只要下标不越界
            int biggerIndex = 2*k+1;    //保存子节点中数值元素大的下标

            if(biggerIndex<high){       //因为是小于，所以，不存在就是+1，数组下标越界，回去再看一遍视频
                if (array[biggerIndex]<array[biggerIndex+1]){
                    biggerIndex++;
                }
            }
			
            //如果k节点的值小于其较大节点的值
           if(array[k]<array[biggerIndex]){
               swap(array,k,biggerIndex);
               //将biggerIndex赋值给k，开始下一次循环，保证子树也是大根堆
               //交换好后没有结束，要一直进行循环
               k=biggerIndex; 
           }else {
               break;   //对该节点调整完毕，结束while循环
           }
       }    //while

    }//sift

    public static void swap(int array[],int a,int b){
//        array[3]=3;
        int temp;
        temp=array[a];
        array[a]= array[b];
        array[b]=temp;
    }


}

https://www.bilibili.com/video/BV1b7411N798?p=83

java中自带swap函数
Java 中的swap交换函数
https://blog.csdn.net/u014688145/article/details/53148607
算法细节系列（1）：Java swap
https://blog.csdn.net/u014688145/article/details/53148607
堆排序算法实现
https://www.bilibili.com/video/BV1bg411u7dk?p=2
堆排序是简单选择排序的一种
#####是一种树形选择排序方法
#####排序特点、排序思想：在排序过程中，将L[1…n]视为一棵【完全二叉树】的【顺序存储结构】，利用完全二叉树中双亲节点和孩子节点之间的内在关系，在当前无序区中选择关键字最大或者最小的元素。
#####堆的定义：n个关键字序列L[1…n]称为堆，当且序列满足以下条件时，
小根堆：L(i)<=L(2i)且L(i)<=(2i+1)
解释：就是元素L(i)小于他的两个子节点，即为小根堆
大根堆：L(i)>=L(2i)且L(i)>=L(2i+1)
解释：就是元素L(i)大于他的两个子节点，即为大根堆
i满足的条件（1<=i<=[n/2]下取整）
另外知识：对于一棵完全二叉树中，最后一个双亲节点i就是（n/2向下取整）这个元素。
它的两个孩子节点分别为2i和2i+1

###堆排序的关键:构造初始堆：对于初始堆的建立，是一个反复筛选的过程。

堆排序有向上调整和向下调整两个
向下调整用来：对堆进行删除 *** 作，比如删除第一个根元素，（用来进行堆排序）
向上调整用来：对堆进行插入 *** 作
对于
#####适用于顺序存储和（链式存储不做要求掌握和快排一样）

堆排序和另外几种线性排序的不同之处
树是从1开始的
数组是从0开始的
#####堆排序的时间复杂度O(nlogn)[最好最坏平均都一样]

和快排、选择排序都一样是不稳定的算法

堆的初始化： 大根堆
对所有具有双亲节点含义编号从大到小（[n/2]~1）做出如下调整：
（1）若孩子节点皆小于双亲节点，则该结点的调整结束
（2）若存在孩子结点大于双亲结点，则将最大的孩子结点与双亲结点交换，并对该孩子结点进行（1）、（2），直到出现（1）或到叶结点为止。
堆排序：不断的输出堆顶元素，并向下调整。