快速排序模板(C语言)

快排的基本思想是,通过一趟排序将要排序的数据分割成独立的两部分,其中的一部分数据比另一部分的数据都要小,或者都要大,然后再把这两个独立的部分进行快速排序,整个过程可以用递归来进行。

#include<stdio.h>
void quicksort(int a[], int low, int high) // 从小到大
{
    int l ,r, key;
    l = low;
    r = high;
    key = a[l];
    if(low > high)  return ;
    while(l < r) //
    {
        while(l < r && a[r] > key) // 从右往左找到比key小的元素
            r--;
        a[l] = a[r]; // 交换之后,  r之后的元素都比key大
        while(l < r && a[l] < key)// 从左往右找到比key大的元素
            l++;
        a[r] = a[l];//交换之后,   l之前的元素都比key小
        //之后再将l到r之间的元素进行排序
    }
    a[l] =  key;
    // 此时0到l-1的元素都比l+1到high的元素小
    //但是0到l-1的元素和l+1到high的元素都是无序的
    quicksort(a, low, l-1); // 将0到l-1的元素进行快速排序
    quicksort(a, l+1, high); //将l+1到high的元素进行快速排序

}
int main()
{
    int a[100];
    int n;
    scanf("%d", &n);
    for(int i = 0; i < n; i++)
        scanf("%d", &a[i]);
    quicksort(a, 0, n-1);
    for(int i = 0; i < n; i++)
        printf("%d ", a[i]);
    printf("\n");
    return 0;
}