递归快速排序法是一种基于分治策略的高效排序算法，其核心思想是通过选择一个基准元素将数组划分为两个子数组，使得左子数组元素均小于基准，右子数组元素大于基准，然后递归地对这两个子数组进行排序，最终实现整个数组的有序排列。
算法原理
1、选择基准元素（Pivot）：从待排序的数组中选择一个元素作为基准元素。基准元素的选择可以影响排序的效率，常见的选择方法有选择第一个元素、最后一个元素、中间元素或随机元素等。为了优化性能，可以采用'三数取中'法，即选择数组首、中、尾三个元素的中位数作为基准。 2、分区操作（Partition）：将数组划分为两个子数组，使得左子数组中的所有元素都小于基准元素，右子数组中的所有元素都大于基准元素。分区操作可以通过双指针技术实现，一个指针从数组的开头向右移动，另一个指针从数组的末尾向左移动，当左指针指向的元素小于等于基准元素且右指针指向的元素大于等于基准元素时，交换这两个元素的位置。当左指针和右指针相遇时，分区操作完成，基准元素被放置在正确的位置上。 3、递归排序：对分区后得到的两个子数组分别递归地调用快速排序算法，直到子数组的长度为1或0时停止递归，此时子数组已经有序。
算法实现（以C语言为例）
左右指针法
1、选出一个 pivot（基准），一般是最左边或是最右边的。 2、定义一个 begin 和一个 end（及代码中的 i、j），begin 从左向右走，end 从右向左走。（需要注意的是：若选择最左边的数据作为 pivot，则需要 end 先走；若选择最右边的数据作为 pivot，则需要 begin 先走，如果是最右边先做为基准，代码中 partition 函数返回 i，并且将基准值与 arr[i] 交换）。 3、最左边做为基准为例，在走的过程中，若 end 遇到小于 key 的数，则停下，begin 开始走，直到 begin 遇到一个大于 key 的数时，将 begin 和 right 的内容交换，end 再次开始走，如此进行下去，直到 begin 大于等于 end（此时 begin 数组已经被分为大于基准和小于基准的两部分，而 begin 处于从左往右第一个大于基准的数，end 处于从右往左第一个小于基准的数），此时将 end（即从右往左第一个小于基准的数）与基准互换。 4、此时 pivot 的左边都是小于 pivot 的数，pivot 的右边都是大于 pivot 的数 5、将 key 的左序列和右序列再次进行这种单趟排序，如此反复操作下去，直到左右序列只有一个数据，或是左右序列不存在时
#include <stdio.h> // 交换两个元素的值 void swap(int *a, int *b){ int temp = *a; *a = *b; *b = temp;} // 分区操作 int partition(int arr[], int low, int high){ int pivot = arr[low]; // 选择第一个元素作为基准元素 int i = low + 1; // 从第二个元素开始向右移动 int j = high; // 从最后一个元素开始向左移动 while(1){ // 从左向右找到第一个大于等于基准元素的元素 while(i <= j && arr[i]< pivot){ i++;} // 从右向左找到第一个小于等于基准元素的元素 while(i <= j && arr[j]> pivot){ j--;} // 如果指针相遇，分区操作完成 if(i >= j){break;} // 交换两个元素的位置 swap(&arr[i], &arr[j]); i++; j--;} // 将基准元素放置在正确的位置上 swap(&arr[low], &arr[j]);return j; // 返回基准元素的索引 } // 递归快速排序 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[]={30, 20, 50, 60, 10, 40}; int n = sizeof(arr) / sizeof(arr[0]); printf("排序前的数组：\n");for(int i =0; i < n; i++){ printf("%d ", arr[i]);} printf("\n"); quickSort(arr, 0, n - 1); printf("排序后的数组：\n");for(int i =0; i < n; i++){ printf("%d ", arr[i]);} printf("\n");return0;}
挖坑法
选出一个数据（一般是最左边或是最右边的）存放在 key 变量中，在该数据位置形成一个坑。 定义一个 left 和一个 right，left 从左向右走（当遇到大于 key 的值时停下来）。right 从右向左走（当遇到小于 key 的值时停下来）。（若在最左边挖坑，则需要 right 先走；若在最右边挖坑，则需要 left 先走）。 把 right 的那个小的数放在坑中，在把 left 那个位置的值放在 right 那个位置中。 重复操作，直到 left>right 时结束，完成一趟，把 key 放在了正确的位置。
方法一： 通过交换数组实现，较为简单
#
