排序合集之快排详解（二）

摘要：快速排序是一种在实践中广泛使用的高效排序算法。它基于分治策略，平均时间复杂度为O(n log n)，使其成为处理大型数据集的理想选择。本文将深入探讨快速排序的各种实现方式、优化技巧以及非递归实现，并通过C语言代码示例进行详细讲解。

一、经典快速排序

1. 基本思想

快速排序的核心在于分而治之。想象一下，你要整理一堆书，你可以随机选一本书作为“基准”，然后把其他的书分成两堆：一堆是书名排在基准之前的，另一堆是排在基准之后的。接着，你再分别对这两堆书重复这个过程。这就是快速排序的基本思想！

2. 步骤

1. 选择基准(Pivot Selection)：从数组中选取一个元素作为基准（pivot）。基准的选择会影响排序效率，后面会介绍优化方法。

2. 分区操作(Partitioning)：重新排列数组，使得所有小于基准的元素位于基准之前，所有大于基准的元素位于基准之后。基准元素在此过程中会被放置在其最终排序位置。

3. 递归排序(Recursive Sorting)：递归地对基准元素左右的两个子数组进行快速排序。

3. C语言代码示例

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); } 
} int partition(int arr[], int low, int high) 
{ int pivot = arr[high]; int i = low - 1; for (int j = low; j < high; j++) { if (arr[j] < pivot) { i++; swap(&arr[i], &arr[j]);} }swap(&arr[i + 1], &arr[high]); return i + 1; 
} void swap(int* a, int* b) 
{ int t = *a; *a = *b; *b = t; 
}

4. 代码解释

• quickSort(arr[], low, high)：递归函数，对数组arr中从索引low到high的元素进行排序。递归结束的条件是low >= high，意味着子数组已经为空或者只包含一个元素，不需要再排序。

• partition(arr[], low, high)：关键函数！它选择最后一个元素作为基准，并执行分区操作，将数组划分为两个部分。i用于追踪小于基准的元素的索引。swap函数用于交换两个元素的位置。

• swap(int* a, int* b)：一个简单的交换函数，用于交换两个整数的值。

二、快速排序 - 挖坑法

1. 基本思想

挖坑法是一种巧妙的分区策略。可以这样想象：你先选一个基准数，把它“挖”出来，形成一个“坑”。然后，从数组两端开始，找到合适的数来填补这个“坑”，同时产生新的“坑”，直到左右指针相遇。

2. 步骤

1. 选择基准(Pivot Selection)：选择数组中的某个元素作为基准（通常选择第一个元素）。
2. 挖坑填数(Digging and Filling)：

• 将基准元素挖出，形成第一个“坑”。

• 从数组右端开始，寻找小于基准的元素，找到后填入左边的“坑”，并形成新的“坑”。

• 从数组左端开始，寻找大于基准的元素，找到后填入右边的“坑”，并形成新的“坑”。

• 重复上述过程，直到左右指针相遇

   3.放置基准(Pivot Placement)：将基准元素放入左右指针相遇的位置，完成分区。

3. C语言代码示例

void quickSort(int arr[], int low, int high) { if (low < high) { 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; quickSort(arr, low, i - 1); quickSort(arr, i + 1, high); }
}

4. 代码解释

关键在于while (i < j)循环中的填坑操作。理解指针i和j的移动和值的覆盖是理解这个算法的关键。

三、快速排序 - 前后指针法

1. 基本思想

前后指针法使用两个指针，i和j。指针i指向小于基准的子数组的末尾，而指针j用于遍历整个数组。如果j遇到的元素小于基准，则将其交换到i的后面，并增加i。

2. 步骤

1. 选择基准(Pivot Selection)：选择数组中的某个元素作为基准（通常选择最后一个元素）。

2. 移动指针(Moving Pointers)：

   • 使用指针j遍历数组。

   • 如果arr[j]小于基准，则将arr[j]与arr[i+1]交换，并递增i。

3. 放置基准(Pivot Placement)：将基准元素放到正确的位置。

3. C语言代码示例

void quickSort(int arr[], int low, int high) { if (low < high) { int pivot = arr[high]; int i = low; for (int j = low; j < high; j++) { if (arr[j] < pivot) { swap(&arr[i], &arr[j]);i++;}} swap(&arr[i], &arr[high]); quickSort(arr, low, i - 1); quickSort(arr, i + 1, high); }
}

