前言
分治法：在每一轮挑选一个基准元素，并让其他比它大的元素移动到数列一边，比它小的元素移动到数列的另一边，从而把数列拆解成两个部分。
正文
一、函数签名
function quick_sort(input:number[],start:number,end:number){ if(start>=end){ return } let pivotIndex=partition(input,start,end) // 1. quick_sort(input,start,pivotIndex-1) // 2. quick_sort(input,pivotIndex+1,end) }
注释：
1.通过执行 partition 函数输入数组、当前操作的左侧下标、当前操作数组的右侧下标，返回 pivotIndex 就是选取的基准元素的数组下标；
2.找到下一个基准元素数组下标之后，两次递归执行 quick_sort 函数，第一次就是在基准元素左侧执行快速排序，第二次就是在基准元素右侧执行快速排序；
3.下面开始实现 partition 函数。
二、partition 函数实现
function partition(input:number[],start:number,end:number):number { let pivot = input[start] // 1. let left = start // 2. let right = end // 3. while (left != right) { while(left<right&&input[right]>pivot){ // 4. right-- } while(left<right&&input[left]<=pivot){ // 5. left++ } if(left<right){ // 6. let tmp=input[left] input[left]=input[right] input[right]=tmp } } input[start] = input[left] // 7. input[left] = pivot return left }
注释：partition 函数返回基准元素的数组下标
1.选取基准元素值为数组的第一个元素（也可以不用第一个元素而是随机选择）
2.赋值 left 变量，确定partition 操作左边界；
3.赋值 right 变量，确定 partition 操作有边界；
4.当 left 小于 right 并且 最右侧值大于基准元素值时，右边界左移即：right--;
5.当 left 小于 right 并且 最左侧值小于等于基准元素时，左边界右移即：left++;
6.当 5,6执行完，left 小于 right 时，交换左右边界的值；
7.重复操作5，6，直到左右边界重合
8.左右边界重合，将基准元素与重合处互换，返回重合处的数组下标。
结果校验
let test=[6,3,4,21,7,8,4,35,63] console.log("start:",test.toString()) quick_sort(test,0,test.length-1) console.log("end:",test.toString())
结果校验
![现有一个接口DataOperation定义了排序方法sort(int[])和查找方法search(int[],int)，已知类QuickSort的quickSort(int[])方法实现了快速排序算法](https://ucc.alicdn.com/b3c447iaqrtq2_20240813_8507e56fc1e0475c88702b767789ed11.png?x-oss-process=image/resize,h_160,m_lfit)