快速排序 (Quick Sort)像“分家”一样每次从数组中挑出一个“基准值”(Pivot)把比它小的数全扔到左边比它大的数全扔到右边。然后对左右两边的小队伍重复这个过程直到每个小队伍只剩一个元素整个数组就排好序了。核心代码#include stdio.h // 分区函数将数组分为两部分并返回基准值最终所在的下标 int partition(int arr[], int low, int high) { int pivot arr[low]; // 选取当前区间的第一个元素作为基准值 while (low high) { // 从右向左找第一个小于基准值的元素 while (low high arr[high] pivot) { high--; } arr[low] arr[high]; // 将找到的较小元素移到左边 // 从左向右找第一个大于基准值的元素 while (low high arr[low] pivot) { low; } arr[high] arr[low]; // 将找到的较大元素移到右边 } arr[low] pivot; // 基准值归位此时lowhigh return low; // 返回基准值所在的下标 } // 快速排序函数 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); // 递归对右半部分排序 } } // 打印数组的辅助函数 void printArray(int arr[], int n) { for (int i 0; i n; i) { printf(%d , arr[i]); } printf(\n); } int main() { int arr[] {64, 34, 25, 12, 22}; int n sizeof(arr) / sizeof(arr[0]); // 计算数组长度 printf(排序前); printArray(arr, n); quickSort(arr, 0, n - 1); // 调用快速排序 printf(排序后); printArray(arr, n); return 0; }示例演示{64, 34, 25, 12, 22}第 1 趟分区选取第一个元素 64 作为基准值目标把比 64 小的放左边比 64 大的放右边。从右向左找小于 64 的数找到 22将其移到最左边。数组变为[22, 34, 25, 12, 22]从左向右找大于 64 的数找到 64(原位置)继续向左找直到左右指针相遇。指针在 12 的位置相遇将基准值 64 填入该位置。第 1 趟结束基准值 64 归位数组被分为左右两部分。当前数组[22, 34, 25, 12, | 64] (竖线为基准值左侧均小于64右侧均大于64)第 2 趟分区对左半部分 {22, 34, 25, 12} 排序选取 22 作为基准值目标把比 22 小的放左边比 22 大的放右边。从右向左找小于 22 的数找到 12将其移到最左边。数组变为[12, 34, 25, 12]从左向右找大于 22 的数找到 34将其移到右边。数组变为[12, 34, 25, 34]左右指针在 25 的位置相遇将基准值 22 填入该位置。第 2 趟结束基准值 22 归位。当前数组[12, | 22, 34, 25, | 64]第 3 趟分区对左半部分 {12} 排序目标只有一个元素无需比较。第 3 趟结束12 归位。当前数组[12, | 22, 34, 25, | 64]第 4 趟分区对右半部分 {34, 25} 排序选取 34 作为基准值目标把比 34 小的放左边比 34 大的放右边。从右向左找小于 34 的数找到 25将其移到左边。数组变为[25, 25]左右指针相遇将基准值 34 填入该位置。第 4 趟结束34 归位。当前数组[12, | 22, 25, | 34, | 64]第 5 趟分区对 {25} 和 {34} 排序目标均只有一个元素无需比较。排序完成。最终结果[12, 22, 25, 34, 64]复杂度时间复杂度是\(O(nlogn)\)(最坏情况下退化为\(O(n^2)\)空间复杂度是\(O(logn)\)(递归调用栈的深度)
算法-快速排序
快速排序 (Quick Sort)像“分家”一样每次从数组中挑出一个“基准值”(Pivot)把比它小的数全扔到左边比它大的数全扔到右边。然后对左右两边的小队伍重复这个过程直到每个小队伍只剩一个元素整个数组就排好序了。核心代码#include stdio.h // 分区函数将数组分为两部分并返回基准值最终所在的下标 int partition(int arr[], int low, int high) { int pivot arr[low]; // 选取当前区间的第一个元素作为基准值 while (low high) { // 从右向左找第一个小于基准值的元素 while (low high arr[high] pivot) { high--; } arr[low] arr[high]; // 将找到的较小元素移到左边 // 从左向右找第一个大于基准值的元素 while (low high arr[low] pivot) { low; } arr[high] arr[low]; // 将找到的较大元素移到右边 } arr[low] pivot; // 基准值归位此时lowhigh return low; // 返回基准值所在的下标 } // 快速排序函数 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); // 递归对右半部分排序 } } // 打印数组的辅助函数 void printArray(int arr[], int n) { for (int i 0; i n; i) { printf(%d , arr[i]); } printf(\n); } int main() { int arr[] {64, 34, 25, 12, 22}; int n sizeof(arr) / sizeof(arr[0]); // 计算数组长度 printf(排序前); printArray(arr, n); quickSort(arr, 0, n - 1); // 调用快速排序 printf(排序后); printArray(arr, n); return 0; }示例演示{64, 34, 25, 12, 22}第 1 趟分区选取第一个元素 64 作为基准值目标把比 64 小的放左边比 64 大的放右边。从右向左找小于 64 的数找到 22将其移到最左边。数组变为[22, 34, 25, 12, 22]从左向右找大于 64 的数找到 64(原位置)继续向左找直到左右指针相遇。指针在 12 的位置相遇将基准值 64 填入该位置。第 1 趟结束基准值 64 归位数组被分为左右两部分。当前数组[22, 34, 25, 12, | 64] (竖线为基准值左侧均小于64右侧均大于64)第 2 趟分区对左半部分 {22, 34, 25, 12} 排序选取 22 作为基准值目标把比 22 小的放左边比 22 大的放右边。从右向左找小于 22 的数找到 12将其移到最左边。数组变为[12, 34, 25, 12]从左向右找大于 22 的数找到 34将其移到右边。数组变为[12, 34, 25, 34]左右指针在 25 的位置相遇将基准值 22 填入该位置。第 2 趟结束基准值 22 归位。当前数组[12, | 22, 34, 25, | 64]第 3 趟分区对左半部分 {12} 排序目标只有一个元素无需比较。第 3 趟结束12 归位。当前数组[12, | 22, 34, 25, | 64]第 4 趟分区对右半部分 {34, 25} 排序选取 34 作为基准值目标把比 34 小的放左边比 34 大的放右边。从右向左找小于 34 的数找到 25将其移到左边。数组变为[25, 25]左右指针相遇将基准值 34 填入该位置。第 4 趟结束34 归位。当前数组[12, | 22, 25, | 34, | 64]第 5 趟分区对 {25} 和 {34} 排序目标均只有一个元素无需比较。排序完成。最终结果[12, 22, 25, 34, 64]复杂度时间复杂度是\(O(nlogn)\)(最坏情况下退化为\(O(n^2)\)空间复杂度是\(O(logn)\)(递归调用栈的深度)
