个人主页：strive-debug
1. 堆排序（Heap Sort）
- **核心思想**：利用 **大根堆（升序）** 或 **小根堆（降序）** 进行选择排序。
- **关键步骤**：
1. **建堆**（Heapify）：从最后一个非叶子节点开始调整（`i=(n-2)/2`），使用 `AdjustDown`（下沉调整）。
2. **排序**：
- **交换**：将堆顶（最大值/最小值）与当前未排序部分的最后一个元素交换。
- **调整**：对剩余部分重新调整成堆结构。
- **时间复杂度**：
- **建堆**：`O(n)`（因为 `AdjustDown` 的时间复杂度是 `O(log n)`）。
- **排序**：`O(n log n)`（每次调整 `O(log n)`，共 `n`次）。
- **空间复杂度**：`O(1)`（原地排序）。
代码如下：
void HPAdjustDown(int* arr, int parent, int n)
{
int child = parent * 2 + 1;
while (child < n)
{//child+1是为了防止只有单个孩子的时候，就不需要比了
if (child + 1 < n && arr[child] < arr[child + 1])
{
child++;
}
if (arr[child] > arr[parent])
{
Swap(&arr[child], &arr[parent]);
parent = child;
child = parent * 2 + 1;
}
else
{
break;
}
}
}
//堆的排序
void HeapSort(int* arr, int n)
{
//创建堆（向上）
//for (int i = 0; i < n ; i++)
//{
// HPAdjustUp(arr, i);
//}
// 创建堆（向下）
for (int i = (n - 1 - 1) / 2; i >= 0; i--)
{
HPAdjustDown(arr, i, n);
}
//堆的排序
int end = n - 1;
while (end > 0)
{
Swap(&arr[0], &arr[end]);
HPAdjustDown(arr, 0, end);
end--;
}
}
---
2. TOP-K问题
- **核心思想**：
1. **建小根堆**（求前 K **最大**的元素）。
2. **遍历剩余数据**：
- **若当前数 > 堆顶**（最小值），则替换并调整。
- **最终保留的是最大的 K个数**。
- **时间复杂度**：
- `O(k)`（建小根堆）+ `O((n-k) log k)`（遍历调整）= `O(n log k)`。为了解决空间不够的问题：
代码如下：
void CreateNDate()
{
// 造数据
int n = 100000;
srand(time(0));
const char* file = "data.txt";
FILE* fin = fopen(file, "w");
if (fin == NULL)
{
perror("fopen error");
return;
}
for (int i = 0; i < n; ++i)
{
int x = (rand() + i) % 1000000;
fprintf(fin, "%d\n", x);
}
fclose(fin);
}
void topk()
{
printf("请输⼊k：>");
int k = 0;
scanf("%d", &k);
//从文件中读取
const char* file = "data.txt";
FILE* fout = fopen(file, "r");
if (fout == NULL)
{
perror("fopen error");
return;
}
int val = 0;
int* minheap = (int*)malloc(sizeof(int) * k);
if (minheap == NULL)
{
perror("malloc error");
return;
}
//读取前k个数
for (int i = 0; i < k; i++)
{
fscanf(fout, "%d", &minheap[i]);
}
// 建k个数据的⼩堆
for (int i = (k - 1 - 1) / 2; i >= 0; i--)
{
AdjustDown(minheap, i, k);
}
int x = 0;
while (fscanf(fout, "%d", &x) != EOF)
{
// 读取剩余数据，⽐堆顶的值⼤，就替换他进堆
if (x > minheap[0])
{
minheap[0] = x;
AdjustDown(minheap, 0, k);
}
}
for (int i = 0; i < k; i++)
{
printf("%d ", minheap[i]);
}
fclose(fout);
}
---
3. 快速排序
快速排序是Hoare于1962年提出的⼀种⼆叉树结构的交换排序⽅法，其基本思想为：任取待排序元素 序列中的某元素作为基准值，按照该排序码将待排序集合分割成两⼦序列，左⼦序列中所有元素均⼩ 于基准值，右⼦序列中所有元素均⼤于基准值，然后最左右⼦序列重复该过程，直到所有元素都排列 在相应位置上为⽌。
快速排序实现主框架：
//快速排序
void QuickSort(int* a, int left, int right)
{
if (left >= right) {
return;
}
//_QuickSort⽤于按照基准值将区间[left,right)中的元素进⾏划分
int meet = _QuickSort(a, left, right);
QuickSort(a, left, meet - 1);
QuickSort(a, meet + 1, right);
}hoare版本
算法思路 ：
1）创建左右指针，确定基准值
2）从右向左找出⽐基准值⼩的数据，从左向右找出⽐基准值⼤的数据，左右指针数据交换，进⼊下次循环
代码如下：
int _QuickSort(int* arr, int left, int right)
{
int keyi = left;
left++;
while (left < right)
{
//找小
while (left<=right && arr[right] > arr[keyi])
{//要确保有意义,不要被开头的结束条件所迷惑
//在符合开头条件进入之后，如果right一直--
//或者left一直++呢，同样会发生left>right的情况
//而且不会停止直到越界
right--;
}
//找大
while (left<=right && arr[left] < arr[keyi])
{
left++;
}
//同样，如果在循环内，left>right的话，把right和left互换的话就导致排序错误
if (left <= right)// 比如3 1 2 4
{
Swap(&arr[right--], &arr[left++]);//不要忘记把right和left往前或往后++ --
}
}
//最后不要忘记把keyi位置的给基本点，以为是一keyi来比较的
Swap(&arr[keyi], &arr[right]);
return right;
}
//传过来的right是n-1，不是n，要想好，是下标
void QuickSort(int* arr, int left, int right)
{
if (left >= right)
{
return;
}
int keyi = _QuickSort(arr,left,right);
//左区间[left,mid-1]
QuickSort(arr, left, keyi - 1);
//右区间[mid+1,right]
QuickSort(arr, keyi + 1, right);
}//mid就是基本点挖坑法
思路：
创建左右指针。⾸先从右向左找出⽐基准⼩的数据，找到后⽴即放⼊左边坑中，当前位置变为新的"坑"，然后从左向右找出⽐基准⼤的数据，找到后⽴即放⼊右边坑中，当前位置变为新的"坑"，结 束循环后将最开始存储的分界值放⼊当前的"坑"中，返回当前"坑"下标（即分界值下标）
代码如下：
//填坑快排
int _QuickSort(int* arr, int left, int right)
{
int hole = left;
int keyi = arr[hole];
while (left < right)
{//这里的left<right根据情况来写
while (left < right && arr[right]>=keyi)
{
right--;
}
arr[hole] = arr[right];
hole = right;
while (left < right && arr[left] <= keyi)
{
left++;
}
arr[hole] = arr[left];
hole = left;
}
arr[hole] = keyi;
return hole;
}
//传过来的right是n-1，不是n，要想好，是下标
void QuickSort(int* arr, int left, int right)
{
if (left >= right)
{
return;
}
int keyi = _QuickSort(arr,left,right);
//左区间[left,mid-1]
QuickSort(arr, left, keyi - 1);
//右区间[mid+1,right]
QuickSort(arr, keyi + 1, right);
}//mid就是基本点lomuto前后指针
创建前后指针，从左往右找⽐基准值⼩的进⾏交换，使得⼩的都排在基准值的左边。
代码如下：
int _QuickSort(int* arr, int left, int right)
{
int prev = left, cur = left + 1;
int key = left;
while (cur <= right)
{//如果prev和cur位置相同就不需要进入，直接让cur++
if (arr[cur] < arr[key] && ++prev != cur)
{
Swap(&arr[cur], &arr[prev]);
}
++cur;
}
Swap(&arr[key], &arr[prev]);
return prev;
}---
**关键优化点**：
- **避免死循环和越界检查**（快排）。
- **减少不必要的调整次数**（TOP-K问题）。
- **确保基准值正确归位**（快排）。
下期预告；
额外篇 非递归之美：归并排序与快速排序的创新实现