快速排序

目录

什么是快速排序：

图解：

递归法：

 方法一（Hoare法）：

  代码实现：

        思路分析：

       方法二（挖坑法）：

        代码实现：

        思路分析：

        非递归法：

        图解：

        代码实现：

        思路分析：

        快速排序是不稳定的。

---

什么是快速排序：

        任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。

图解：

        

         假设 0 下标的数字 3 作为我们的基准值，先看上图的left 和 right ，他们一开始是在start 和 end 的位置。

        在走的过程中，right 先走，直到遇到比 3 小的数字停下来，再到 left 走，直到遇到比 3 大的数字停下来；然后交换 此时 left 下标 和 right 下标 的数字，然后不断重复此过程，直到left 与 right 相遇停止；再把最后left 和 right 相遇的 下标位置 与 我们设定的基准值 3 交换；这样就保证了此时的left 位置的下标的左边都是比他小的，右边都是比他大的。也可以说此时的left 下标的数据已经有序了。（用 par 记录left 和 right相遇的位置）

        然后，再看此图：

        

         因为使用了 par 记录了 left 和 righjt 相遇的的位置，那么下次划分 一段数据左边则 使用 start 和 par - 1 作为一段新的数据的 left 和 right ，右边 使用 par + 1 和 end 作为一段新的数据的 left 和 right ，不断细分排序重复下去，直到start 与 end 相遇停止划分；看上图绿色椭圆圈出来的start ，那是在 1 下标右边走划分出来的一段，此时start 大于了 end ，也算一种停止划分条件。

        所以，停止划分的条件是 start >= end

递归法：

 方法一（Hoare法）：

  代码实现：

public static void quickSortHoare(int[] arr) {quick(arr,0,arr.length - 1);}private static void quick(int[] arr, int start, int end) {if(start >= end) {return;}int par = parrtion(arr,start,end);//往左走quick(arr,start,par - 1);//往右走quick(arr,par + 1,end);}private static int parrtion(int[] arr, int left, int right) {int i = left;int ret = arr[left];while(left < right) {while(left < right && arr[right] >= ret) {right--;}while(left < right && arr[left] <= ret) {left++;}//交换swap(arr,left,right);}//交换swap(arr,i,left);return left;}private static void swap(int[] arr,int i,int j) {int tmp = arr[i];arr[i] = arr[j];arr[j] = tmp;}

        思路分析：

        结合上面我们分析的图解，有个要注意的是 parrtion 方法里 的 left < right && arr[right] >= ret 和 left < right && arr[left] <= ret 这两个的循环条件，前提都要加上 left < right ，因为如果 对于一段已经有序的数据，假设我们使用对一个最小的数据作为基准值，第一个 arr[right] >= ret 循环 判断条件会一直让 right --，如果没有left < right 作为前提条件，会导致 right 越界。

        

       方法二（挖坑法）：

        代码实现：

 public static void quickSort2(int[] arr) {quick(arr,0,arr.length - 1);}private static void quick2(int[] arr, int start, int end) {if(start >= end) {return;}int par = parrtion2(arr,start,end);//往左走quick2(arr,start,par - 1);//往右走quick2(arr,par + 1,end);}private static int parrtion2(int[] arr, int left, int right) {int ret = arr[left];while(left < right) {while(left < right && arr[right] >= ret) {right--;}arr[left] = arr[right];while(left < right && arr[left] <= ret) {left++;}arr[right] = arr[left];}arr[left] = ret;return left;}private static void swap(int[] arr,int i,int j) {int tmp = arr[i];arr[i] = arr[j];arr[j] = tmp;}

        思路分析：

        挖坑法 与 Hoare 法思路很相像，不同的是；

        挖坑法 是把 right 找到比 基准值 小的时候，把此时 的 right 下标的值给到 left 下标；left 找到比 基准值 大的时候，把此时 的 left 下标的值给到 right 下标。

        最后，由于一开始使用了 ret 存储了基准值，所以当 left 与 right 相遇时把 ret 给到 left 下标的位置。

        

        非递归法：

        图解：

         

        快速排序非递归的方法我们借助了一个栈，用来存放数据的下标；

        先把一段数据的 left 给到 栈里，再把 right 给到 栈里，然后排完一段序后，得到 par ，再把一段新的数据的 left 和 right 给到 栈里。

        要注意，当：

        

         这是分出来的一段数据，当par右边只剩一个元素时，那么右边剩下的一个元素是有序的，par 左边同理。

        代码实现：

public static void quickSortNor(int[] arr) {int left = 0;int right = arr.length - 1;int par = parrtion3(arr,left,right);Stack<Integer> stack = new Stack<>();//左边有两个元素及以上if(left + 1 < par) {stack.push(left);stack.push(par - 1);}//右边有两个元素及以上if(par < right - 1) {stack.push(par + 1);stack.push(right);}while(!stack.isEmpty()) {right = stack.pop();left = stack.pop();par = parrtion3(arr,left,right);//左边有两个元素及以上if(left + 1 < par) {stack.push(left);stack.push(par - 1);}//右边有两个元素及以上if(par < right - 1) {stack.push(par + 1);stack.push(right);}}}private static int parrtion3(int[] arr, int left, int right) {int ret = arr[left];while(left < right) {while(left < right && arr[right] >= ret) {right--;}arr[left] = arr[right];while(left < right && arr[left] <= ret) {left++;}arr[right] = arr[left];}arr[left] = ret;return left;}

        思路分析：

        结合上面的图解，一开始在循环外，我们排了一次序，得到了 par ，再把对应的 left 和 right 给到栈里。

        当栈不为空时，栈弹出的第一个元素作为相应一段数据 right ，下一个是对应的 left ，原因是我们放入栈时是先 left 再 right；再对其排序后得到新的 par ，再结合图解分析。直到栈为空时结束。

        

        快速排序是不稳定的。