调整百度对网站的最大天级抓取频次值优化设计一年级下册数学答案
目录
前言
一、向上调整算法建堆
二、向下调整算法建堆
三、堆排序
前言
堆排序是基于堆结构的一种排序思想，因此要为一个乱序的数组进行排序的前提是数组必须要是一个堆，所以要先对数组进行建堆操作
一、向上调整算法建堆
时间复杂度：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;
} 