C、Rust语言中的快速排序

QuickSort 是 Tony Hoare 于 1960 年开发的用于对数组进行排序的最佳排序算法之一。它遵循分而治之规则，类似于归并排序，但又不同归并排序，该算法不使用任何额外的空间进行排序（尽管它使用了辅助堆栈空间）。

快速排序的基本思想是从数组中选择一个“枢轴”元素，然后根据其他元素是否小于或大于将其划分为两个子数组枢轴。

基于快速排序的现实示例
想象一下，你有一堆卡片，你想按照从小到大的顺序排列它们。
操作方法如下：

选择一张牌：从牌堆中随机选择任意一张牌。将此卡称为“枢轴”。
分牌堆：将剩余的牌分成两堆 - 一堆牌的牌比枢轴小，另一堆牌的牌比枢轴大。
对牌堆进行排序：现在，重复划分两堆牌的相同过程，直到每堆只剩下一张牌。
合并已排序的堆：当所有子堆排序完成后，将它们按照最小的在左边、最大的在右边的顺序放在一起。

因此，一副纸牌是通过反复划分和征服任务来排序的。

快速排序算法
该算法基本上需要实现两个函数：

partition()函数
QuickSort() 函数

1.quickSort()函数
QuickSort() 函数接受三个参数：

arr[]: 大小为 n 的整数数组。
low：指向第一个索引。
high：指向最后一个索引。

QuickSort() 的工作原理

最初，低点指向第一个索引，高点指向最后一个索引。
使用partition()函数获取索引（排序后应放置枢轴的位置），称为分区索引。
对左侧和右侧子数组递归调用函数 quickSort()，即 quickSort(arr,low,partitionIndex - 1) 和 quickSort(arr,partitioning + 1, high) 执行以下操作 while(low<high)

2. partition() 函数
partition() 函数接受三个参数：

arr[]：整数数组。
low：指向起始索引。
high：指向结束索引。

partition() 的工作原理

首先选择枢轴。
i 指针指向低点，j 指针指向高点。
指针 i 将向前移动，找到第一个大于中枢的元素。同样，指针 j 将向后移动，找到第一个小于中枢的元素。
一旦找到这样的元素，即 arr > 中枢，arr[j] < 中枢，且 i < j，我们将交换 arr 和 arr[j]。继续执行步骤 3 和步骤 4，直到 j 小于 I（J 交叉 I）。
最后，我们将把中枢元素（即 arr[low]）与 arr[j] 互换，并返回索引 j，即分区索引。

注：此处添加一些检查，如 i <= high-1 和 j >= low+1。因为可能会出现这样的情况：i 处于高位并试图继续前进，或者 j 处于低位并试图超越。

// C program to implement Quick Sort Algorithm 
include <stdio.h> 

// Function to swap two elements 
void swap(int* a, int* b) 
{ 
    int temp = *a; 
    *a = *b; 
    *b = temp; 
} 

// Partition function 
int partition(int arr[], int low, int high) 
{ 

   // 将枢轴初始化为第一个元素 ；
    int pivot = arr[low]; 
    int i = low; 
    int j = high; 

    while (i < j) { 

        // 条件 1：查找第一个元素大于 
     //枢轴（从起点开始） ；
        while (arr[i] <= pivot && i <= high - 1) { 
            i++; 
        } 

       // 条件 2：查找第一个元素小于 
      //枢轴（从最后一个开始） ；
        while (arr[j] > pivot && j >= low + 1) { 
            j--; 
        } 
        if (i < j) { 
            swap(&arr[i], &arr[j]); 
        } 
    } 
    swap(&arr[low], &arr[j]); 
    return j; 
} 

// QuickSort function 
void quickSort(int arr[], int low, int high) 
{ 
    if (low < high) { 

        // 调用分区函数查找分区索引 ；
        int partitionIndex = partition(arr, low, high); 

        // 递归调用 quickSort() 进行左右排序 
        // 根据分区索引排序一半 ；
        quickSort(arr, low, partitionIndex - 1); 
        quickSort(arr, partitionIndex + 1, high); 
    } 
} 

