最近做题，发现冒泡和选择排序的复杂度太大了，容易超时，于是就学习了快排
快排：简单地说就是找到一个基准数字m，数组中比m大的放在右边，比m小的放在左边，这样m的位置是正确的的。然后利用递归再分别对两边进行快排
下面我逐步讲解一下快排的思路：
1.假定对数组{6，1，7，5，3，11}进行快排
2.首先在这个序列中找一个数作为基准数，为了方便可以取第一个数6
3.进行初步快排之后，变成{5，1，3，6，7，11}
4.这是如何做到的呢，取6为基准
5.从数组最右向左边遍历找到一个比6小的数字，记为j
6.同理：遍历数组左边，找到比6大的数字，记为i
7.然后交换i和j所在位置的数字，然后继续检索
8.直到i= =j,表示本次检索已经结束，讲i与基准数字换位。此时基准数字已经找到自己的位置了
9.然后把数组根据基准数=左右分成两部分，利用递归再进行排序
就像：
原数组 ：6,1，7,5，3,11---------key：6
第一次交换：6，1,3，5,7，11------3和7进行交换
第二次交换：5，1,3，6,7，11-------此时i==j
那么如果第四个数字5换成8会怎么样？当初我就感觉如果这样还要再加一个判断，思考一下，问题会在最后揭晓
接下来先上代码：`
import java.sql.Array; import java.util.Arrays; public class test1 { public static void main(String[] args) { int [] arr= {6,1,8,7,5,2,3,11}; System.out.println(Arrays.toString(arr)); quickSort(arr,0,arr.length-1); System.out.println(Arrays.toString(arr)); } private static void quickSort(int[] arr, int left, int right) { if(left>=right) return;//如果边界相等，就直接结束循环了 int key=arr[left]; int i=left; int j=right; while(i<j) { while(i<j&&arr[j]>=key) {//遇到比key大的数字，向左检索 j--; } while(i<j&&arr[i]<=key) {//从左开始，遇到比key小的数字，向右检索 i++; } if(i<j) { int temp=arr[i]; arr[i]=arr[j]; arr[j]=temp; } } //此时i==j arr[left]=arr[i]; arr[i]=key; quickSort(arr, left, i-1); quickSort(arr, i+1, right); } }
如果把5换成8，那么程序在执行下面这个语句是while(i<j&&arr[j]<key) {//遇到比key大的数字，向左检索 j--; }
因为满足条件，会自动向左在移动一位。我当时查资料的时候就一直迷在这里，以为还要再加一个判断
