堆排序算法浅解

分手后的思念是犯贱 2022-01-27 05:45 139阅读 0赞

## 堆排序算法浅解 ##

1.堆排序即利用堆的思想对堆进行重复的调整,把堆顶的元素放到最后一个节点处,然后调整堆,依次循环直到排序完成

#include <iostream>
    using namespace std;
    
    
    void Swap(int* arr,int a, int b) { 
    	int temp = arr[a];
    	arr[a] = arr[b];
    	arr[b] = temp;
    }
    void AdJust(int* arr, int parent, int len) { 
    	//孩子的标号等于父亲标号的二倍加一
    	int child = 2 * parent + 1;
    	while (child<len) { 
    		//左孩子和右孩子进行比较
    		if (child + 1 < len&&arr[child + 1] > arr[child]) { 
    			//如果右孩子大,则孩子标号到右孩子身上
    			child = child + 1;
    		}
    		//如果孩子比父亲大
    		if (arr[child] > arr[parent]) { 
    			//交换父子身份
    			Swap(arr,child,parent);
    			//因为交换身份打乱后面的排序,需要对后面重新排序,
    			parent = child;
    			child = parent * 2 + 1;
    		}
    		else { 
    			return;
    		}
    		
    	}
    
    }
    void Print(int arr[],int  len) { 
    	for (int i = 0; i < len; ++i) { 
    		cout << arr[i] << " ";
    	}
    	cout << endl;
    }
    void HeapSort(int* arr, int len) { 
    	//堆的最后一个非叶子结点算法
    	//因为len是元素个数并非,编号,所以需要多减一个1
    	int root = ((len-1-1)>>1);
    	//从最后一个非叶子结点向前一直排序
    	//把堆排成一个大堆
    	for (root; root >= 0; --root) { 
    		AdJust(arr, root, len);
    	}
    	//成为大堆以后需要进行排序,把堆顶元素和最后一个结点进行交换,然后重复调整堆的位置
    	//
    	for (int i = len - 1; i > 0; --i) { 
    		Swap(arr, i, 0);
    		AdJust(arr, 0, i);
    	}
    	return;
    }
    
    int main() { 
    
    	int array[] = {  4,2,8,5,0,9,3,1 };
    	int len = sizeof(array) / sizeof(array[0]);
    	Print(array, len);
    	HeapSort(array, len);
    	Print(array, len);
    	cout<<"hello....."<<endl;
    	system("pause");
    	return 0;
    }