快速排序
1.简介：
快速排序是对冒泡排序的一种改进。它的最坏时间复杂度为O(n2)，最好时间复杂度为O(nlogn)，平均时间复杂度为O(nlogn)，它是不稳定排序。
基本思想：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
2.算法原理：
从数列中挑出一个元素，称为 “基准”；
重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区操作；
递归地把小于基准值元素的子数列和大于基准值元素的子数列排序。
结合动态图理解一下：
（图片来源：十大经典排序算法（动图演示））
3.代码实现：
public static void kuaiSu(int[] a,int low,int height){ int i = low,j = height; if(low < height){ int mark = a[low]; while (i < j) { while (a[j] > mark && i < j){ j--; } if(i < j) { a[i] = a[j]; i++; } while (a[i] < mark && i < j){ i++; } if(i < j) { a[j] = a[i]; j--; } } a[i] = mark; kuaiSu(a,low,i - 1); kuaiSu(a,i+1,height); } }
测试一波：
package sort; /** * @author yzh * @date 2019-07-15 20:36 */ public class KuaiSu { public static void kuaiSu(int[] a,int low,int height){ int i = low,j = height; if(low < height){ int mark = a[low]; while (i < j) { while (a[j] > mark && i < j){ j--; } if(i < j) { a[i] = a[j]; i++; } while (a[i] < mark && i < j){ i++; } if(i < j) { a[j] = a[i]; j--; } } a[i] = mark; kuaiSu(a,low,i - 1); kuaiSu(a,i+1,height); } } public static void main(String[] args) { int[] a = {4,-4,52,0,54,14,754}; kuaiSu(a,0,a.length-1); for(int i = 0;i < a.length;i++){ System.out.println(a[i]); } } }
测试结果：
4.优缺点：
- 优点：极快，数据移动少；
- 缺点：不稳定。