// driver code 
int main() 
{ 
    int arr[] = { 19, 17, 15, 12, 16, 18, 4, 11, 13 }; 
    int n = sizeof(arr) / sizeof(arr[0]); 

    // printing the original array 
    printf("Original array: "); 
    for (int i = 0; i < n; i++) { 
        printf("%d ", arr[i]); 
    } 

    // 调用 quickSort() 对给定数组进行排序 ；
    quickSort(arr, 0, n - 1); 

    // printing the sorted array 
    printf("\nSorted array: "); 
    for (int i = 0; i < n; i++) { 
        printf("%d ", arr[i]); 
    } 

    return 0; 
}

输出
OutputOriginal array:：19 17 15 12 16 18 4 11 13 
Sorted arra：4 11 12 13 15 16 17 18 19

时间复杂度：O(n*logn)，其中 n = 数组大小。空间复杂度: O(1) + O(n)（考虑辅助堆栈空间）。

快速排序算法中如何选择枢轴？
pivot 是给定数组中任何选定的元素。它作为一个点，用于将数组划分为两个子数组（右半部分和左半部分）。
用于选择枢轴的常见策略是：

第一个元素： 选择数组的第一个元素作为基准。
最后一个元素：选择数组的最后一个元素作为基准。
数组的中位数：计算数组的中位数（数组排序时的中间元素），并将其作为基准。
随机元素：从数组中随机选择任意元素作为基准。

主元的选择会影响快速排序算法的效率。
快速排序算法的优点
以下是快速排序算法的主要优点 -

与其他排序算法相比，快速排序具有最好的时间复杂度。
它使用分而治之的策略，使算法更容易理解和解决问题。
适用于大型数据集或高度结构化的数据。

快速排序算法的缺点
以下是快速排序算法的缺点 -
如果所选的主元导致数组的分区错误，则快速排序的最坏情况时间复杂度为 O(n2)。
快速排序并不稳定，因为在快速排序算法中，元素的交换是根据枢轴的位置完成的（甚至不考虑它们的原始位置）。
不适合小数据集。
实施起来很困难，因为它需要仔细选择枢轴才能获得最佳结果。
C语言快速排序常见面试问题解答
Q1.什么是快速排序？
回答：
快速排序是最好的排序算法之一。它采用 分而治之 策略，因为它选择一个主元元素并根据分区索引将给定数组划分为两个子数组，左半部分包含元素小于枢轴，右半部分具有大于枢轴的元素。
Q2。快速排序的时间复杂度是多少？
回答：

