C语言实现quickSort.rar

快速排序（QuickSort）是一种高效的排序算法，由C.A.R. Hoare在1960年提出。它的基本思想是采用分治法（Divide and Conquer）将一个大问题分解为若干个小问题来解决。在C语言中，快速排序通常通过递归实现，其主要步骤包括选择一个“基准”元素，将数组分为两部分，一部分的所有元素都小于基准，另一部分的所有元素都大于或等于基准，然后对这两部分再分别进行快速排序，直到所有元素排序完成。 以下是快速排序的C语言实现详解： 1. **选取基准**：在待排序的序列中选择一个元素作为基准，这个元素可以是任意位置的，但一般选择第一个或最后一个元素。 ```c int pivot = array[low]; // 选择第一个元素为基准 ``` 2. **分区操作**：将数组分为两个子序列，使得左边的元素都小于基准，右边的元素都大于或等于基准。这个过程可以通过两个指针`i`和`j`来实现，`i`从左向右移动，`j`从右向左移动，当`i`找到大于等于基准的元素，`j`找到小于基准的元素时，交换这两个元素，最后使`i`和`j`相遇。 ```c int i = low, j = high; while (i < j) { while (array[i] < pivot) { i++; } // 找到大于等于基准的元素 while (array[j] >= pivot) { j--; } // 找到小于基准的元素 if (i < j) { swap(&array[i], &array[j]); } // 交换元素 } ``` 3. **递归排序**：将分区后的两个子序列分别进行快速排序。由于分区操作已经保证了基准元素的位置正确，所以可以对基准左边的子序列和右边的子序列分别进行递归调用快速排序函数。 ```c if (low < j) { quickSort(array, low, j); } // 对左子序列排序 if (high > i) { quickSort(array, i, high); } // 对右子序列排序 ``` 4. **完整代码示例**：结合以上步骤，快速排序的完整C语言实现如下： ```c #include <stdio.h> void swap(int* a, int* b) { int t = *a; *a = *b; *b = t; } void quickSort(int array[], int low, int high) { if (low < high) { int pivot = array[low]; int i = low, j = high; while (i < j) { while (array[i] < pivot) { i++; } while (array[j] >= pivot) { j--; } if (i < j) { swap(&array[i], &array[j]); } } array[low] = array[j]; array[j] = pivot; quickSort(array, low, j - 1); quickSort(array, j + 1, high); } } void printArray(int array[], int size) { for (int i = 0; i < size; i++) { printf("%d ", array[i]); } printf("\n"); } int main() { int array[] = {10, 7, 8, 9, 1, 5}; int n = sizeof(array) / sizeof(array[0]); quickSort(array, 0, n - 1); printf("Sorted array: \n"); printArray(array, n); return 0; } ``` 快速排序的时间复杂度在平均情况下是O(n log n)，在最坏情况下是O(n^2)，但这种情况非常罕见。空间复杂度是O(log n)，因为快速排序是递归的，需要栈空间。快速排序是原地排序算法，不需要额外的存储空间，因此在实际应用中被广泛使用。