C语言实现快速排序算法

简介

快速排序（Quick Sort）是由东尼·霍尔所发展的一种排序算法，在平均状况下，排序 n 个项目要 O(n log n) 次比较。在最坏状况下则需要 O(n^2) 次比较，但这种状况并不常见。快速排序采用了分治法（Divide and Conquer）的思想，将一个数组分成两个子数组，然后递归地对这两个子数组进行排序，最终将整个数组排序。本文将详细介绍如何使用C语言实现快速排序算法，包括基础概念、使用方法、常见实践以及最佳实践。

基础概念

分治法

分治法是一种算法设计策略，它将一个问题分解为若干个规模较小的子问题，分别解决这些子问题，然后将子问题的解合并起来得到原问题的解。在快速排序中，分治法的应用体现在以下三个步骤：

分解（Divide）：选择一个基准元素（pivot），将数组分为两部分，使得左边部分的元素都小于等于基准元素，右边部分的元素都大于等于基准元素。
解决（Conquer）：递归地对左右两个子数组进行快速排序。
合并（Combine）：由于子数组在递归排序后已经有序，所以不需要额外的合并操作。

快速排序的基本步骤

选择基准元素：从数组中选择一个元素作为基准元素。常见的选择方法有选择第一个元素、最后一个元素或者中间元素作为基准元素。
分区操作：通过比较和交换元素，将数组分为两部分，使得左边部分的元素都小于等于基准元素，右边部分的元素都大于等于基准元素。
递归排序：对左右两个子数组分别递归地进行快速排序，直到子数组的大小为1或者0，此时数组已经有序。

使用方法

代码实现

#include <stdio.h>

// 交换两个整数的值
void swap(int* a, int* b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

// 分区函数，返回基准元素的最终位置
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++;  // 增加较小元素的索引
            swap(&arr[i], &arr[j]);
        }
    }
    swap(&arr[i + 1], &arr[high]);
    return (i + 1);
}

// 快速排序函数
void quickSort(int arr[], int low, int high) {
    if (low < high) {
        // pi 是基准元素的最终位置
        int pi = partition(arr, low, high);

        // 递归地对基准元素左边和右边的子数组进行排序
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

// 打印数组
void printArray(int arr[], int size) {
    for (int i = 0; i < size; i++)
        printf("%d ", arr[i]);
    printf("\n");
}

int main() {
    int arr[] = {10, 7, 8, 9, 1, 5};
    int size = sizeof(arr) / sizeof(arr[0]);

    printf("Original array: ");
    printArray(arr, size);

    quickSort(arr, 0, size - 1);

    printf("Sorted array: ");
    printArray(arr, size);

    return 0;
}

代码解析

swap函数：用于交换两个整数的值。
partition函数：实现了分区操作，选择最后一个元素作为基准元素，通过遍历数组将元素分为两部分，返回基准元素的最终位置。
quickSort函数：递归地对数组进行快速排序，调用 partition 函数将数组分为两部分，然后分别对左右两部分进行递归排序。
printArray函数：用于打印数组元素。
main函数：定义了一个测试数组，调用 quickSort 函数对数组进行排序，并打印排序前后的数组。

常见实践

随机化快速排序

为了避免在最坏情况下快速排序的性能退化，我们可以采用随机化的方法选择基准元素。随机化快速排序的基本思想是在每次分区操作前，随机选择一个元素作为基准元素，这样可以使快速排序在平均情况下的性能更加稳定。

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

// 交换两个整数的值
void swap(int* a, int* b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

// 随机选择基准元素并进行分区
int randomPartition(int arr[], int low, int high) {
    int pivotIndex = low + rand() % (high - low + 1);
    swap(&arr[pivotIndex], &arr[high]);
    return partition(arr, low, high);
}

// 分区函数，返回基准元素的最终位置
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++;  // 增加较小元素的索引
            swap(&arr[i], &arr[j]);
        }
    }
    swap(&arr[i + 1], &arr[high]);
    return (i + 1);
}