4. 代码解释

i始终指向小于pivot的区域的下一个位置。在循环过程中，i之前的元素都小于pivot。

四、性能优化

1. 三数取中

• 问题：如果基准元素选择不当（例如，总是选择最大或最小元素），快速排序可能会退化到O(n²)的时间复杂度。

• 解决方案：三数取中法。从数组的第一个、中间和最后一个元素中选择中间值作为基准。这可以有效避免最坏情况的发生。

• 步骤：

1. 计算中间位置：mid = (low + high) / 2。
2. 比较 arr[low]、arr[mid] 和 arr[high]，并将中间值与 arr[high] 交换。

2. C代码示例

void quickSort(int arr[], int low, int high) { if (low < high) { int mid = (low + high) / 2;if (arr[mid] < arr[low]) swap(&arr[mid], &arr[low]);if (arr[high] < arr[low]) swap(&arr[high], &arr[low]);if (arr[mid] < arr[high]) swap(&arr[mid], &arr[high]);int pivot = arr[high]; int i = low; for (int j = low; j < high; j++) { if (arr[j] < pivot) { swap(&arr[i], &arr[j]);i++;}} swap(&arr[i], &arr[high]); quickSort(arr, low, i - 1); quickSort(arr, i + 1, high); }
}

3. 针对重复值优化

• 问题：当数组中存在大量重复元素时，快速排序的性能会下降。

• 解决方案：在分区过程中，将所有等于基准的元素集中到一起，避免对它们进行递归排序。这通常被称为“三向切分”。

4. C代码示例

void quickSort(int arr[], int low, int high) { if (low < high) { int pivot = arr[low]; int lt = low; int gt = high; int i = low + 1; while (i <= gt) { if (arr[i] < pivot) { swap(&arr[i], &arr[lt + 1]);lt++;i++;} else if (arr[i] > pivot) { swap(&arr[i], &arr[gt]);gt--;} else { i++;}} quickSort(arr, low, lt - 1); quickSort(arr, gt + 1, high); }
}

5. 代码解释

此版本将数组划分为三个部分：小于基准值、等于基准值和大于基准值。等于基准值的部分在递归调用中被排除，从而提高了具有许多重复项的数组的性能。

五、快速排序 - 非递归实现

1. 基本思想

递归版本的快速排序在处理大型数组时可能会导致栈溢出。非递归实现通过使用栈来模拟递归调用，从而避免栈溢出的问题。

2. 步骤

1. 初始化栈(Initialize Stack)：将初始的分区范围（low和high）压入栈。

2. 循环处理(Loop Processing)：从栈中弹出一个分区范围，进行分区操作。

3. 压入子分区(Push Sub-partitions)：将左右子分区的范围压入栈中，以便后续处理

3. C语言代码示例

#include <stdio.h>
#include <stdlib.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 quickSortNonRecursive(int arr[], int low, int high) { int *stack = (int *)malloc(sizeof(int) * (high - low + 1) * 2); int top = -1; stack[++top] = low; stack[++top] = high; while (top >= 0) { high = stack[top--]; low = stack[top--]; int p = partition(arr, low, high); if (p - 1 > low) { stack[++top] = low; stack[++top] = p - 1; } if (p + 1 < high) { stack[++top] = p + 1; stack[++top] = high; } } free(stack); 
}int main() { int arr[] = {10, 7, 8, 9, 1, 5}; int n = sizeof(arr) / sizeof(arr[0]); quickSortNonRecursive(arr, 0, n - 1); printf("Sorted array: \n"); for (int i = 0; i < n; i++) printf("%d ", arr[i]); return 0; 
}

4. 代码解释

• 使用动态分配的栈来避免固定大小的栈的限制。

• 在算法结束时释放动态分配的内存以避免内存泄漏。

• 栈存储要处理的分区的边界。

• 该算法迭代地从栈中弹出分区边界，对分区进行分区，并将新分区推入栈中，直到所有分区都被处理完毕。

合适的基准和采用适当的优化策略，可以充分发挥其性能优势。 理解快速排序的不同实现方式有助于在实际应用中选择最合适的算法变体。 无论是经典递归实现还是非递归实现，快速排序都是每个程序员工具箱中不可或缺的一部分.