C语言快速排序

快速排序的基本思想是在待排序的序列中选择一个元素作为中间元素，将序列中小于等于中间元素的元素放到左边，大于中间元素的元素放到右边，然后递归地对左右两个子序列进行排序，直到序列有序。在实现过程中，我们选择序列中的第一个元素作为中间元素，通过两个指针 i 和 j 分别从左边和右边向中间扫描，找到需要交换的两个元素并交换它们的位置。直到两个指针相遇，此时中间元素已经放到了正确的位置，将中间元素左边的子序列和右边的子序列分别递归地进行快速排序。

#include   
  
// 交换数组中两个元素的位置  
void swap(int* array, int i, int j) {  
    int temp = array[i];  
    array[i] = array[j];  
    array[j] = temp;  
}  
  
// 分区函数，返回中间元素的下标  
int partition(int* array, int low, int high) {  
    int pivot = array[low]; // 选择第一个元素作为中间元素  
    int i = low, j = high + 1;  
    while (1) {  
        while (array[++i] < pivot) { // 找到左边第一个大于等于中间元素的元素  
            if (i == high) break;  
        }  
        while (array[--j] > pivot) { // 找到右边第一个小于等于中间元素的元素  
            if (j == low) break;  
        }  
        if (i >= j) break; // 两个指针相遇，结束循环  
        swap(array, i, j); // 交换左右两个元素  
    }  
    swap(array, low, j); // 将中间元素放到正确的位置  
    return j; // 返回中间元素的下标  
}  
  
// 快速排序函数  
void quicksort(int* array, int low, int high) {  
    if (low < high) {  
        int pivot = partition(array, low, high); // 分区并得到中间元素的下标  
        quicksort(array, low, pivot - 1); // 对左边部分递归排序  
        quicksort(array, pivot + 1, high); // 对右边部分递归排序  
    }  
}  
  
int main() {  
    int array[] = {5, 2, 9, 1, 5, 6};  
    int n = sizeof(array) / sizeof(array[0]);  
    quicksort(array, 0, n - 1); // 对整个数组进行快速排序  
    for (int i = 0; i < n; i++) {  
        printf("%d ", array[i]); // 输出排序后的数组  
    }  
    return 0;  
}