c 实现数组和指针的快速排序

快速排序是一种高效的排序算法，由英国计算机科学家C.A.R. Hoare在1960年提出。它的基本思想是分治法（Divide and Conquer），通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，然后分别对这两部分记录继续进行排序，以达到整个序列有序的目的。 在C语言中实现快速排序，首先我们需要理解数组和指针的概念。数组是相同类型元素的集合，可以通过下标访问每个元素。而指针则可以看作是内存地址的别名，它指向数组中的某个元素。在快速排序中，我们通常使用指针来操作数组，因为它允许我们高效地访问和修改内存位置。 快速排序的主要步骤如下： 1. **选择基准元素（Pivot Selection）**：选取数组中的一个元素作为基准，通常选择第一个或最后一个元素，也可以随机选择。 2. **分区操作（Partitioning）**：根据基准元素将数组分为两部分，小于或等于基准的元素放在基准的左边，大于基准的元素放在基准的右边。这个过程通过两个指针，一个从左向右扫描，一个从右向左扫描，当找到不满足条件的元素时，交换它们的位置。让基准元素位于分界线处，使得基准左边的所有元素都小于等于基准，右边的所有元素都大于基准。 3. **递归排序（Recursion）**：对基准左边和右边的子数组分别进行快速排序，直到所有子数组只有一个元素或者为空，排序结束。 以下是一个简单的C语言实现快速排序的示例代码： ```c #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) { int pi = partition(arr, low, high); quickSort(arr, low, pi - 1); quickSort(arr, pi + 1, high); } } void printArray(int A[], int size) { for (int i = 0; i < size; i++) printf("%d ", A[i]); printf("\n"); } int main() { int arr[] = {10, 7, 8, 9, 1, 5}; int n = sizeof(arr) / sizeof(arr[0]); printf("Original array: \n"); printArray(arr, n); quickSort(arr, 0, n - 1); printf("\nSorted array: \n"); printArray(arr, n); return 0; } ``` 在这个例子中，`swap()`函数用于交换两个元素，`partition()`函数执行分区操作，`quickSort()`函数是递归排序的核心，`printArray()`函数用于输出排序后的数组。在`main()`函数中，我们创建了一个数组并调用`quickSort()`对其进行排序，最后打印出排序结果。 快速排序的平均时间复杂度为O(n log n)，但在最坏的情况下，如果输入数组已经排序或几乎排序，其时间复杂度会退化为O(n^2)。为了避免这种情况，可以采用三数取中法、随机化选择基准等策略优化选择基准的过程，提高算法的稳定性。 此外，快速排序在原地排序，不需要额外的存储空间，但需要注意的是，由于递归调用，如果数据量非常大，可能会导致栈溢出。在实际应用中，可以根据具体需求考虑使用尾递归优化或其他排序算法，如归并排序、堆排序等。