408算法

快速排序

void quick_sort(int *arr, int n) {
    if (n <= 1) return;
    int low = 0, high = n - 1, mid = (low + high) / 2;
    int pivot = arr[mid];
    arr[mid] = arr[low];
    while (low < high) {
        while (low < high && arr[high] >= pivot) high--;
        arr[low] = arr[high];
        while (low < high && arr[low] <= pivot) low++;
        arr[high] = arr[low];
    }
    arr[low] = pivot;
    quick_sort(arr, low);
    quick_sort(arr + low + 1, n - low - 1);
}

堆排序

void heapify(int *arr, int n, int i) {
    int largest = i; // 初始化最大值为根节点
    int left = 2 * i + 1; // 左子节点
    int right = 2 * i + 2; // 右子节点

    // 如果左子节点大于根节点
    if (left < n && arr[left] > arr[largest])
        largest = left;

    // 如果右子节点大于当前最大值
    if (right < n && arr[right] > arr[largest])
        largest = right;

    // 如果最大值不是根节点
    if (largest != i) {
        swap(&arr[i], &arr[largest]);
        // 递归调整受影响的子堆
        heapify(arr, n, largest);
    }
}

void heap_sort(int *arr, int n) {
    // 构建最大堆（从最后一个非叶子节点开始）
    for (int i = n / 2 - 1; i >= 0; i--)
        heapify(arr, n, i);

    // 一个个从堆顶取出元素
    for (int i = n - 1; i > 0; i--) {
        // 将当前根节点（最大值）移动到数组末尾
        swap(&arr[0], &arr[i]);
        // 调整剩余元素的堆
        heapify(arr, i, 0);
    }
}