1. 算法概述快速排序Quick Sort是由英国计算机科学家 Tony Hoare 于 1959 年提出的一种高效排序算法也是目前应用最广泛的排序算法之一。它基于分治Divide and Conquer思想通过一趟排序将待排记录分割成独立的两部分其中一部分的关键字均比另一部分的关键字小然后分别对这两部分继续进行排序以达到整个序列有序的目的。快速排序的平均时间复杂度为O(n log n)最坏情况下为O(n²)空间复杂度为O(log n)递归栈开销。由于其内部循环可以在大多数实际架构上高效运行快速排序通常比其他 O(n log n) 算法更快这也是 Java 的Arrays.sort()和 C 标准库qsort()都采用它的原因。2. 算法原理快速排序的核心操作是分区Partition。其基本步骤如下选择基准从待排序序列中选取一个元素作为基准值pivot。分区操作将序列重新排列所有比基准值小的元素放在基准前面所有比基准值大的元素放在基准后面相等的元素可以放在任意一边。经过这一步基准值就处于其最终位置。递归排序递归地对基准值左右两侧的子序列重复上述步骤直到子序列长度为 0 或 1此时整个序列已经有序。分区过程图解以序列[5, 3, 8, 4, 2]为例选择最后一个元素2作为基准初始序列: [5, 3, 8, 4, 2]选择基准 pivot 2分区: [2, 3, 8, 4, 5]基准 2 已就位左子序列: []右子序列: [3, 8, 4, 5]递归完成3. 代码实现3.1 基础实现MATLABMATLAB 数组下标从 1 开始且没有内置swap函数可用arr([i j]) arr([j i])一行完成交换。将以下代码保存为quickSortDemo.m即可运行functionquickSortDemo()arr[53842716];arrquickSort(arr,1,length(arr));disp(排序结果);disp(arr);% 输出: 1 2 3 4 5 6 7 8endfunctionarrquickSort(arr,low,high)iflowhigh[arr,pivotIndex]partition(arr,low,high);arrquickSort(arr,low,pivotIndex-1);arrquickSort(arr,pivotIndex1,high);endendfunction[arr,pivotIndex]partition(arr,low,high)pivotarr(high);% 选择最后一个元素作为基准ilow-1;% 小于基准的元素的边界forjlow:high-1ifarr(j)pivotii1;arr([ij])arr([ji]);% 交换endendarr([i1high])arr([highi1]);% 基准归位pivotIndexi1;end3.2 优化版本三数取中 插入排序当序列接近有序时基础实现会退化为 O(n²)。通过三数取中选择基准和小区间插入排序可以显著优化性能。MATLAB 版本如下保存为quickSortOptimizedDemo.mfunctionquickSortOptimizedDemo()arr[53842716];arrquickSort(arr,1,length(arr));disp(排序结果);disp(arr);endfunctionarrquickSort(arr,low,high)INSERTION_THRESHOLD7;% 小区间使用插入排序ifhigh-lowINSERTION_THRESHOLD arrinsertionSort(arr,low,high);return;end[arr,pivotIndex]partition(arr,low,high);arrquickSort(arr,low,pivotIndex-1);arrquickSort(arr,pivotIndex1,high);endfunction[arr,pivotIndex]partition(arr,low,high)% 三数取中low、mid、high 三个位置的中值作为基准midlowfloor((high-low)/2);ifarr(mid)arr(low),arr([low mid])arr([mid low]);endifarr(high)arr(low),arr([low high])arr([high low]);endifarr(high)arr(mid),arr([mid high])arr([high mid]);endarr([mid high-1])arr([high-1mid]);% 将基准藏到 high-1pivotarr(high-1);ilow;jhigh-1;whiletrueii1;whilearr(i)pivot,ii1;endjj-1;whilejlowarr(j)pivot,jj-1;endifij,break;endarr([ij])arr([ji]);endarr([ihigh-1])arr([high-1i]);pivotIndexi;endfunctionarrinsertionSort(arr,low,high)forilow1:high keyarr(i);ji-1;whilejlowarr(j)keyarr(j1)arr(j);jj-1;endarr(j1)key;endend4. 复杂度分析指标最好情况平均情况最坏情况时间复杂度O(n log n)O(n log n)O(n²)空间复杂度O(log n)O(log n)O(n)稳定性不稳定不稳定不稳定最好/平均情况每次分区都能将序列均匀分割递归深度为 log n每层需要 O(n) 的比较总复杂度 O(n log n)。最坏情况每次分区都极度不平衡如序列已有序且固定选首元素递归深度为 n退化为 O(n²)。稳定性快速排序是不稳定排序因为分区过程中元素的相对顺序可能被打乱。5. 案例分析案例对成绩单进行排序假设有一个学生成绩数组需要按分数从低到高排序。MATLAB 中可用元胞数组cell array存放学生姓名配合分数数组进行排序保存为scoreSorterDemo.mfunctionscoreSorterDemo()names{张三,李四,王五,赵六,孙七};scores[8592786588];[scores,idx]quickSort(scores,1,length(scores));namesnames(idx);% 按排序后的索引重排姓名disp(排序结果);fork1:length(names)fprintf(%s: %d\n,names{k},scores(k));endendfunction[arr,idx]quickSort(arr,low,high)iflowhigh[arr,idx,pivotIndex]partition(arr,low,high);[arr,idx]quickSort(arr,low,pivotIndex-1);[arr,idx]quickSort(arr,pivotIndex1,high);endendfunction[arr,idx,pivotIndex]partition(arr,low,high)pivotarr(high);ilow-1;forjlow:high-1ifarr(j)pivotii1;arr([ij])arr([ji]);endendarr([i1high])arr([highi1]);pivotIndexi1;idx1:length(arr);% 初始索引end6. 总结快速排序凭借其优秀的平均性能和广泛的应用场景成为算法学习中的必修内容。掌握其分治思想和分区操作是理解算法的关键。在实际工程中通常会结合三数取中、随机化基准、小区间插入排序等优化手段来避免最坏情况的发生。建议读者动手实现一遍并尝试用不同语言如 Python、C复现以加深理解。
