做信息类网站,集团网站建设调研报告,江苏建设教育网首页,wordpress手机电影目录
前言
一、向上调整算法建堆
二、向下调整算法建堆
三、堆排序 前言 堆排序是基于堆结构的一种排序思想#xff0c;因此要为一个乱序的数组进行排序的前提是数组必须要是一个堆#xff0c;所以要先对数组进行建堆操作 一、向上调整算法建堆 时间复杂度#xff1a;O…目录
前言
一、向上调整算法建堆
二、向下调整算法建堆
三、堆排序 前言 堆排序是基于堆结构的一种排序思想因此要为一个乱序的数组进行排序的前提是数组必须要是一个堆所以要先对数组进行建堆操作 一、向上调整算法建堆 时间复杂度O n*logn 由于向上调整算法建堆的时间复杂度的证明太过晦涩难懂还要涉及数学中的错位相减法所以这里就不证明了感兴趣的可以自己去了解一下 这里只需要知道向上调整算法建堆的时间复杂度为 O n*logn
//交换两个数的位置
void sweap(int* num1, int* num2)
{int tmp *num1;*num1 *num2;*num2 tmp;
}
//向上调整算法大根堆
void AdjustUp(int* arr, int pos)
{//当前调整的位置不能是堆顶if (pos 0){return;}//寻找双亲节点int parents (pos - 1) / 2;//当前位置与双亲节点进行比较//如果当前位置的数大于双亲节点就进行交换并且继续向上调整//如果当前位置的数小于双亲节点表示堆已经构建好了if (arr[parents] arr[pos]){//交换两个数位置sweap(arr[parents], arr[pos]);//继续向上调整AdjustUp(arr, parents);}
}
int main()
{//给定一个乱序数组int arr[] { 8,3,2,6,7,1,4,9,5 };//计算数组元素个数int size sizeof(arr) / sizeof(arr[0]);//向上调整算法建堆//从前往后依次调整建堆//先让节点之前的数为堆然后整体为堆for (int i 0; i size; i){AdjustUp(arr, i);}return 0;
} 二、向下调整算法建堆 时间复杂度O n 由于向下调整算法建堆的时间复杂度的证明太过晦涩难懂还要涉及数学中的错位相减法所以这里就不证明了感兴趣的可以自己去了解一下 这里只需要知道向下调整算法建堆的时间复杂度为 O n
//交换两个数的位置
void sweap(int* num1, int* num2)
{int tmp *num1;*num1 *num2;*num2 tmp;
}
//向下调整算法大根堆
void AdjustDown(int* arr, int size, int pos)
{//左孩子位置int child pos * 2 1;//向下调整算法直到左孩子位置大于数组个数if (child size){//选出左右孩子中最大的那个孩子if (child 1 size arr[child] arr[child 1]){child;}//与当前位置进行比较//如果左右孩子中最大数大于当前位置的数就进行交换并且继续向下调整//如果左右孩子中最大数小于当前位置的数表示堆已经调整好了if (arr[child] arr[pos]){//交换两个数的位置sweap(arr[pos], arr[child]);//继续向下调整AdjustDown(arr, size, child);}}
}
int main()
{//给定一个乱序数组int arr[] { 8,3,2,6,7,1,4,9,5 };//计算数组元素个数int size sizeof(arr) / sizeof(arr[0]);//向上调整算法建堆//从最后一个叶子节点父节点往前依次调整建堆//先让节点的左右子树为堆然后整体为堆int pos (size - 1) / 2;//最后一个叶子节点父节点for (int i pos; i 0; i--){AdjustDown(arr, size, i);}return 0;
} 三、堆排序 时间复杂度O n*logn 在进行建堆操作时我们可以选择向上调整算法和向下调整算法但是由于向下调整算法的时间复杂度要优于向上调整算法因此更推荐使用向下调整算法建堆 建堆的时间复杂度为O n 每次调整的堆结构的时间复杂度为O logn 因此整体时间复杂度为O n*logn 堆排序的过程大致如下 将待排序的数组构造成一个大顶堆或小顶堆根据需要。此时整个数组的最大值或最小值就是堆结构的顶端将顶端的数与末尾的数交换。此时末尾的数为最大值或最小值剩余待排序数组个数为n-1将剩余的n-1个数再构造成大顶堆或小顶堆再将顶端数与n-1位置的数交换。如此反复执行便能得到有序数组 【注意】 排升序要建大堆排降序要建小堆 整体代码实现
//交换两个数的位置
void sweap(int* num1, int* num2)
{int tmp *num1;*num1 *num2;*num2 tmp;
}//向下调整算法大根堆
void AdjustDown(int* arr, int size, int pos)
{//左孩子位置int child pos * 2 1;//向下调整算法直到左孩子位置大于数组个数if (child size){//选出左右孩子中最大的那个孩子if (child 1 size arr[child] arr[child 1]){child;}//与当前位置进行比较//如果左右孩子中最大数大于当前位置的数就进行交换并且继续向下调整//如果左右孩子中最大数小于当前位置的数表示堆已经调整好了if (arr[child] arr[pos]){//交换两个数的位置sweap(arr[pos], arr[child]);//继续向下调整AdjustDown(arr, size, child);}}
}//堆排序——升序
void HeapSort(int* arr, int size)
{//从后往前依次调整建堆//先让节点的左右子树为堆然后整体为堆int pos (size - 1) / 2;//最后一个叶子节点父节点for (int i pos; i 0; i--){//向下调整建堆AdjustDown(arr, size, i);}//堆排序//排升序要建大堆//排降序要建小堆for (int i 0; i size; i){//堆顶与最后一个有效元素交换位置sweap(arr[0], arr[size - 1 - i]);//向下调整保持堆的结构AdjustDown(arr, size - i - 1, 0);}
}int main()
{//给定一个乱序数组int arr[] { 8,3,2,6,7,1,4,9,5 };//计算数组元素个数int size sizeof(arr) / sizeof(arr[0]);//堆排序HeapSort(arr, size);//打印排序后的数据for (int i 0; i size; i){printf(%d , arr[i]);}return 0;
}
