目录
快速排序的思想
代码实现
思路
代码
快速排序的特点
快速排序的思想
快速排序和冒泡排序一样，是一种交换排序。快速排序的核心思想也是分治，分而治之。给定一个数组，先选定一个元素作为枢轴，然后将大于枢轴的放在右边，小于枢轴的放在左边，然后再对左右两边的元素进行排序。
代码实现
思路
根据上面的分析，我们发现还是要用到递归。那先定义出口，当什么时候不需要继续递归了？当要排序的范围只有一个元素时，就可以return了。
拿到数组后，如果数组长度大于一个元素，那我们首先把第一个元素作为枢轴，然后就是将大于枢轴的放在右边，小于枢轴的放在左边 说起来轻松，具体是如何实现的呢。这里我们采取的方法比较巧妙，我们应用了双指针。L=0,R=length-1,我们把枢轴元素临时存储在temp中，那个数组的第一个位置(即L)就空了R从后往前找一个比temp小的元素，将其放在L所指位置，L++，此时R所指就空了，这个时候我们再从L往后找一个比temp大的元素，将其放在R所指位置，R--，循环进行，直至L和R相遇，即空白位置左边都比temp小，右边都比temp大，我们将temp放在L或R所指即可。（由于是我自己组织的语言，可能有表述不清楚的地方，如果大家不是非常理解，可以看一下
青岛大学数据结构王卓老师的讲解，很透彻。课程放这里了，大家有需要自行观看
代码
package algorithm.sort;public class QuickSort {public static void main(String[] args) {int[] nums = new int[]{2,4,6,83,4,62,2,1};qucikSort(nums,0,nums.length-1);for (int i = 0; i < nums.length; i++) {System.out.print(nums[i]+" ");}}//快速排序public static void qucikSort(int[] nums,int left, int right) {//判断排序长短，一定是小于等于，不然会死循环if(right<=left){return;}//找枢轴，划分左右两边int temp = nums[left];int i = left,j=right;while(i<j){//从后往前找一个比枢轴小的while(nums[j]>=temp && i<j)j--;//将其放在L所指位置if(i<j)nums[i++]=nums[j];//必须加if判断，不然i=j时也会执行了，然而i=j是要跳出来的，所以不要执行//从前往后找一个比枢轴大的while(nums[i]<=temp && i<j)i++;将其放在R所指位置if(i<j)nums[j--]=nums[i];}//将temp放在枢轴的位置上nums[i]=temp;//左右两边继续排序qucikSort(nums,left,i-1);qucikSort(nums,i+1,right);}
}
快速排序的特点
1. 不稳定的排序
2. 时间复杂度为O(nlogn)，最差情况，即数组本身有序时，退化为冒泡排序，复杂度为O()
