C语言快速排序算法 Hoare 版本实现详解

#include <stdio.h>

void swap(int* a, int* b) { int temp = *a; *a = *b; *b = temp; }

void QuickSort(int* arr, int begin, int end) { // 只有一个数或区间不存在 if (begin >= end) return; int left = begin; int right = end; // 选左边为 key int keyi = begin; while (begin < end) { // 右边选小 等号防止和 key 值相等 防止顺序 begin 和 end 越界 while (arr[end] >= arr[keyi] && begin < end) { --end; } // 左边选大 while (arr[begin] <= arr[keyi] && begin < end) { ++begin; } // 小的换到右边，大的换到左边 swap(&arr[begin], &arr[end]); } swap(&arr[keyi], &arr[end]); keyi = end; // [left, keyi-1] keyi [keyi+1, right] QuickSort(arr, left, keyi - 1); QuickSort(arr, keyi + 1, right); }

int main() { int arr[] = { 5, 3, 1, 4, 6, 2 }; int n = sizeof(arr) / sizeof(int); QuickSort(arr, 0, n - 1); for (int i = 0; i < n; ++i) { printf('%d ', arr[i]); } printf(' '); return 0; }