八大排序算法——堆排序
目录
前言
一、向上调整算法建堆
二、向下调整算法建堆
三、堆排序
前言
堆排序是基于堆结构的一种排序思想，因此要为一个乱序的数组进行排序的前提是数组必须要是一个堆，所以要先对数组进行建堆操作
一、向上调整算法建堆
时间复杂度：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;
} 