平均情况快速排序的时间复杂度为O(n log n) (n is数组中的多个元素）。
最坏的情况快速排序的时间复杂度为O(n2)当枢轴选择不当时，这种情况很少见。

Q3。快速排序是稳定排序算法还是不稳定排序算法？
回答：
不，快速排序并不稳定，因为在快速排序算法中，元素的交换是根据枢轴的位置完成的（甚至不考虑它们的原始位置）。
Q4。快速排序是否使用额外空间排序？
回答：
不，快速排序不使用额外空间，因为快速排序是一种就地排序算法。然而，它使用递归方法，可能会消耗堆栈空间。
Q5.快速排序是如何工作的？
回答：
快速排序适用于分而治之r 策略，将给定数组递归地划分为右半部分和左半部分，并使用通过重新排列数组元素来进行枢转，使得小于枢轴的元素位于左侧，大于枢轴的元素位于右侧。对每个分区不断重复此过程以获得排序后的数组。
Q6.快速排序中如何选择枢轴？
回答：
快速排序中的主元可以通过多种方式选择，例如选择第一个元素作为主元、最后一个元素、三个元素的中值或随机元素。枢轴元素的选择影响算法的效率。
C++中快速排序
下面是在C++中实现的快速排序算法示例：
include <iostream>
include <vector>

// 分区函数，返回枢轴元素的索引
int partition(std::vector<int>& arr, int low, int high) {
int pivot = arr[high]; // 选择最后一个元素作为枢轴
int i = low - 1; // 较小元素的索引

for (int j = low; j < high; ++j) {
if (arr[j] < pivot) {
// 交换 arr[i+1] 和 arr[j]
std::swap(arr[++i], arr[j]);
}
}

// 交换 arr[i+1] 和 arr[high]（将枢轴放入正确的位置）
std::swap(arr[i + 1], arr[high]);

return i + 1;
}

// 快速排序函数
void quickSort(std::vector<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() {
std::vector<int> arr = {12, 4, 5, 6, 7, 3, 1, 15};
int n = arr.size();

std::cout << "原始数组: ";
for (int num : arr) {
std::cout << num << " ";
}
std::cout << std::endl;

// 执行快速排序
quickSort(arr, 0, n - 1);

std::cout << "排序后的数组: ";
for (int num : arr) {
std::cout << num << " ";
}
std::cout << std::endl;

return 0;
}

这个程序定义了partition函数，选择一个枢轴元素并将数组分为两半，以及quickSort函数，递归地对子数组进行排序。main函数演示了通过对示例数组进行排序的用法。
Rust中快速排序
以下是在Rust中实现的快速排序算法的示例：
fn partition(arr: &mut Vec<i32>, low: usize, high: usize) -> usize {
let pivot = arr[high];
let mut i = low as i32 - 1;

for j in low..high {
if arr[j] < pivot {
i += 1;
arr.swap(i as usize, j);
}
}

arr.swap((i + 1) as usize, high);
(i + 1) as usize
}

fn quick_sort(arr: &mut Vec<i32>, low: usize, high: usize) {
if low < high {
let pivot_index = partition(arr, low, high);

if pivot_index > 0 {
quick_sort(arr, low, pivot_index - 1);
}

quick_sort(arr, pivot_index + 1, high);
}
}

fn main() {
let mut arr = vec![12, 4, 5, 6, 7, 3, 1, 15];

println!("原始数组: {:?}", arr);

let n = arr.len();
quick_sort(&mut arr, 0, n - 1);

println!("排序后的数组: {:?}", arr);
}
这个Rust程序定义了partition函数，选择一个枢轴元素并将数组分为两半，以及quick_sort函数，递归地对子数组进行排序。main函数演示了通过对示例数组进行排序的用法。
请注意，Rust中的变量默认是不可变的，因此在partition函数中需要使用&mut Vec<i32>来传递可变引用以修改数组。此外，Rust的索引是无符号整数，因此在递归调用quick_sort时，需要将pivot_index减去1，以确保在子数组中排序的正确部分。
在Rust中，标准库 std::vec::Vec 提供了 sort 方法，该方法使用快速排序算法来对向量进行排序。这是一个简单的示例：
fn main() {
let mut arr = vec![12, 4, 5, 6, 7, 3, 1, 15];

println!("原始数组: {:?}", arr);

// 使用 sort 方法进行快速排序
arr.sort();

println!("排序后的数组: {:?}", arr);
}
上述代码中的 arr.sort() 会对向量 arr 进行原地排序。如果你需要对其他类型的集合进行排序，可以使用 sort_by 方法，并提供一个比较函数。
fn main() {
let mut arr = vec![12, 4, 5, 6, 7, 3, 1, 15];

println!("原始数组: {:?}", arr);

// 使用 sort_by 方法进行自定义排序
arr.sort_by(|a, b| a.cmp(b));

println!("排序后的数组: {:?}", arr);
}
在这里，cmp 是一个比较函数，你可以根据需要使用不同的比较函数。
这些方法是使用 Rust 标准库提供的功能来实现快速排序的简单而有效的方式。如果你需要更多的控制或者想要实现自定义的排序算法，你可以使用 sort_unstable_by 方法，该方法允许你提供一个不稳定的比较函数来进行排序。