相比于冒泡排序的改进点：
在前面学过的冒泡排序中，由于扫描过程只对相邻的两个元素进行比较，因此在互换两个相邻元素时，只能消除一个逆序，如果能通过两个(不相邻的)元素的交换，消除待排序记录 中的多个逆序，则会大大加快排序的速度，快速排序方法中的一次交换可能消除多个逆序
文字描述：
a.每一轮排序选择一个基准点(pivot)进行分区：
1：让小于基准点的元素进入一个分区，大于基准点的元素进入另一个分区 2：当分区完成后，基准点元素的位置就是其最终位置
b.在子分区内重复以上过程，直至子分区元素个数少于等于1，这体现的是分而治之的思想(divide-and-conquer)
快速排序的实现方式:
单边循环快排(lomuto洛穆托分区方案）
1：选择最右元素作为基准点元素 2：j指针负责找到比基准点小的元素，一旦找到则与i进行交换 3：i指针维护小于基准点元素的边界，也是每次交换的目标索引 4：最后基准点与i交换，i即为分区位置
一次快速排序代码的实现如下：
package bin_find; import java.util.Arrays; public class quick_sort { public static void main(String[] args) { int[] a={5,3,7,2,1,9,8,4}; quick(a,0,a.length-1); } public static int quick(int []a,int l,int h){ int pv=a[h];//基准点元素 //i相当于是一个分割线，位于它左边的所有元素都是小于基准元素的，位于它右边的元素都是大于基准元素的 int i=l; //j变量根据索引从左往右一旦找到比当前基准元素小的元素，则与索引值为i的元素进行交换 for(int j=l;j<h;j++){ if(a[j]<pv){ swap(a,i,j); //交换完成，i++ --->下一个需要排序的元素 i++; } } //基准点和i的元素进行交换,一轮分区完成 swap(a,h,i); System.out.println(Arrays.toString(a)); return 0; } public static void swap(int arr[],int i,int j){ int t=arr[i]; arr[i]=arr[j]; arr[j]=t; } }
输出如下：
[3, 2, 1, 4, 7, 9, 8, 5]
一轮排序的步骤如下：
一轮排序图解如下所示：
pv：表示基准点元素
第一次：由于5比4大，所以不发生交换,j继续向后移动寻找比4小的元素
第二次:
j移动到元素3的位置，3比4小，发生交换，i++,结果如下所示：
第3次：当j移动到元素2的位置，2比4小，所以发生交换，且i++
j再移动直到找到1，元素1小于4，将i和j指向的元素进行交换，如下所示：
此时j已经移动到了基准点前一个位置：
最后只需要将i和pv指向的元素进行交换，则一轮快排结束
通过一轮快排结束的结果我们会发现，以i指向的元素作为基准，位于它左边的元素都是小于它的，位于它右边的元素都是大于它的
完整快速排序代码如下：
package bin_find; import java.util.Arrays; public class quick_sort { public static void main(String[] args) { int[] a={5,3,7,2,1,9,8,4}; recurrence(a,0,a.length-1); } //该方法的作用是：递归实现分区排序直至整个数组有序，通过每轮排序返回的下标值进而确定这次排序的范围 public static void recurrence(int []a,int l,int h){ if(l>=h){//递归结束的条件:当区间只有一个元素或者没有元素时，有等号的原因是由于当l恰好等于返回的索引值，此时p再减1就使得h<l return; } int p=quick(a,l,h);//基准点的索引值 recurrence(a,l,p-1);//左边分区范围：第一个元素~基准元素的前一个元素 recurrence(a,p+1,h);//右边分区范围：基准元素的下一个元素~最后一个元素 } public static int quick(int []a,int l,int h){ int pv=a[h]; int i=l; for(int j=l;j<h;j++){ if(a[j]<pv){ //优化1： if(i!=j) {//当j找到小于基准点的值和i指向的元素不是同一个元素时，发生交换，这样能够减少不必要的交换次数 swap(a, i, j); } i++; } } //优化2： if(i!=h){//当基准点元素和i指向的元素不是同一个元素时，发生交换，这样能够减少不必要的交换次数 swap(a,h,i); } System.out.println(Arrays.toString(a)); return i; } public static void swap(int arr[],int i,int j){ int t=arr[i]; arr[i]=arr[j]; arr[j]=t; } }
输出：
[3, 2, 1, 4, 7, 9, 8, 5] [1, 2, 3, 4, 7, 9, 8, 5] [1, 2, 3, 4, 7, 9, 8, 5] [1, 2, 3, 4, 5, 9, 8, 7] [1, 2, 3, 4, 5, 7, 8, 9] [1, 2, 3, 4, 5, 7, 8, 9]
双边循环快排(并不完全等价于hoare霍尔分区方案)
1：选择最左元素作为基准点元素 2：j指针负责从右向左找比基准点小的元素，i指针负责从左向右找比基准点大的元素，一旦找到二者交换，直至i,j相交 3:最后基准点与i(此时i与j相等)交换，i即为分区位置
一轮双边循环快排图解如下：
j此时指向的元素为4比5小，因此j不需要移动了，此时需要等待i移动直至找到大于基准元素的元素：
此时i找到了大于基准元素的元素，i和j指向的元素进行交换：
j移动找到1，小于基准元素，等待i找到大于基准元素的元素9时：
二者发生交换：
当下次再开始寻找时，j寻找小于基准元素的值，找到元素1，i和j相等，如下所示：
最后只需要交换基准元素和i，j指向的同一个元素即可，表示本轮排序结束：
代码如下所示：
package bin_find; import java.util.Arrays; public class quick_sort { public static void main(String[] args) { int[] a={5,3,7,2,9,8,1,4}; recurrence(a,0,a.length-1); } public static void recurrence(int []a,int l,int h){ if(l>=h){//递归结束的条件:当区间只有一个元素或者没有元素时，有等号的原因是由于当l恰好等于返回的索引值，此时p再减1就使得h<l return; } int p=quick(a,l,h);//基准点的索引值 recurrence(a,l,p-1);//左边分区范围：第一个元素~基准元素的前一个元素 recurrence(a,p+1,h);//右边分区范围：基准元素的下一个元素~最后一个元素 } //该方法的作用是：递归实现分区排序直至整个数组有序，通过每轮排序返回的下标值进而确定这次排序的范围 public static int quick(int []a,int l,int h){ int pv=a[l]; int i=l; int j=h; while(i<j){ while (i<j&&a[j]>pv){ j--; } while(i<j&&a[i]<=pv){ i++; } swap(a,i,j); } swap(a,l,i);//i和j都可以，因为他们指向同一个元素 System.out.println(Arrays.toString(a)); return i; } public static void swap(int arr[],int i,int j){ int t=arr[i]; arr[i]=arr[j]; arr[j]=t; } }
输出：
[1, 3, 4, 2, 5, 8, 9, 7] [1, 3, 4, 2, 5, 8, 9, 7] [1, 2, 3, 4, 5, 8, 9, 7] [1, 2, 3, 4, 5, 7, 8, 9]
针对上述的算法，有以下三个地方需要注意：
细节一：
答案：不可以发生颠倒
在开始进行排序的过程中，两个while循环位置发生颠倒看似没有什么问题，但经过几轮之后，最终会出现下述情况导致整个逻辑混乱
细节二：
答案：不可以
原因如下：假设我们现在的条件为a[i]<pv，j开始找比基准点小的元素，找到4后，i开始找比基准点大的元素，此a[i]<pv不满足，i++不会被执行，i依然指向基准点元素，第二个while循环退出执行swap函数，导致基准点元素被调换，因此加等号条件的作用是，为了在最开始跳过基准点元素，避免不必要的逻辑错误
细节三：
答案：不可以
原因如下：
假设此时，我们将内层的两个循环中的i<j条件同时去除，那么就会发生如下所示，当j从右往左找到了小于基准点的元素停下，i从基准点出发寻找大于基准点的元素，当i++到元素3的位置，逻辑上应为排序完成，但由于没有i<j的条件，因此i会++到元素6的位置，最终将元素6换到了左侧，这显然已经违背正确的结果了
双边循环需要注意的点：
1：基准点在左边并且要先j后i 2：while(i<j&&a[j]>pv)j-- 3:while(i<j&&a[i]<=pv)i++
快速排序的特点：
平均时间复杂度是O(nlog2^n),最坏时间复杂度是O(n ^n)
数据量较大时，优势非常明显
属于不稳定的排序
举例;
3,3,2
采用单边循环快排，2作为基准元素，起初i,j都指向3，从左往右找比2小的元素，当找到3退出循环，由于i指向3，基准元素为2，二者并不相等，因此发生交换，这就导致3和3的前后关系发生变化，因此快速排序属于不稳定排序
