西安市网站建设_网站建设公司_需求分析_seo优化

一、快速排序的核心思想

快速的精髓在于“分治”，即每一轮只做一件事：选一个基准值，把比它小的丢左边，比它大的丢右边，最后当基准值归位后，它左右两边的区间就成为了两个独立的子问题，直接递归处理就行

速记：
选基—划区—递归

代码框架

publicstaticvoidquickSort(int[]array){quick(array,0,array.length-1);}privatestaticvoidquick(int[]array,intstart,intend){if(start>=end){return;}intpivot=partition(array,start,end);quick(array,start,pivot-1);quick(array,pivot+1,end);}privatestaticvoidswap(int[]array,inti,intminIndex){inttmp=array[i];array[i]=array[minIndex];array[minIndex]=tmp;}//核心方法privatestaticintpartition(int[]array,intleft,intright)

二、三种切分方法

1.Hoare 法（左右指针法）

这是快排发明者 Hoare 最初提出的版本

核心逻辑：

• 选取最最左边（left）的元素作为基准值（key）
• 让right指针先走，去找比key小的数
• left指针再向右走，找比key大的数
• 交换他们两个的值
• 重复该流程，直到他们相遇，最后将基准值与相遇点交换

// Hoare版本核心代码privatestaticintpartition(int[]array,intleft,intright){inti=left;intkey=array[left];// 选最左边做基准while(left<right){// 必须右边先走！找比 key 小的while(left<right&&array[right]>=key){right--;}// 左边后走，找比 key 大的while(left<right&&array[left]<=key){left++;}swap(array,left,right);}swap(array,left,i);// 基准值归位returnleft;}

疑惑点

疑问 1：为什么要限制 left < right？
Q： 外层循环已经有了 while(left < right)，为什么里面的小循环还要加这个判断？
A: 防止越界(IndexOutOfBounds)
eg：如果数组{1,2,3,4,5}这种情况下，基准值为1，right指针会一直找比1小的数，但是一直找不到，会一直减，由于没有left < right拦着，right会减到-1，直接报错

疑问 2：为什么必须取“等于” (>= 和 <=)？
Q： 我写成 array[right] > key ，不加 = 可以吗？
A：NO！等一下死循环就老实了
eg：假如数组是 {5, 5, 2…}，基准是 5
left指针指向 5，不满足 <5，停下，right指针指向 5，不满足 >5，停下，两人交换，数组还是 {5, 5…}
下一轮循环，他们又在原地停下，发呆，最后再次交换……陷入死循环 ……

疑问 3：为什么要“右边先走”？
Q： 我先移动左指针不行吗？
A：不可以！（当基准在左边时）

• 当到最后一步是 swap(array, left, i)，也就是把相遇点的数和基准值交换

• 基准值在最左边，所以我们希望交换到最左边的那个数，必须是比基准值小的

• 右边先走：right 会停在比基准小的地方。此时 left 撞上来，相遇点就是小的

• 左边先走：left 会停在比基准大的地方。此时 right 撞上来，相遇点就是大的。把大的换到最左边，排序就错了

总结：基准在左，右边先走；俩人停下，互相交换。

2.挖坑法

既然 Hoare 法还要考虑左右谁先走，还要考虑最后一步交换逻辑，那么主播主播，有没有更强势的写法？
当然有，那就是挖坑法

核心逻辑：

• 把基准值存入临时变量key，此时left 指针位置形成第一个坑
• right指针找小于key，找到了直接填到左边的坑里（right指针现在的位置变新坑)。
• left指针找大于key，找到了直接填到右边的坑里（left现在位置变新坑)
• 相遇时，把 key 填入最后的坑中

//挖坑法版本核心代码privatestaticintpartition(int[]array,intleft,intright){intkey=array[left];// 1. 挖坑while(left<right){// 2. 右边找小，填左坑while(left<right&&array[right]>=key){right--;}array[left]=array[right];// 3. 左边找大，填右坑while(left<right&&array[left]<=key){left++;}array[right]=array[left];}// 4. 填最后的坑array[left]=key;returnleft;}

总结：先挖基准，右填左，左填右，最后再把基准填上

3.前后指针法

这种方法逻辑稍微抽象一点，虽然代码看着短，但逻辑稍微绕一点，但是它的优势是不需要从右往左遍历，适合链表

核心逻辑：

• prev指向基准，cur指向下一个

• 当cur遇到比基准小的数时：
  prev向前扩一步
  交换prev和cur的值（把小的拉进圈子，把大的挤出去）

• 最后交换基准值和prev

// 前后指针法版本核心代码privatestaticintpartition3(int[]array,intleft,intright){intprev=left;intcur=left+1;//prev 指向 0 (基准值位置)，cur 指向 1 (下一个)。intkey=array[left];//只有当 cur 遇到比 key 小的数时，才需要处理while(cur<=right){// 核心判断：只在遇到“小的”时候处理// if (array[cur] < key && ++prev != cur)// 条件 A: array[cur] < key -> 找到了属于左边的数// 条件 B: ++prev != cur -> 这是一个优化。// 如果 prev 紧贴着 cur (中间没夹着大数)，比如开头全是小的，// 那 prev 往前走一步就撞上 cur 了，自己换自己没必要。// 只有当 prev 和 cur 之间有空隙（夹着大数）时，才需要真正的交换。// 下面的是简化版本if(array[cur]<key){prev++;if(prev!=cur){swap(array,cur,prev);}}//不管是不是比 key 小，cur 都要继续往后走，去检查下一个数cur++;}// 循环结束，prev 指向的是最后一个比 key 小的数// 把基准值(key)换到这里，让它居中swap(array,left,prev);returnprev;}

三、非递归实现 (Stack 版本)

如果数据量超级大，或者数组本身就有序，递归层数太深会导致StackOverflowError。这时候必须使用非递归写法

非递归的核心是：自己造一个栈，模拟系统递归的过程

核心思路：
手搓一个 Stack 来存任务

• 创建一个 Stack

• 把整个数组的 left 和 right 压入栈

• 循环弹栈 -> 调用partition来切分-> 得到基准 pivot

• 如果 pivot 左边还有元素，把左区间的范围压栈

• 如果 pivot 右边还有元素，把右区间的范围压栈

• 注意顺序：
  入栈如果是“先左后右”，出栈就是“先右后左”

importjava.util.Stack;publicstaticvoidquickSortNonRecursive(int[]array){Stack<Integer>stack=newStack<>();// 放入整个数组 (先放左，再放右)（放下标）stack.push(0);stack.push(array.length-1);while(!stack.isEmpty()){// 取出 (注意顺序：先出右，再出左)intright=stack.pop();intleft=stack.pop();// 调用之前的 partition 方法intpivot=partition(array,left,right);// 右边(如果元素 > 1个)，压栈if(pivot+1<right){stack.push(pivot+1);stack.push(right);}// 左边 (如果元素 > 1个).压栈if(left<pivot-1){stack.push(left);stack.push(pivot-1);}}}

四、总结