数据结构-快速排序算法【C语言版】_数据结构快速排序c语言

快速排序（Quick Sort）是一种高效的排序算法，由东尼·霍尔（Tony Hoare）在1960年提出。它采用分治法（Divide and Conquer）的策略来把一个序列分为较小的两个子序列，然后递归地排序两个子序列。

快速排序的原理

快速排序的基本思想是：

1. 从数列中挑出一个元素，作为"基准"（pivot）。
2. 重新排列数组，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。
3. 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。

快速排序的过程

1. 从数列中选择一个元素作为基准。
2. 将数列分为两部分：一部分是比基准值小的元素，另一部分是比基准值大的元素。
3. 对这两部分分别进行快速排序。
4. 合并排序好的两部分。

快速排序的性能

• 时间复杂度：平均和最坏情况下，快速排序的时间复杂度是O(n log n)，其中n是数列的长度。最好情况下，即每次分割都恰好将数列分为两半，时间复杂度为O(n)。
• 空间复杂度：快速排序是原地排序算法，除了递归调用的栈空间之外，不需要额外的存储空间，因此空间复杂度是O(log n)。
• 稳定性：快速排序是不稳定的排序算法，相同值的元素在排序过程中可能会改变它们的相对顺序。

快速排序的示例代码

下面是一个快速排序的C语言实现示例：

#include <stdio.h>
 
int partition(int arr[], int low, int high) {
    int pivot = arr[high]; // 选择最后一个元素作为基准
    int i = (low - 1); // 指向比基准小的元素的最后一个位置
 
    for (int j = low; j <= high - 1; j++) {
        if (arr[j] < pivot) {
            i++; // 找到比基准小的元素，指向它的下一个位置
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }
    int temp = arr[i + 1];
    arr[i + 1] = arr[high];
    arr[high] = temp;
    return (i + 1);
}
 
void quickSort(int arr[], int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high); // pi是基准元素的正确位置
        quickSort(arr, low, pi - 1); // 递归地对基准左边的子数组进行快速排序
        quickSort(arr, pi + 1, high); // 递归地对基准右边的子数组进行快速排序
    }
}
 
void printArray(int arr[], int size) {
    int i;
    for (i = 0; i < size; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}
 
int main() {
    int arr[] = {64, 34, 25, 12, 22, 11, 90};
    int n = sizeof(arr) / sizeof(arr[0]);
    quickSort(arr, 0, n - 1);
    printf("Sorted array: \n");
    printArray(arr, n);
    return 0;
}

这段代码首先定义了一个partition函数，它接受一个整数数组、数组的起始索引和结束索引作为参数，并使用一个变量pivot来选择基准。然后，它将数组分为两部分，并返回基准元素的正确位置。quickSort函数递归地对数组进行排序。printArray函数用于打印排序后的数组。

快速排序的实现细节

快速排序的实现细节包括基准的选择、分区的算法以及递归的实现。

1. 基准的选择：基准的选择对于快速排序的性能有重要影响。常用的基准选择方法包括：

   • 随机选择：从数列中随机选择一个元素作为基准。
   • 选择第一个元素或最后一个元素作为基准。
   • 选择中间的元素作为基准。
   • 三数取中：从数列中随机选择三个元素，然后选择中间的元素作为基准。

2. 分区的算法：分区算法是快速排序的核心。分区算法将数列分为两个子序列，一个包含比基准小的元素，另一个包含比基准大的元素。分区算法的基本思想是：

   • 从数列中选择一个元素作为基准。
   • 初始化两个指针，一个指向数列的开始，另一个指向数列的结束。
   • 遍历数列，将比基准小的元素移动到指针的左侧，比基准大的元素移动到指针的右侧。
   • 返回基准元素的正确位置。

3. 递归的实现：递归是快速排序的核心，它允许算法将数列分为两个子序列，然后分别对子序列进行排序。递归的基本思想是：

   • 选择一个基准。
   • 将数列分为两个子序列。
   • 对子序列进行递归排序。
   • 合并排序好的子序列。

快速排序的优缺点

• 优点：快速排序是一种高效的排序算法，平均和最坏情况下的时间复杂度为O(n log n)。
• 缺点：快速排序的空间复杂度为O(log n)，因为它需要递归调用。此外，快速排序是不稳定的排序算法，相同值的元素在排序过程中可能会改变它们的相对顺序。

快速排序的应用

快速排序在实际应用中非常广泛，例如在操作系统、数据库、网络通信等领域。它通常用于处理大规模的数据，并且可以在各种编程语言中实现。

总结

快速排序是一种高效的排序算法，它通过分治法将数组分为两个子序列，然后递归地对子序列进行排序。尽管快速排序的实现细节可能较为复杂，但它是一个非常有用的排序算法，可以在各种编程语言中实现。通过了解快速排序的原理和实现细节，您可以更好地理解和应用它。