【算法】- 排序

【算法】- 排序 - 堆排序

文章目录

前言
一、堆排序思想
二、堆排序
总结

前言

编译语言：C++
编译器：VS2022

一、堆排序思想

堆排序的思想也就是将数列转化成大顶堆数列，通过充分利用大顶堆数列的特点，第一个数是整个数组的最大值，将这个数放大数列的最后一个位置，这样也就完成了一个位置排序，然后再次调整数列成为堆排序，然后循环这样就可以就可以完成对数列的排序

二、堆排序

#define MAXSIZE 10//数组要排序的个数
#include <iostream>
using namespace std;
//交换
void Swap(int arr[], int n, int m)
{int tmp = arr[n];arr[n] = arr[m];arr[m] = tmp;
}
//调整为大顶堆排序
void HeapAdjust(int arr[], int s, int n)
{int j;arr[0] = arr[s];//存放双亲结点的值for (j = 2 * s; j <= n; j*=2)//找到双亲的所有左孩子结点{if (j<n && arr[j] < arr[j + 1])//如果右孩子比左孩子大则j加1,且在序列内j++;if (arr[s] >= arr[j])//如果双亲比孩子结点都大则直接返回,且在序列内break;arr[s] = arr[j];//将比双亲大的孩子赋值给双亲s = j;//将j下标给s,找到要交换的孩子结点}arr[s] = arr[0];//将孩子和双亲完成交换
}
//堆排序
void HeapSort(int arr[])
{int i;for (i = MAXSIZE / 2; i > 0; i--)//找到每个有孩子的双亲(这里是层序排列完全二叉树)HeapAdjust(arr, i, MAXSIZE);//将无序的数列调整为大顶堆for (i = MAXSIZE; i > 1; i--)//从数列最后一个数开始循环{Swap(arr, 1, i);//交换每个大顶堆第一个数和最后一个数HeapAdjust(arr, 1, i-1);//再次调整为大顶堆}
}
int main()
{int i;int arr[MAXSIZE + 1] = { 0,5,2,3,7,8,6,1,9,10,4 };//创建要排序数组HeapSort(arr);//进行堆排序for (i = 1; i <= MAXSIZE; i++)cout << arr[i] << " ";return 0;
}