// 快速排序函数
void quickSort(int arr[], int low, int high) {
    if (low < high) {
        // pi 是基准元素的最终位置
        int pi = randomPartition(arr, low, high);

        // 递归地对基准元素左边和右边的子数组进行排序
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

// 打印数组
void printArray(int arr[], int size) {
    for (int i = 0; i < size; i++)
        printf("%d ", arr[i]);
    printf("\n");
}

int main() {
    srand(time(0));  // 初始化随机数种子
    int arr[] = {10, 7, 8, 9, 1, 5};
    int size = sizeof(arr) / sizeof(arr[0]);

    printf("Original array: ");
    printArray(arr, size);

    quickSort(arr, 0, size - 1);

    printf("Sorted array: ");
    printArray(arr, size);

    return 0;
}

优化快速排序

三数取中：选择第一个、中间和最后一个元素中的中间值作为基准元素，这样可以减少最坏情况的发生。
小数组优化：当子数组的大小较小时，快速排序的递归调用开销较大，可以使用插入排序等简单排序算法对小数组进行排序。

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

// 交换两个整数的值
void swap(int* a, int* b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

// 插入排序
void insertionSort(int arr[], int low, int high) {
    for (int i = low + 1; i <= high; i++) {
        int key = arr[i];
        int j = i - 1;

        while (j >= low && arr[j] > key) {
            arr[j + 1] = arr[j];
            j = j - 1;
        }
        arr[j + 1] = key;
    }
}

// 三数取中选择基准元素并进行分区
int medianOfThreePartition(int arr[], int low, int high) {
    int mid = low + (high - low) / 2;

    if ((arr[low] <= arr[mid] && arr[mid] <= arr[high]) || (arr[high] <= arr[mid] && arr[mid] <= arr[low]))
        swap(&arr[mid], &arr[high]);
    else if ((arr[mid] <= arr[low] && arr[low] <= arr[high]) || (arr[high] <= arr[low] && arr[low] <= arr[mid]))
        swap(&arr[low], &arr[high]);

    return partition(arr, low, high);
}

// 分区函数，返回基准元素的最终位置
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++;  // 增加较小元素的索引
            swap(&arr[i], &arr[j]);
        }
    }
    swap(&arr[i + 1], &arr[high]);
    return (i + 1);
}

// 快速排序函数
void quickSort(int arr[], int low, int high) {
    if (low < high) {
        if (high - low + 1 <= 16) {
            insertionSort(arr, low, high);
        } else {
            // pi 是基准元素的最终位置
            int pi = medianOfThreePartition(arr, low, high);

            // 递归地对基准元素左边和右边的子数组进行排序
            quickSort(arr, low, pi - 1);
            quickSort(arr, pi + 1, high);
        }
    }
}

// 打印数组
void printArray(int arr[], int size) {
    for (int i = 0; i < size; i++)
        printf("%d ", arr[i]);
    printf("\n");
}

int main() {
    int arr[] = {10, 7, 8, 9, 1, 5};
    int size = sizeof(arr) / sizeof(arr[0]);

    printf("Original array: ");
    printArray(arr, size);

    quickSort(arr, 0, size - 1);

    printf("Sorted array: ");
    printArray(arr, size);

    return 0;
}

最佳实践

选择合适的基准元素

选择合适的基准元素是快速排序性能的关键。随机化选择基准元素或者三数取中选择基准元素可以有效避免最坏情况的发生，提高快速排序的平均性能。

处理小数组

当子数组的大小较小时，快速排序的递归调用开销较大，此时使用插入排序等简单排序算法对小数组进行排序可以提高整体性能。

小结

本文详细介绍了C语言实现快速排序算法的基础概念、使用方法、常见实践以及最佳实践。快速排序是一种高效的排序算法，采用分治法的思想将数组分为两部分并递归排序。通过随机化选择基准元素、三数取中选择基准元素以及处理小数组等优化方法，可以进一步提高快速排序的性能。希望本文能够帮助读者深入理解并高效使用C语言实现快速排序算法。

参考资料

《算法导论》（Introduction to Algorithms）
《C Primer Plus》
维基百科 - 快速排序

更多学习资料

C语言实现AC自动机算法

AC自动机（Aho-Corasick自动机）是一种多模式串匹配算法，由Alfred V. Aho和Margaret J. Corasick在1975年提出。它在文本处理、信息检索、生物信息学等领域有着广泛的应用。AC自动机通过构建一个高效的有限状态自动机，能够在一次扫描中同时匹配多个模式串，大大提高了匹配效率。

深入理解 C 语言中的数组

在 C 语言中，数组是一种重要的数据结构，它允许我们在内存中连续存储多个相同类型的元素。通过使用数组，我们可以方便地处理一系列相关的数据，无论是简单的数字列表，还是复杂的矩阵。本文将深入探讨 C 语言中数组的基础概念、使用方法、常见实践以及最佳实践，帮助读者更好地掌握这一强大的工具。

C语言实现B+树算法：从基础到实践

