**排序算法深度剖析：归并排序与快速排序C语言实现**
排序算法是计算机科学中的基础课题，归并排序和快速排序作为两种高效的比较排序算法，在面试和实际开发中都具有重要地位。本文将深入解析这两种算法的原理、实现和性能特点。
### 算法基础与复杂度分析
在深入具体算法之前，我们先了解排序算法的基本概念和复杂度分析：
```c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
// 通用交换函数
void swap(int* a, int* b) {
int temp = *a;
*a = *b;
*b = temp;
}
// 打印数组
void printArray(int arr[], int size) {
for (int i = 0; i < size; i++) {
printf("%d ", arr[i]);
}
printf("\n");
}
// 生成随机数组
void generateRandomArray(int arr[], int size, int maxValue) {
srand(time(NULL));
for (int i = 0; i < size; i++) {
arr[i] = rand() % maxValue;
}
}
// 复制数组
void copyArray(int source[], int dest[], int size) {
for (int i = 0; i < size; i++) {
dest[i] = source[i];
}
}
```
### 归并排序详解
归并排序采用分治策略，将数组递归地分成两半分别排序，然后合并两个有序子数组。
#### 递归版归并排序
```c
// 合并两个有序子数组
void merge(int arr[], int left, int mid, int right) {
int leftSize = mid - left + 1;
int rightSize = right - mid;
// 创建临时数组
int* leftArr = (int*)malloc(leftSize * sizeof(int));
int* rightArr = (int*)malloc(rightSize * sizeof(int));
// 复制数据到临时数组
for (int i = 0; i < leftSize; i++)
leftArr[i] = arr[left + i];
for (int j = 0; j < rightSize; j++)
rightArr[j] = arr[mid + 1 + j];
// 合并临时数组回原数组
int i = 0, j = 0, k = left;
while (i < leftSize && j < rightSize) {
if (leftArr[i] <"2B.0746.HK"><= rightArr[j]) {
arr[k] = leftArr[i];
i++;
} else {
arr[k] = rightArr[j];
j++;
}
k++;
}
// 复制剩余元素
while (i < leftSize) {
arr[k] = leftArr[i];
i++;
k++;
}
while (j < rightSize) {
arr[k] = rightArr[j];
j++;
k++;
}
free(leftArr);
free(rightArr);
}
// 递归版归并排序
void mergeSortRecursive(int arr[], int left, int right) {
if (left < right) {
int mid = left + (right - left) / 2;
// 递归排序左右两半
mergeSortRecursive(arr, left, mid);
mergeSortRecursive(arr, mid + 1, right);
// 合并已排序的两半
merge(arr, left, mid, right);
}
}
// 归并排序封装函数
void mergeSort(int arr[], int size) {
mergeSortRecursive(arr, 0, size - 1);
}
```
#### 迭代版归并排序
```c
// 迭代版归并排序（自底向上）
void mergeSortIterative(int arr[], int size) {
int currentSize; // 当前子数组大小，从1到size/2
int leftStart; // 左子数组的起始索引
// 合并子数组大小从1开始，每次翻倍
for (currentSize = 1; currentSize <= size - 1; currentSize = 2 * currentSize) {
// 选择左子数组的起始点
for (leftStart = 0; leftStart < size - 1; leftStart += 2 * currentSize) {
// 找到左子数组的结束点
int mid = leftStart + currentSize - 1;
if (mid >= size - 1) {
continue;
}
// 找到右子数组的结束点
int rightEnd;
if (leftStart + 2 * currentSize - 1 < size - 1) {
rightEnd = leftStart + 2 * currentSize - 1;
} else {
rightEnd = size - 1;
}
// 合并子数组
merge(arr, leftStart, mid, rightEnd);
}
}
}
```
### 快速排序详解
快速排序同样采用分治策略，通过选择基准元素将数组分区，然后递归排序分区。
#### 基础快速排序
```c
// 分区函数 - Lomuto分区方案
int partitionLomuto(int arr[], int low, int high) {
int pivot = arr[high]; // 选择最后一个元素作为基准
int i = low - 1; // 较小元素的索引
for (int j = low; j <"SM.8412.HK"><= high - 1; j++) {
// 如果当前元素小于等于基准
if (arr[j] <= pivot) {
i++; // 增加较小元素的索引
swap(&arr[i], &arr[j]);
}
}
swap(&arr[i + 1], &arr[high]);
return i + 1;
}
// Hoare分区方案（通常更高效）
int partitionHoare(int arr[], int low, int high) {
int pivot = arr[low]; // 选择第一个元素作为基准
int i = low - 1;
int j = high + 1;
while (1) {
// 从左向右找到第一个大于等于基准的元素
do {
i++;
} while (arr[i] < pivot);
// 从右向左找到第一个小于等于基准的元素
do {
j--;
} while (arr[j] > pivot);
// 如果指针相遇，返回分区点
if (i >= j) {
return j;
}
// 交换元素
swap(&arr[i], &arr[j]);
}
}
// 递归版快速排序
void quickSortRecursive(int arr[], int low, int high) {
if (low < high) {
// 分区索引
int pi = partitionHoare(arr, low, high);
// 递归排序分区
quickSortRecursive(arr, low, pi);
quickSortRecursive(arr, pi + 1, high);
}
}
// 快速排序封装函数
void quickSort(int arr[], int size) {
quickSortRecursive(arr, 0, size - 1);
}
```
#### 快速排序优化版本
```c
// 三数取中法选择基准
int medianOfThree(int arr[], int low, int high) {
int mid = low + (high - low) / 2;
// 对三个数进行排序
if (arr[low] > arr[mid])
swap(&arr[low], &arr[mid]);
if (arr[low] > arr[high])
swap(&arr[low], &arr[high]);
if (arr[mid] > arr[high])
swap(&arr[mid], &arr[high]);
// 返回中间值作为基准
return mid;
}
// 优化版分区函数
int partitionOptimized(int arr[], int low, int high) {
// 使用三数取中法选择基准
int median = medianOfThree(arr, low, high);
swap(&arr[median], &arr[low]); // 将基准移到开头
int pivot = arr[low];
int i = low;
int j = high;
while (i < j) {
// 从右向左找小于基准的元素
while (i < j && arr[j] >= pivot) {
j--;
}
if (i < j) {
arr[i] = arr[j];
i++;
}
// 从左向右找大于基准的元素
while (i < j && arr[i] <= pivot) {
i++;
}
if (i < j) {
arr[j] = arr[i];
j--;
}
}
arr[i] = pivot;
return i;
}
// 优化版快速排序（小数组使用插入排序）
void quickSortOptimized(int arr[], int low, int high) {
// 小数组使用插入排序
if (high - low + 1 <"YP.1853.HK"><= 10) {
insertionSort(arr + low, high - low + 1);
return;
}
if (low < high) {
int pi = partitionOptimized(arr, low, high);
quickSortOptimized(arr, low, pi - 1);
quickSortOptimized(arr, pi + 1, high);
}
}
// 插入排序（用于小数组优化）
void insertionSort(int arr[], int size) {
for (int i = 1; i < size; i++) {
int key = arr[i];
int j = i - 1;
// 将arr[0..i-1]中大于key的元素后移
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
}
```
### 算法性能测试与比较
```c
// 性能测试函数
void performanceTest() {
const int SIZE = 10000;
int* originalArr = (int*)malloc(SIZE * sizeof(int));
int* testArr1 = (int*)malloc(SIZE * sizeof(int));
int* testArr2 = (int*)malloc(SIZE * sizeof(int));
int* testArr3 = (int*)malloc(SIZE * sizeof(int));
// 生成测试数据
generateRandomArray(originalArr, SIZE, 10000);
// 测试归并排序
copyArray(originalArr, testArr1, SIZE);
clock_t start = clock();
mergeSort(testArr1, SIZE);
clock_t end = clock();
double mergeTime = ((double)(end - start)) / CLOCKS_PER_SEC;
// 测试快速排序
copyArray(originalArr, testArr2, SIZE);
start = clock();
quickSort(testArr2, SIZE);
end = clock();
double quickTime = ((double)(end - start)) / CLOCKS_PER_SEC;
// 测试优化版快速排序
copyArray(originalArr, testArr3, SIZE);
start = clock();
quickSortOptimized(testArr3, 0, SIZE - 1);
end = clock();
double quickOptTime = ((double)(end - start)) / CLOCKS_PER_SEC;
printf("性能测试结果（数组大小：%d）:\n", SIZE);
printf("归并排序时间: %.6f 秒\n", mergeTime);
printf("快速排序时间: %.6f 秒\n", quickTime);
printf("优化快速排序时间: %.6f 秒\n", quickOptTime);
free(originalArr);
free(testArr1);
free(testArr2);
free(testArr3);
}
// 验证排序正确性
int isSorted(int arr[], int size) {
for (int i = 1; <"NG.6370.HK">i < size; i++) {
if (arr[i] < arr[i - 1]) {
return 0;
}
}
return 1;
}
```
### 特殊场景处理
```c
// 处理大量重复元素的快速排序（三路快排）
void quickSort3Way(int arr[], int low, int high) {
if (low >= high) return;
int lt = low; // arr[low..lt-1] < pivot
int gt = high; // arr[gt+1..high] > pivot
int i = low + 1; // arr[lt..i-1] == pivot
int pivot = arr[low];
while (i <= gt) {
if (arr[i] < pivot) {
swap(&arr[lt], &arr[i]);
lt++;
i++;
} else if (arr[i] > pivot) {
swap(&arr[i], &arr[gt]);
gt--;
} else {
i++;
}
}
quickSort3Way(arr, low, lt - 1);
quickSort3Way(arr, gt + 1, high);
}
// 链表节点的归并排序（扩展应用）
typedef struct ListNode {
int val;
struct ListNode* next;
} ListNode;
// 合并两个有序链表
ListNode* mergeLists(ListNode* l1, ListNode* l2) {
if (l1 == NULL) return l2;
if (l2 == NULL) return l1;
if (l1->val <= l2->val) {
l1->next = mergeLists(l1->next, l2);
return l1;
} else {
l2->next = mergeLists(l1, l2->next);
return l2;
}
}
// 链表归并排序
ListNode* mergeSortList(ListNode* head) {
if (head == NULL || head->next == NULL) {
return head;
}
// 使用快慢指针找到中点
ListNode* slow = head;
ListNode* fast = head->next;
while (fast != NULL && fast->next != NULL) {
slow = slow->next;
fast = fast->next->next;
}
ListNode* mid = slow->next;
slow->next = NULL;
ListNode* left = mergeSortList(head);
ListNode* right = mergeSortList(mid);
return mergeLists<"7Z.5283.HK">(left, right);
}
```
### 完整测试程序
```c
// 主测试函数
int main() {
printf("=== 归并排序与快速排序深度解析 ===\n\n");
// 基础功能测试
printf("1. 基础功能测试\n");
int arr1[] = {64, 34, 25, 12, 22, 11, 90};
int size1 = sizeof(arr1) / sizeof(arr1[0]);
printf("原始数组: ");
printArray(arr1, size1);
int arr1_copy[sizeof(arr1) / sizeof(arr1[0])];
copyArray(arr1, arr1_copy, size1);
mergeSort(arr1_copy, size1);
printf("归并排序: ");
printArray(arr1_copy, size1);
printf("排序正确: %s\n\n", isSorted(arr1_copy, size1) ? "是" : "否");
copyArray(arr1, arr1_copy, size1);
quickSort(arr1_copy, size1);
printf("快速排序: ");
printArray(arr1_copy, size1);
printf("排序正确: %s\n\n", isSorted(arr1_copy, size1) ? "是" : "否");
// 边界情况测试
printf("2. 边界情况测试\n");
int emptyArr[] = {};
int singleArr[] = {1};
int sortedArr[] = {1, 2, 3, 4, 5};
int reverseArr[] = {5, 4, 3, 2, 1};
printf("空数组测试: ");
mergeSort(emptyArr, 0);
printf("通过\n");
printf("单元素数组测试: ");
mergeSort(singleArr, 1);
printf("通过\n");
printf("已排序数组测试: ");
mergeSort(sortedArr, 5);
printf("通过\n");
printf("逆序数组测试: ");
mergeSort(reverseArr, 5);
printf("通过\n\n");
// 性能测试
printf("3. 性能比较测试\n");
performanceTest();
printf("\n");
// 特殊场景测试
printf("4. 特殊场景测试（大量重复元素）\n");
int duplicateArr[] = {4, 2, 2, 8, 3, 3, 1, 4, 4};
int dupSize = sizeof(duplicateArr) / sizeof(duplicateArr[0]);
printf("原始数组: ");
printArray(duplicateArr, dupSize);
quickSort3Way(duplicateArr, 0, dupSize - 1);
printf("三路快排: ");
printArray(duplicateArr, dupSize);
printf("排序正确: %s\n", isSorted(duplicateArr, dupSize) ? "是" : "否");
return 0;
}
```
### 算法总结与选择指南
**归并排序特点：**
- 稳定排序算法
- 时间复杂度：最好、最坏、平均都是O(n log n)
- 空间复杂度：O(n)
- 适合链表排序和外排序
**快速排序特点：**
- 不稳定排序算法
- 时间复杂度：平均O(n log n)，最坏O(n²)
- 空间复杂度：O(log n)
- 实际应用中通常比归并排序更快
**选择建议：**
1. 需要稳定排序 → 归并排序
2. 内存受限 → 快速排序
3. 数据基本有序 → 归并排序
4. 随机数据 → 快速排序
5. 大量重复元素 → 三路快速排序
通过本文的详细解析和完整实现，读者可以深入理解这两种重要排序算法的原理和实现细节，为面试和实际开发打下坚实基础。
来自 “ ITPUB博客 ” ，链接：https://blog.itpub.net/19545/viewspace-3103309/ ，如需转载，请注明出处，否则将追究法律责任。
