快速排序算法原理与多语言实现
快速排序是一种基于分治策略的高效排序算法，其核心思想是通过选择一个基准元素，将数组划分为两部分：左侧元素均小于等于基准，右侧元素均大于基准，然后递归处理左右子数组。尽管最坏情况时间复杂度为 O(n²)，但在平均情况下其性能接近 O(n log n)，且常数因子优于归并排序，因此在实际应用中广泛使用。
算法流程
- 从数组中选取一个元素作为基准（pivot）。
- 重新组织数组，使所有小于基准的元素位于其左侧，大于基准的位于右侧，基准最终位于其排序后正确位置。
- 对基准左右两侧的子数组分别递归执行上述过程，直至子数组长度为 0 或 1。
JavaScript 实现
function quickSort(arr, start = 0, end = arr.length - 1) {
if (start >= end) return arr;
const pivotIndex = partition(arr, start, end);
quickSort(arr, start, pivotIndex - 1);
quickSort(arr, pivotIndex + 1, end);
return arr;
}
function partition(arr, left, right) {
const pivotValue = arr[right];
let storeIndex = left;
for (let i = left; i < right; i++) {
if (arr[i] <= pivotValue) {
[arr[i], arr[storeIndex]] = [arr[storeIndex], arr[i]];
storeIndex++;
}
}
[arr[storeIndex], arr[right]] = [arr[right], arr[storeIndex]];
return storeIndex;
}Python 实现
def quick_sort(arr, low=0, high=None):
if high is None:
high = len(arr) - 1
if low >= high:
return arr
pivot_idx = partition(arr, low, high)
quick_sort(arr, low, pivot_idx - 1)
quick_sort(arr, pivot_idx + 1, high)
return arr
def partition(arr, left, right):
pivot = arr[right]
i = left - 1
for j in range(left, right):
if arr[j] <= pivot:
i += 1
arr[i], arr[j] = arr[j], arr[i]
arr[i + 1], arr[right] = arr[right], arr[i + 1]
return i + 1C语言实现
void swap(int *a, int *b) {
int temp = *a;
*a = *b;
*b = temp;
}
void quickSort(int arr[], int low, int high) {
if (low >= high) return;
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]);
quickSort(arr, low, i);
quickSort(arr, i + 2, high);
}C++ 实现（模板版本）
template<typename T>
void quickSort(T arr[], int low, int high) {
if (low >= high) return;
T pivot = arr[high];
int i = low - 1;
for (int j = low; j < high; ++j) {
if (arr[j] <= pivot) {
++i;
std::swap(arr[i], arr[j]);
}
}
std::swap(arr[i + 1], arr[high]);
quickSort(arr, low, i);
quickSort(arr, i + 2, high);
}
template<typename T>
void sortArray(T arr[], int size) {
quickSort(arr, 0, size - 1);
}