B+树是一种自平衡二叉查找树的变种，它在数据库索引和文件系统中有着广泛的应用。相较于其他树结构，B+树具有独特的性质，使得它在数据存储和检索方面表现出色。本文将深入探讨如何使用C语言实现B+树算法，帮助读者理解其基础概念、掌握使用方法，并分享一些常见实践和最佳实践。

C语言实现B树算法：从基础到实践

B树是一种自平衡多路查找树，在文件系统和数据库索引等领域有着广泛的应用。它能够有效地组织数据，提供高效的查找、插入和删除操作。本文将深入探讨如何使用C语言实现B树算法，涵盖基础概念、使用方法、常见实践以及最佳实践，帮助读者全面掌握这一重要的数据结构。

C语言实现平衡二叉树

平衡二叉树（AVL树）是一种自平衡二叉查找树，由苏联数学家阿德尔森-维尔斯基（Adelson-Velsky）和兰迪斯（Landis）在1962年提出。在AVL树中，每个节点的左子树和右子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。这种平衡特性确保了二叉查找树的高度保持在对数级别，从而使查找、插入和删除操作的时间复杂度都维持在 (O(log n))，极大地提高了数据处理的效率，在许多算法和数据处理场景中都有广泛应用。

C语言实现二叉搜索树：从基础到实践

二叉搜索树（Binary Search Tree，BST）是一种非常重要的数据结构，在许多算法和应用中都有广泛的使用。它结合了树结构的层次性和搜索算法的高效性，使得数据的插入、查找和删除操作平均时间复杂度为 O(log n)，其中 n 是树中节点的数量。在这篇博客中，我们将深入探讨如何使用C语言实现二叉搜索树，包括基础概念、使用方法、常见实践以及最佳实践。

C语言实现二分查找算法：从基础到最佳实践

二分查找（Binary Search）是一种在有序数组中查找特定元素的高效算法。相比于线性查找需要逐个比较数组元素，二分查找每次可以将搜索区间缩小一半，大大提高了查找效率。在C语言中，实现二分查找算法不仅有助于理解算法设计思想，还能在实际编程中优化数据检索过程。本文将详细介绍C语言实现二分查找算法的基础概念、使用方法、常见实践以及最佳实践。

C语言实现二叉树：从基础到实践

二叉树是一种树形数据结构，每个节点最多有两个子节点。在C语言中，实现二叉树可以帮助我们解决许多算法问题，如搜索、排序和数据组织等。本文将深入探讨如何用C语言实现二叉树，并介绍其使用方法、常见实践以及最佳实践。

C语言实现BM字符串匹配算法：从基础到实践

在字符串处理领域，字符串匹配算法是一项核心技术。BM（Boyer-Moore）字符串匹配算法作为一种高效的字符串搜索算法，它的独特之处在于它从右向左进行字符比较，通过利用坏字符规则和好后缀规则，能够跳过大量不必要的比较，从而大大提高匹配效率。本文将详细介绍如何使用C语言实现BM字符串匹配算法，帮助读者深入理解并应用这一强大的算法。

C语言实现冒泡排序算法

冒泡排序（Bubble Sort）是一种简单的排序算法。它重复地走访要排序的数列，一次比较两个数据元素，如果顺序错误就把它们交换过来。走访数列的工作是重复地进行直到整个数列都被排序，这个算法的名字由来是因为越小（或越大）的元素会经由交换慢慢“浮”到数列的顶端。在本文中，我们将深入探讨如何使用C语言实现冒泡排序算法，包括基础概念、使用方法、常见实践以及最佳实践。

C语言实现桶排序算法：从基础到最佳实践

排序算法在计算机科学中扮演着至关重要的角色，它能够将无序的数据集合转换为有序的序列，以便于后续的查找、分析等操作。桶排序（Bucket Sort）作为一种高效的排序算法，特别适用于数据分布较为均匀的情况。本文将深入探讨如何使用C语言实现桶排序算法，涵盖基础概念、使用方法、常见实践以及最佳实践，帮助读者全面掌握这一算法。

C语言实现计数排序算法：从基础到最佳实践

排序算法在计算机科学中占据着重要地位，它们被广泛应用于数据处理、搜索算法等众多领域。计数排序（Counting Sort）作为一种非比较排序算法，具有独特的优势和应用场景。本文将深入探讨如何使用C语言实现计数排序算法，涵盖基础概念、使用方法、常见实践以及最佳实践，帮助读者全面掌握这一强大的排序技术。

C语言实现双端队列：深入探索与实践

