#include <stdio.h>

// 交换数组中两个元素的位置
void swap(int arr[], int i, int j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

// 分区函数，返回基准元素的位置
int partition(int arr[], int low, int high) {
    // 选择最左边的元素作为基准
    int pivot = arr[low];
    int left = low + 1;
    int right = high;
    
    while (1) {
        // 向右移动，直到找到大于或等于基准的元素
        while (left <= right && arr[left] <= pivot) {
            left++;
        }
        
        // 向左移动，直到找到小于或等于基准的元素
        while (left <= right && arr[right] >= pivot) {
            right--;
        }
        
        // 如果左指针小于右指针，则交换
        if (left < right) {
            swap(arr, left, right);
        } else {
            break;
        }
    }
    
    // 把基准元素放到正确的位置
    swap(arr, low, right);
    return right;
}

// 快速排序主函数
void quickSort(int arr[], int low, int high) {
    if (low < high) {
        // 找到基准元素的位置
        int pivotIndex = partition(arr, low, high);
        
        // 递归排序基准元素左侧和右侧的子数组
        quickSort(arr, low, pivotIndex - 1);
        quickSort(arr, pivotIndex + 1, high);
    }
}

// 主函数，用于测试
int main() {
    int arr[] = { 6, 1, 2, 7, 9, 3, 4, 5, 10, 8 };
    int length = sizeof(arr) / sizeof(arr[0]);  // 获取数组长度
    
    printf("原始数组:\n");
    for (int i = 0; i < length; i++) {
        printf("%d ", arr[i]);
    }
    
    quickSort(arr, 0, length - 1);  // 调用快速排序
    
    printf("\n排序后的数组:\n");
    for (int i = 0; i < length; i++) {
        printf("%d ", arr[i]);
    }
    
    return 0;
}
