选择类排序-----堆排序

淡淡的烟草味﹌ 2022-05-03 01:58 193阅读 0赞

/*堆排序：初始时把要排序的n个数的序列看作是一棵顺序存储的二叉树（一维数组存储二叉树），
    调整它们的存储序，使之成为一个堆，将堆顶元素输出，
    得到n 个元素中最大(或最小)的元素，这时堆的根节点的数最大（或者最小）。
    然后对前面(n-1)个元素重新调整使之成为堆，输出堆顶元素，得到n 个元素中次小(或次大)的元素。
    依此类推，直到只有两个节点的堆，并对它们作交换，最后得到有n个节点的有序序列*/
    //堆排序:树形选择排序，将带排序记录看成完整的二叉树，第一步：建立初堆，第二步：调整堆 
    # include<stdio.h>//时间复杂度 O(nlogn)  不稳定 
    //第二步：调整堆  
    void HeapAdjust(int a[], int s, int n){   //调整为大根堆，从大到小  
    	int rc = a[s];//rc根节点,s第一个节点，n节点数 
    	for(int j = 2*s; j <= n; j *= 2){
    		if(j<n && a[j]<a[j+1])//判断左右子数大小
    		j++;
    		if(rc >= a[j])//直到找到比第一个节点大的数 
    		break;
    		a[s] = a[j];
    		s = j;
    	} 
    	a[s] = rc;
    } 
    
    //第一步：建初堆 
    void CreatHeap(int a[], int n){ //大根堆 
    	for(int i = n/2; i > 0; i--)
    	HeapAdjust(a, i, n);
    }
    
    //整合
    void HeapSort(int a[], int n){
        CreatHeap(a, n);//第一步建堆
    	for(int i = n; i > 1; i--){ //堆顶与最后一个元素互换
    		int x = a[1];
    		a[1] = a[i];
    		a[i] = x;
    		HeapAdjust(a, 1, i-1);
    	} 
    } 
     
     
     int main(){
    	int n;
    	printf("请输入你要排序的数的个数:"); 
    	scanf("%d", &n);
    	int *a = new int[n+1];//申请一个整型变量空间,没有赋初值，并定义一个整型指针a指向该地址空间 
    	for(int i = 1; i <= n; i++)
    	scanf("%d", &a[i]);
    	HeapSort(a, n);
    	printf("排序后:"); 
    	for(int j = 1; j <= n; j++)
    	printf("%6d", a[j]);
    	delete []a;//回收数组a的空间 
    	return 0;
    }