面试题：C语言快速排序的分区函数实现

Question

请用C语言实现快速排序中的分区（Partition）函数。假设给定一个整数数组`arr`和数组的左右边界`left`和`right`，函数需要选择一个基准元素，并将数组分为两部分，左边部分的元素小于等于基准元素，右边部分的元素大于基准元素，最后返回基准元素的最终位置。

Answer 1

#include <stdio.h>

// 交换两个整数
void swap(int* a, int* b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

// 分区函数
int Partition(int arr[], int left, int right) {
    // 选择最右边的元素作为基准元素
    int pivot = arr[right];
    int i = left - 1; // 小于等于基准元素子数组的边界

    for (int j = left; j <= right - 1; j++) {
        // 如果当前元素小于等于基准元素
        if (arr[j] <= pivot) {
            i++; // 扩大小于等于基准元素子数组的边界
            swap(&arr[i], &arr[j]);
        }
    }
    swap(&arr[i + 1], &arr[right]);
    return i + 1;
}