C++堆排序算法实例详解
更新时间:2023-08-30前言
堆排序是一种高效的排序算法,属于选择排序的一种。它利用了二叉堆的特性来进行排序,具有较好的时间复杂度。下面将详细介绍C++中的堆排序算法,并提供一个实例。
代码实现
#includeusing namespace std; // 下沉函数 void sink(int arr[], int len, int k){ while(2*k <=len){ int j=2 * k; if(j < len && arr[j] < arr[j+1]){ j++; } if(arr[k] >=arr[j]){ break; } swap(arr[k], arr[j]); k=j; } } // 堆排序函数 void heapSort(int arr[], int len){ // 构建堆,从最后一个非叶子节点开始下沉调整 for(int k=len/2; k >=1; k--){ sink(arr, len, k); } // 排序 while(len > 1){ swap(arr[1], arr[len]); len--; sink(arr, len, 1); } } int main(){ int arr[]={0, 9, 5, 2, 8, 1, 4, 7, 6, 3}; int len=sizeof(arr)/sizeof(int) - 1; heapSort(arr, len); for(int i=1; i <=len; i++){ cout << arr[i] << " "; } cout << endl; return 0; }
代码解析
上面的代码实现了堆排序算法。
首先,需要实现一个下沉函数sink()用于调整堆。该函数中,参数arr[]表示待操作的数组,len表示数组的长度,k表示当前要进行下沉操作的元素索引。
在heapSort()函数中,我们首先利用sink()函数构建了一个最大堆。然后,我们通过不断将堆顶元素与堆末尾元素交换,并将堆大小缩小1的方式,将最大的元素逐个移动到数组末尾。最终得到的就是升序排列的数组。
总结
通过堆排序算法,我们可以对一个数组进行高效的排序。堆排序的时间复杂度为O(nlogn),其中n是数组的长度。堆排序的实现主要依赖于构建堆和下沉操作,通过不断调整堆结构,使得最大(或最小)元素位于堆顶,从而实现排序的目的。