代码仓库： 1037827920/AlgorithmZoo
快速排序
算法步骤
- 选择基准元素，从数组中选择一个元素作为基准，通常选择方式有：
- 第一个元素
- 最后一个元素
- 中间元素
- 随机选择
- 分区操作，将数组元素根据基准分为两部分，一部分小于基准，另一部分大于基准
- 递归排序，对基准左边和右边的子数组都进行快速排序，每次递归都会进行分区操作
- 终止条件：当子数组的大小为1或0时，也就是左指针索引大于等于右指针索引时，递归终止
时间复杂度
平均情况： O(N logN)
假设每次分区操作都能把数组划分成大约两半，这样递归的深度大概就是logN（以2为底，每次除以2，直到除到1，就是递归深度，如log8=3，如果每次对半分，8个元素递归深度为3），所以时间复杂度为O(logN)
每一层递归都需要对数组进行分区操作，这个通过for循环可以看出时间复杂度为O(N)
因此平均情况的时间复杂度为O(NlogN)
最坏情况： O(N^2)
每次选择的基准元素总是数据中的最大或最小元素，如果是这样，分区操作会把数组分成一个空数组和一个包含所有其余元素的数组，递归深度会达到N，每次递归减少一个元素。分区操作复杂度也为O(N)，所以最坏情况的时间复杂度为O(N^2)
稳定性
当两个相等的元素在排序后保持原来的相对顺序，说明这个排序算法是稳定的。
举个具体的例子，对数组[5, 2, 5]进行分区操作，选择第二个5作为基准，对数组进行遍历，第一个5保持不变，2会跟第一个5交换位置([2, 5, 5])，然后要把基准放到正确的位置（这时候小于基准的元素的索引是0，+1后是基准要放置的索引），所以第一个5会跟第二个5进行交换，这时候两个相等的元素已经不是原来的相对顺序了，所以快速排序不是稳定的
C++
#include <iostream>
#include <vector>
#include <cmath>
#include <concepts>using std::vector;
using std::swap;
using std::cout;
using std::endl;
using std::totally_ordered;// 快速排序的分区函数
template<totally_ordered T>
int partition(vector<T>& arr, size_t left, size_t right) {// 选择最右边的元素作为基准T pivot = arr[right];// 小于基准的元素的索引size_t i = left;// 遍历数组// 将小于基准的元素放到左边// 将大于基准的元素放到右边for (size_t j = left; j < right; ++j) {if (arr[j] < pivot) {swap(arr[i], arr[j]);++i;}}// 将基准元素放到正确的位置swap(arr[i], arr[right]);// 返回基准元素的索引return i;
}template<totally_ordered T>
void quick_sort(vector<T>& arr, size_t left, size_t right) {if (left < right) {// 分区操作size_t pivot_index = partition<T>(arr, left, right);// 对两边进行递归quick_sort(arr, left, pivot_index - 1);quick_sort(arr, pivot_index + 1, right);}
}int main() {vector<int> arr = { 10, 7, 8, 9, 1, 5 };quick_sort<int>(arr, 0, arr.size() - 1);for (const auto& num : arr) {cout << num << " ";}cout << endl;return 0;
}
C
#include <stdio.h>
#include <stdlib.h>void swap(int* a, int* b) {int tmp = *b;*b = *a;*a = tmp;
}int partition(int* arr, int left, int right) {// 确定基准元素int pivot = arr[right];// 小于基准的元素的索引int i = left;for (int j = left; j < right; ++j) {if (arr[j] < pivot) {swap(&arr[i], &arr[j]);i++;}}// 将基准元素放到正确的位置swap(&arr[i], &arr[right]);// 返回基准元素的索引return i;
}void quick_sort(int* arr, int left, int right) {if (left < right) {int pivot_index = partition(arr, left, right);quick_sort(arr, left, pivot_index - 1);quick_sort(arr, pivot_index + 1, right);}
}int main() {int* arr = (int*)malloc(6 * sizeof(int));if (arr == NULL) {fprintf(stderr, "malloc failed\n");return 1;}arr[0] = 10;arr[1] = 7;arr[2] = 8;arr[3] = 9;arr[4] = 1;arr[5] = 5;quick_sort(arr, 0, 5);for (int i = 0; i < 6; ++i) {printf("%d ", arr[i]);}printf("\n");free(arr);return 0;
}
Rust
use std::vec::Vec;// 快速排序的分区函数
fn partition<T: PartialOrd + Copy>(arr: &mut Vec<T>, left: usize, right: usize) -> usize {// 选择最右边的元素作为基准let pivot = arr[right as usize];// 小于基准的元素的索引let mut i = left;// 遍历数组// 将小于基准的元素放到左边// 将大于基准的元素放到右边for j in left..right {if arr[j] < pivot {arr.swap(i, j);i += 1;}}// 将基准元素放到正确的位置arr.swap(i, right);// 返回基准元素的索引i
}// 快排函数
fn quick_sort<T: PartialOrd + Copy>(arr: &mut Vec<T>, left: usize, right: usize) {if left < right {// 分区操作let pivot_index = partition(arr, left, right);// 对两边执行递归quick_sort(arr, left, pivot_index - 1);quick_sort(arr, pivot_index + 1, right);}
}fn main() {let mut arr = vec![10, 7, 8, 9, 1, 5];let len = arr.len();quick_sort(&mut arr, 0, len - 1);arr.iter().for_each(|x| print!("{x} "));println!();
}
Python
# 快速排序的分区函数
def partition(arr, left, right):# 选择最右边的元素作为基准pivot = arr[right]# 小于基准的元素的索引i = left# 遍历数组# 将小于基准的元素放到左边# 将大于基准的元素放到右边for j in range(left, right):if arr[j] < pivot:arr[i], arr[j] = arr[j], arr[i]i += 1# 将基准元素放到正确的位置arr[i], arr[right] = arr[right], arr[i]# 返回基准元素的索引return i# 递归函数
def quick_sort(arr, left, right):if left < right:# 分区操作pivot_index = partition(arr, left, right)# 对两边进行递归quick_sort(arr, left, pivot_index - 1)quick_sort(arr, pivot_index + 1, right)def main():arr = [10, 7, 8, 9, 1, 5]quick_sort(arr, 0, len(arr) - 1)for num in arr:print(num, end=' ')print()if __name__ == '__main__':main()
