1.什么是快速排序算法
快速排序是对冒泡排序的一种改良版，通过一趟排序，把要排序的序列分割成两个部分，一部分的所有数据要比另一部分的数据都小，然后再根据这两部分的数据来进行快速排序。以此来达到整一个数据都变成了有序序列。
（1）快速排序基本思路
- 首先快速排序要选取一个基准值，以基准值为分割，把比该基准值小的放左边，基准值大的放右边。然后得出来的序列再进行快速排序。
- （2）快速排序的应用场景
- 快速排序的时间复杂度为O（nlogn），是目前基于比较的内部排序里被认为是最好的方法，当数据过大并且数据是杂乱无序的时候，适合用快速排序。
（3）快速排序的优缺点
- 优点：平均性能好O（nlogn）
- 缺点：不稳定，如果初始的序列或基本的序列是有序的时候，时间复杂度为O（n²）。
2.快速排序算法图解
- 第一趟排序：以初始数据的头元素作为基准值来进行分割，把比25小的作为一部分，比25大的又作为一部分。
- 第二趟排序：比25小的那一部分以开头的15作为基准值来拆分成两部分，比15小的为一部分（8,12,4,10），比15大的为一部分（20）。此外另一组是比25大的，以46为基准值，比46小为一部分，比46大为一部分。
- 第三趟排序：比15小的以开头的8作为基准值又开始进行分组，分为比8小和比8大这两部分。
- 最后合并出来的数据就是已经排序好了的
- 拆分原理讲解
- 1.先是right从右往左找，寻找比基准值小的数，找到了10。接着left指针开始从左往右找，寻找比基准值大的数，找到了31，这时10与31进行互换。
- 2.然后right继续从右往左找，找到了4。然后left开始从左往右找，找到了46，这时4与46的位置进行交换。
- 3.这时right继续从右往左找，找到了15。left也开始从左往右找，它也到了15的位置。说明整个数据已经遍历过一次了。然后就是基准值跟两个指针重合的位置进行交换。
- 基准值的选取
- 固定位置选取基准值：选取第一个或者是最后一个元素作为基准值
- 随机选取基准值：选取待排序里的任意一个数作为基准值
- 三数取中法：取第一个数与中间数和最后一个数来比较，哪一个在中间那就以谁作为基准值。如：‘10’，‘44’，‘2’，这三个数10在中间，取10。
3.快速排序算法编码实现
（1）整体代码实现
public class QuickSort { public static void main(String[] args) { int[] arr = {25,12,20,31,8,46,15,4,50,10}; System.out.println("排序前："); System.out.println(Arrays.toString(arr)); quickSort(arr,0,9); System.out.println("排序后："); System.out.println(Arrays.toString(arr)); } public static void quickSort(int[] arr,int leftIndex,int rightIndex){ //递归 如果左边的索引大于右边的索引，跳出循环，递归结束 if(leftIndex>rightIndex){ return; } int left = leftIndex; int right = rightIndex; //定义基准值 int key = arr[left]; //扫描左边跟右边的数字，只有当left<right的时候才会循环 while(left<right){ //右边 找到一个最小的基准值,从右指针向前开始找 while (right>left && arr[right]>=key){ right--; } //找到之后，交换值 arr[left] = arr[right]; //左边 找到大于基准值的数字，从左指针向后开始找 while(left<right && arr[left]<=key){ left++; } //找到之后，交换值 arr[right]=arr[left]; //执行到这步，left=right,基准值归位 arr[left]=key; //递归调用，对基准值左边的元素进行排序 quickSort(arr,leftIndex,left-1); //递归调用，对基准值右边的元素进行排序 quickSort(arr,right+1,rightIndex); } } }
（2）运行结果
