经典算法 —— 快速排序（Quick Sort）
以下是六种语言实现的快速排序（Quick Sort），采用经典原地分区（Hoare 或 Lomuto 分区，这里统一使用常用的 Lomuto 分区 方案，便于理解）。
程序员十大经典算法
- 1、快速排序（Quick Sort）
- 2、归并排序（Merge Sort）
- 3、堆排序（Heap Sort）
- 4、二分查找（Binary Search）
- 5、广度优先搜索（BFS，用邻接表）
- 6、深度优先搜索（DFS，递归）
- 7、Dijkstra 最短路径（邻接矩阵简化版）
- 8、0-1 背包问题（动态规划）
- 9、活动选择（贪心，按结束时间排序）
- 10、KMP 字符串匹配
1. C 语言（带注释）
1#include <stdio.h> 2 3// 分区函数（Lomuto 分区方案） 4// 参数：数组 arr，子数组范围 low（下界） 到 high（上界） 5// 返回值：基准元素最终所在的位置索引 6int partition(int arr[], int low, int high) { 7 // 选择最右边的元素作为基准（pivot） 8 int pivot = arr[high]; 9 // i 指向小于等于基准的区域的最后一个元素 10 int i = low - 1; 11 12 // 遍历除基准外的所有元素 13 for (int j = low; j < high; j++) { 14 // 如果当前元素 <= 基准，则将其交换到左侧区域 15 if (arr[j] <= pivot) { 16 i++; // 扩大左侧区域 17 // 交换 arr[i] 和 arr[j] 18 int temp = arr[i]; 19 arr[i] = arr[j]; 20 arr[j] = temp; 21 } 22 } 23 // 最后将基准放到正确位置（i+1），此时左侧均 <= 基准，右侧均 > 基准 24 int temp = arr[i + 1]; 25 arr[i + 1] = arr[high]; 26 arr[high] = temp; 27 return i + 1; // 返回基准的索引 28} 29 30// 快速排序递归函数 31// 参数：数组 arr，当前排序子数组的起止索引 low, high 32void quickSort(int arr[], int low, int high) { 33 if (low < high) { 34 // 获取分区后基准的位置 35 int pi = partition(arr, low, high); 36 // 递归排序基准左侧部分 37 quickSort(arr, low, pi - 1); 38 // 递归排序基准右侧部分 39 quickSort(arr, pi + 1, high); 40 } 41} 42 43// 测试代码 44int main() { 45 int arr[] = {10, 7, 8, 9, 1, 5}; 46 int n = sizeof(arr) / sizeof(arr[0]); 47 48 quickSort(arr, 0, n - 1); 49 50 printf("排序后的数组: "); 51 for (int i = 0; i < n; i++) 52 printf("%d ", arr[i]); 53 printf("\n"); 54 return 0; 55}
2. C++ 语言（带注释）
1#include <iostream> 2#include <vector> 3using namespace std; 4 5// 分区函数（Lomuto 分区方案） 6// 参数：数组（引用传递），子数组下界 low，上界 high 7// 返回值：基准元素最终所在位置的索引 8int partition(vector<int>& arr, int low, int high) { 9 int pivot = arr[high]; // 选取最后一个元素作为基准 10 int i = low - 1; // i 指向小于等于基准的区域的末尾 11 12 for (int j = low; j < high; j++) { 13 // 若当前元素 <= 基准，则将其放到左侧区域 14 if (arr[j] <= pivot) { 15 i++; 16 swap(arr[i], arr[j]); // 标准库交换函数 17 } 18 } 19 // 将基准交换到正确位置 20 swap(arr[i + 1], arr[high]); 21 return i + 1; 22} 23 24// 快速排序递归函数 25void quickSort(vector<int>& arr, int low, int high) { 26 if (low < high) { 27 int pi = partition(arr, low, high); // 分区 28 quickSort(arr, low, pi - 1); // 排序左半部分 29 quickSort(arr, pi + 1, high); // 排序右半部分 30 } 31} 32 33// 测试 34int main() { 35 vector<int> arr = {10, 7, 8, 9, 1, 5}; 36 quickSort(arr, 0, arr.size() - 1); 37 38 cout << "排序后的数组: "; 39 for (int x : arr) cout << x << " "; 40 cout << endl; 41 return 0; 42}
3. Go 语言（带注释）
1package main 2 3import "fmt" 4 5// partition 函数实现 Lomuto 分区 6// 参数：切片 arr，子数组下界 low，上界 high 7// 返回：基准元素最终位置的索引 8func partition(arr []int, low, high int) int { 9 pivot := arr[high] // 选择最后一个元素作为基准 10 i := low - 1 // i 指向小于等于基准的区域末尾 11 12 for j := low; j < high; j++ { 13 // 如果当前元素 <= 基准，则将其交换到左侧 14 if arr[j] <= pivot { 15 i++ 16 arr[i], arr[j] = arr[j], arr[i] // 交换 17 } 18 } 19 // 将基准放到中间位置（i+1） 20 arr[i+1], arr[high] = arr[high], arr[i+1] 21 return i + 1 22} 23 24// quickSort 递归实现快速排序 25func quickSort(arr []int, low, high int) { 26 if low < high { 27 pi := partition(arr, low, high) // 分区，得到基准位置 28 quickSort(arr, low, pi-1) // 排序基准左侧 29 quickSort(arr, pi+1, high) // 排序基准右侧 30 } 31} 32 33func main() { 34 arr := []int{10, 7, 8, 9, 1, 5} 35 quickSort(arr, 0, len(arr)-1) 36 fmt.Println("排序后的数组:", arr) 37}
4. Rust 语言（带注释）
1/// Lomuto 分区函数 2/// 参数：可变数组切片，子数组下界 low，上界 high 3/// 返回：基准元素在分区后所处的索引 4fn partition(arr: &mut [i32], low: usize, high: usize) -> usize { 5 let pivot = arr[high]; // 选择最后一个元素作为基准 6 let mut i = low; // i 指向小于等于基准的区域的下一个位置（注意与 C 版本略有不同） 7 8 // 遍历除基准外的元素，从 low 到 high-1 9 for j in low..high { 10 if arr[j] <= pivot { 11 arr.swap(i, j); // 将 <= pivot 的元素交换到前面 12 i += 1; // 扩大左侧区域 13 } 14 } 15 // 将基准放到正确的位置（i 处） 16 arr.swap(i, high); 17 i // 返回基准索引 18} 19 20/// 快速排序递归函数 21/// 参数：可变数组切片，当前排序区间的起止索引（low, high） 22fn quick_sort(arr: &mut [i32], low: usize, high: usize) { 23 if low < high { 24 let pi = partition(arr, low, high); // 分区，获得基准位置 25 // 注意：需要检查 pi 是否大于 0，防止无符号整数下溢 26 if pi > 0 { 27 quick_sort(arr, low, pi - 1); // 排序左半部分 28 } 29 quick_sort(arr, pi + 1, high); // 排序右半部分 30 } 31} 32 33fn main() { 34 let mut arr = [10, 7, 8, 9, 1, 5]; 35 let len = arr.len(); 36 if len > 0 { 37 quick_sort(&mut arr, 0, len - 1); 38 } 39 println!("排序后的数组: {:?}", arr); 40}
5. Python 语言（带注释）
1def partition(arr, low, high): 2 """ 3 Lomuto 分区函数 4 :param arr: 待分区列表 5 :param low: 子数组下界 6 :param high: 子数组上界 7 :return: 基准元素的最终索引 8 """ 9 pivot = arr[high] # 选取最后一个元素作为基准 10 i = low - 1 # i 指向小于等于基准的区域末尾 11 12 for j in range(low, high): 13 # 如果当前元素 <= 基准，则将其交换到左侧区域 14 if arr[j] <= pivot: 15 i += 1 16 arr[i], arr[j] = arr[j], arr[i] 17 18 # 将基准放到正确位置（i+1） 19 arr[i + 1], arr[high] = arr[high], arr[i + 1] 20 return i + 1 21 22def quick_sort(arr, low, high): 23 """ 24 快速排序递归函数 25 :param arr: 待排序列表 26 :param low: 当前排序区间下界 27 :param high: 当前排序区间上界 28 """ 29 if low < high: 30 pi = partition(arr, low, high) # 分区 31 quick_sort(arr, low, pi - 1) # 递归排序左侧 32 quick_sort(arr, pi + 1, high) # 递归排序右侧 33 34# 测试代码 35if __name__ == "__main__": 36 arr = [10, 7, 8, 9, 1, 5] 37 quick_sort(arr, 0, len(arr) - 1) 38 print("排序后的数组:", arr)
6. TypeScript 语言（带注释）
1/** 2 * Lomuto 分区函数 3 * @param arr 待分区的数组（原地修改） 4 * @param low 子数组起始索引 5 * @param high 子数组结束索引 6 * @returns 基准元素的最终索引 7 */ 8function partition(arr: number[], low: number, high: number): number { 9 const pivot = arr[high]; // 选择最后一个元素作为基准 10 let i = low - 1; // i 指向小于等于基准的区域末尾 11 12 for (let j = low; j < high; j++) { 13 // 如果当前元素 <= 基准，则将其移到左侧区域 14 if (arr[j] <= pivot) { 15 i++; 16 // 交换 arr[i] 和 arr[j] 17 [arr[i], arr[j]] = [arr[j], arr[i]]; 18 } 19 } 20 // 将基准放到中间位置（i+1） 21 [arr[i + 1], arr[high]] = [arr[high], arr[i + 1]]; 22 return i + 1; 23} 24 25/** 26 * 快速排序（原地修改） 27 * @param arr 待排序数组 28 * @param low 当前子数组起始索引 29 * @param high 当前子数组结束索引 30 */ 31function quickSort(arr: number[], low: number, high: number): void { 32 if (low < high) { 33 const pi = partition(arr, low, high); // 分区，得到基准索引 34 quickSort(arr, low, pi - 1); // 排序左侧部分 35 quickSort(arr, pi + 1, high); // 排序右侧部分 36 } 37} 38 39// 测试代码 40const arr = [10, 7, 8, 9, 1, 5]; 41quickSort(arr, 0, arr.length - 1); 42console.log("排序后的数组:", arr);
以上代码均采用相同的算法逻辑（Lomuto 分区 + 递归），并添加了足够的注释以解释关键步骤和设计思路。
评论 0
加载评论中...