在计算机科学中，双端队列（Deque，Double - ended Queue的缩写）是一种特殊的数据结构，它允许在队列的两端进行插入和删除操作。与普通队列（只能在一端插入，另一端删除）和栈（只能在一端进行插入和删除）不同，双端队列提供了更大的灵活性。在C语言中，实现双端队列可以通过数组或链表来完成。本文将详细介绍如何使用C语言实现双端队列，包括基础概念、使用方法、常见实践以及最佳实践。

C语言实现并查集：原理、实践与优化

并查集（Union-Find Set）是一种非常实用的数据结构，用于处理不相交集合的合并与查询问题。在许多算法和实际应用中，比如图的连通性判断、最小生成树算法等，都能看到并查集的身影。本文将深入探讨如何使用C语言实现并查集，从基础概念开始，逐步介绍其使用方法、常见实践以及最佳实践。

C语言实现双向链表：从基础到最佳实践

双向链表是一种重要的数据结构，它允许在两个方向上遍历列表。与单向链表相比，双向链表在某些操作上具有更高的效率，例如删除和反向遍历。在C语言中实现双向链表，不仅能加深对数据结构的理解，还能提升编程能力。本文将详细介绍C语言实现双向链表的基础概念、使用方法、常见实践以及最佳实践。

C语言实现树状数组：原理、使用与实践

树状数组（Fenwick Tree）是一种高效的数据结构，用于处理数组区间和查询以及单点更新的问题。相较于普通数组直接遍历求和的O(n)时间复杂度，树状数组在区间求和时能达到O(log n)的时间复杂度，单点更新操作同样为O(log n)。这使得树状数组在处理大量数据时具有显著的性能优势。本文将详细介绍C语言实现树状数组的基础概念、使用方法、常见实践以及最佳实践。

C语言实现斐波那契查找算法

斐波那契查找（Fibonacci Search）是一种用于在有序数组中查找特定元素的搜索算法。它利用斐波那契数列的特性来进行查找，在某些情况下，其性能优于传统的二分查找算法。与二分查找每次将搜索区间分成两部分不同，斐波那契查找根据斐波那契数列的比例来划分搜索区间，从而减少比较次数。

C语言实现图的广度优先搜索

图是一种复杂的数据结构，在计算机科学和许多其他领域都有广泛应用。广度优先搜索（Breadth-First Search，BFS）是一种用于遍历或搜索图的算法。它从给定的起始顶点开始，逐层地探索图中的顶点，直到找到目标顶点或遍历完整个图。在 C 语言中实现图的广度优先搜索，需要我们结合图的存储结构和 BFS 算法的逻辑，本文将详细介绍相关内容。

C语言实现图的深度优先搜索

在计算机科学中，图是一种用于表示对象之间关系的数据结构。深度优先搜索（Depth-First Search，DFS）是一种用于遍历或搜索图或树的算法。在C语言中实现图的深度优先搜索，可以帮助我们解决许多实际问题，如路径查找、连通性检测等。本文将详细介绍C语言实现图的深度优先搜索的相关知识，包括基础概念、使用方法、常见实践以及最佳实践。

C语言实现图：从基础到实践

在计算机科学中，图是一种用于表示对象之间关系的数据结构。图由节点（vertices）和边（edges）组成，这种结构能够模拟许多现实世界的问题，如社交网络、交通网络、任务调度等。C语言作为一门强大且高效的编程语言，提供了丰富的机制来实现图数据结构。本文将深入探讨如何使用C语言实现图，涵盖基础概念、使用方法、常见实践以及最佳实践，帮助读者掌握这一重要的数据结构及其应用。

C语言实现哈希查找算法

哈希查找算法是一种高效的数据查找方法，通过将数据的键值映射到一个哈希表中，利用哈希函数将键值转换为哈希表的索引，从而快速定位到所需的数据。在C语言中，实现哈希查找算法可以显著提高数据查找的效率，特别是在处理大规模数据时。本文将详细介绍C语言中哈希查找算法的基础概念、使用方法、常见实践以及最佳实践。

C语言实现哈希表：从基础到最佳实践

哈希表（Hash Table），也称为散列表，是一种用于数据存储和检索的数据结构。它通过哈希函数将键值对映射到一个特定的位置，从而实现快速的数据查找和插入操作。在C语言中，实现哈希表可以帮助我们优化程序性能，特别是在处理大量数据时。本文将深入探讨C语言中哈希表的基础概念、使用方法、常见实践以及最佳实践，帮助读者更好地理解和应用这一强大的数据结构。

C语言实现堆排序算法：从基础到最佳实践

堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。它是一种高效的排序算法，在许多实际应用场景中被广泛使用。在本文中，我们将深入探讨如何使用C语言实现堆排序算法，包括基础概念、使用方法、常见实践以及最佳实践。通过详细的代码示例和解释，希望能帮助读者更好地理解和应用这一算法。

C语言实现堆：从基础到最佳实践

在计算机科学中，堆（Heap）是一种特殊的数据结构，它是完全二叉树，并且满足堆属性。在堆中，每个节点的值都大于或等于其子节点的值（最大堆），或者每个节点的值都小于或等于其子节点的值（最小堆）。堆在许多算法中都有广泛应用，如优先队列、堆排序等。本文将详细介绍如何使用C语言实现堆，并涵盖其基础概念、使用方法、常见实践以及最佳实践。

C语言实现哈夫曼树：从基础到实践

哈夫曼树（Huffman Tree），又称最优二叉树，是一种带权路径长度最短的二叉树。在数据压缩、编码译码等领域有着广泛的应用。本文将详细介绍如何使用C语言实现哈夫曼树，包括其基础概念、使用方法、常见实践以及最佳实践。通过阅读本文，读者将能够深入理解哈夫曼树的原理，并在实际项目中灵活运用。

C语言实现插入排序算法：深入解析与实践

在计算机科学领域，排序算法是一项基础且重要的技术。插入排序（Insertion Sort）作为一种简单直观的排序算法，在许多场景下都有着广泛的应用。本文将深入探讨如何使用C语言实现插入排序算法，涵盖基础概念、使用方法、常见实践以及最佳实践，帮助读者全面掌握这一算法并能在实际项目中灵活运用。

C语言实现插值查找算法：深入探索与实践

在计算机科学中，查找算法是一类用于在数据集合中寻找特定元素的算法。插值查找（Interpolation Search）是一种高效的查找算法，特别适用于均匀分布的数据。与传统的二分查找相比，插值查找能够更快地定位目标元素，减少查找次数。本文将详细介绍如何使用C语言实现插值查找算法，包括基础概念、使用方法、常见实践以及最佳实践。

C语言实现KMP字符串匹配算法

在字符串处理中，字符串匹配是一项常见的任务。KMP（Knuth-Morris-Pratt）算法是一种高效的字符串匹配算法，它能够在不进行回溯的情况下快速找到模式串在主串中出现的位置。相较于传统的暴力匹配算法，KMP算法通过预处理模式串，构建部分匹配表（也称为前缀函数），从而大大提高了匹配效率。本文将详细介绍如何使用C语言实现KMP字符串匹配算法。

C语言实现线性探测哈希：从基础到实践

在计算机科学中，哈希表是一种用于数据存储和检索的数据结构，它能够在平均情况下以非常高的效率执行插入、查找和删除操作。线性探测哈希是实现哈希表的一种简单而有效的方法。本文将深入探讨如何使用C语言实现线性探测哈希，涵盖基础概念、使用方法、常见实践以及最佳实践。通过阅读本文，读者将能够深入理解线性探测哈希的原理，并能够在实际项目中高效地应用它。

C语言实现线性查找算法：从基础到最佳实践

线性查找（Linear Search）是一种在数据集合中查找特定元素的基本算法。它的原理简单直接，依次检查数据集中的每个元素，直到找到目标元素或者遍历完整个数据集。在C语言中，实现线性查找算法能够帮助我们理解基本的算法设计和数组操作。本文将深入探讨C语言实现线性查找算法的各个方面，包括基础概念、使用方法、常见实践以及最佳实践，帮助读者全面掌握这一算法并能在实际项目中高效运用。

C语言实现链表：从基础到最佳实践

在C语言编程中，链表是一种重要的数据结构。与数组不同，链表的元素在内存中不必连续存储，这使得它在插入和删除操作上具有更高的效率。本文将详细介绍C语言中链表的基础概念、使用方法、常见实践以及最佳实践，帮助读者深入理解并熟练运用链表这一数据结构。

C语言实现最长公共子序列算法

在计算机科学和数学领域，最长公共子序列（Longest Common Subsequence，LCS）问题是一个经典的动态规划问题。给定两个序列，我们需要找到一个最长的子序列，这个子序列在两个原始序列中都按相同顺序出现，但不一定是连续的。例如，对于序列 X = {1, 3, 4, 5, 6, 7, 7, 8} 和 Y = {3, 5, 7, 4, 8, 6, 7, 8, 2}，它们的一个最长公共子序列是 {3, 5, 7, 8}。LCS 算法在许多领域都有应用，如文本编辑中的差异比较、生物信息学中的 DNA 序列比对等。