c语言快速排序

快速排序（Quicksort）是一种高效的排序算法，采用分治法（Divide and Conquer）策略来把一个序列分为较小和较大的两个子序列，然后递归地排序两个子序列。

快速排序的步骤：

1. 选择基准（Pivot）：从数列中挑出一个元素，称为 "基准"（pivot）。

2. 分区（Partitioning）：重新排序数列，所有元素比基准值小的摆放在基准的前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任何一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个操作称为分区（partition）操作。

3. 递归排序子序列：递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。

 思路：在快排函数传参时传入数组、第一个元素下标和最后一个元素下标，以第一个元素为基准，将数组分为比基准大和比基准小的两个子序列，再对两个子序列进行递归快排，实现排序。

#include <stdio.h>
void quickSort(int *p,int l,int r)
{
    if(l>=r)    //当两个下标相遇或者l大于r的时候，说明已经找完了
        return;
    int temp = p[l];   //先保存基准的值
    int i = l, j=r;    //用两个数来作为遍历的左右下标
    while(i != j)
    {
        while(temp<=p[j] && i<j)   //i<j防止越界
            j--;
        while(temp>=p[i] && i<j)
            i++;
        if(i<j)
        {
            int t = p[i];
            p[i] = p[j];
            p[j] = t;
        }
    }
    p[l] = p[i];    //将基准与arr[i]交换
    p[i] = temp;
    quickSort(p,l,i-1);  //递归对子序列进行快排
    quickSort(p,i+1,r);
}
int main(int argc, char *argv[])
{
    int arr[] = {64, 40, 12, 22, 11, 35};
    quickSort(arr,0,5);
    printf("Sorted array: \n");
    for (int i=0; i < 6; i++)
        printf("%d ", arr[i]);
    puts("");
    return 0;
}

解析：在快排函数中需要传入数组和首尾元素下标，在函数内首先保存了基准的值，之后用一个循环在里面交换元素，直到i=j时就结束循环，在内部使用两个循环分别去寻找比基准小和比基准大的数的下标，得到之后进行位置交换；在循环结束之后，i下标对应的元素左边就是比基准小的（包括i下标对应的元素），右边就是比基准大的，这时再把基准与i下标对应的元素进行交换，此时就得到了两个子序列，递归调用快排函数，将数组和子序列的首尾元素下标当做参数传入函数，这样就能实现快速排序，快排函数结束的条件就是当子序列只有一个元素就结束。