🔥 1. 快速排序（Quick Sort）
核心思想
本算法用到了分区的思想，分而治之，即分治法。
分治法：将原问题分解为若干个子问题，直到子问题可以求解为止，子问题的解的合并即原问题的解。
产生的子问题往往和原问题相同，只是原问题的较小规模的表达。递归。
- 选一个基准（pivot）（通常选最后一个元素）。
- 分区（Partition）：把比
pivot小的放左边，大的放右边。 - 递归排序：对左右两部分分别排序。
public void quicksort(int[]arr,left,right){ if (left>right) return //当left大于right的时候就可以返回了 int privotIndex=partition（arr，left,right）;//分区的位置 quicksort(arr,privotIndex+1,right);//排序右半部分 quicksort(arr,left),privotIndex-1);//排序左半部分 开始递归 }
quicksort不断递归自己，对privot左右两边的数据进行比较分区排序，比基准小的放左边，比基准大的放在右边。
public void partition(int[]arr, left,right){ int pivot=arr[right];//选择基准，以最后一个元素为基准 int i=left;//i是小于pivot的边界值 for(int j=left;j<right;j++)//遍历完传进来的数组，数组最左边的开始 { if(arr[j]<=pivot){ 当当前元素小于等于pivot 交换到左边 swap(arr,i,j); i++//移动边界 } } swap(arr,i.right);将pivot 放在正确的位置 return i;返回pivot 的索引 } public swap(int[]arr ,i,j){ int temp=arr[i]; arr[i]=arr[j]; arr[j]=temp; }
如何手撕？
- 先写
partition（核心逻辑）。 - 再写
quickSort（递归调用）。 - 最后写
swap（辅助函数）。
关于基准的选择，与时间复杂度的关系：
| 时间复杂度 | 平均 O(n log n)，最坏 O(n²)（如数组已有序） |
| 空间复杂度 | O(1)（原地排序） |
| 稳定性 | 不稳定（可能交换相同元素） |
| 适用场景 | 通用排序（如 Arrays.sort() 底层用它 |
如何优化快速排序？
随机化基准（避免最坏情况）。
三数取中法（选第一个、中间、最后一个的中位数作为基准）
![现有一个接口DataOperation定义了排序方法sort(int[])和查找方法search(int[],int)，已知类QuickSort的quickSort(int[])方法实现了快速排序算法](https://ucc.alicdn.com/b3c447iaqrtq2_20240813_8507e56fc1e0475c88702b767789ed11.png?x-oss-process=image/format,webp/resize,h_160,m_lfit)