文章目录一、快速排序介绍二、图解三、代码分析3.1交换函数(1)一直交换)左右交换)3)填充数)4)三种方法简化3.2递归实现快速排序四、完整代码
一.快速排序介绍
1.快速排序是对鼓泡进行排序的改进。 气泡排序可以在每次交换时将原始数组的倒数减少1 (相邻元素的交换)，但快速排序可以进行不相邻元素的交换，倒数至少可以减少1。 (如果排序顺序的逆序数为0，则排序完成。)
百度百科逆序解读： http://www.Sina.com/. http://www.Sina.com/(按升序排序示例) :
选择数组中的一个数作为引用数，将小于该数的数置于左侧，将较大的数置于右侧。 将其左边和右边的数量视为新的数组，分别进行第一步的过程，然后循环直到新数组中只剩下一个元素。 二、图解下图只看思想，排序中实际数量的顺序不一定。 在此为每个数组选择2。 实际引用数有几种选择。
三、代码分析3.1交换函数快列中最重要的是小于引用数的向左，大的向右的方法。 在这里看了几篇文章，结合自己的思考，总结了三种方法。
(1)一直交换这里定义的2个指针分别指向数组的开头和末尾。
a .确定末尾指针所在的元素是否小于引用数(即，头部指针所指的数)，如果不小于，则将末尾指针向左移动，直到找到小于引用数的数或头部指针，如果头部指针与头部指针相遇
b .然后，判断头指针所在的元素是否大于引用数(末尾指针所指的数)，如果不大于，则将头指针向右移动，直到找到大于引用数的数或到达末尾指针(两个指针相遇，循环结束)
c .重复步骤ab，直到头尾指针相遇。
*思考： **这确保头指针前面的都小于引用数，而末端指针后面的都大于引用数。
基本思想
在此，以arr={5、4、8、2、7、1}为例
尾指针小于5，要更换。 (因为头指针记录了参照数，所以请务必先用尾指针判断。 ）
头部指针开始判断：
找到，交换。
尾巴指针开始判断。
找到，交换。
头针开始判断。
两针相遇，结束。第一个数当参照数
publicstaticintchange(int[]arr，int left，int right ) ) int left； //头指针int r=right； //末尾指针while(LR ) ) while ) arr[R]=arr[L]LR ) ({ r--； } int temp=arr[r]； arr[r]=arr[l]； arr[l]=temp； wile(arr(L )=arr ) LR )； } temp=arr[r]； arr[r]=arr[l]； arr[l]=temp； }返回r； )2)左右调换定义两个指针分别指向数组的开头和结尾。
a .确定末尾指针是否小于参考数(即，头部指针所指的数)，否则末尾指针左移，直到找到小于参考数的数或头部指针(两个指针相遇，循环结束)
b .接着，判断头指针的一个元素是否大于参考数(即末尾指针所指的数)，如果不大于，则使头指针向右移动，直到发现了大于参考数的数目或者到达末尾指针(两个指针相遇，循环结束)
c .重复步骤ab，直到头尾指针对准，将那里的元素与引用数进行交换。
图解：
在此，以arr={5、4、8、2、7、1}为例
找到右边的判断，开始左边的判断。
找到两者，交换。
从右边开始找。
找到，从左边开始找。
两个指针相遇，元素和引用数在此互换。 (在这里，你可以看到右边的指针必须先判断。 否则，两个指针相遇时指向的元素将大于引用数。)
完成。
代码：
publicstaticintchange2(int [ ] arr，int left，intright({intL=left； //头指针int r=right； //末尾指针while(LR ) ) while ) arr(R )=A
rr[left] && l < r){//尾指针判断 r--; } while(arr[l] <= arr[left] && l < r){//头指针判断 l++; } int temp = arr[r];//交换 arr[r] = arr[l]; arr[l] = temp; } int temp = arr[left];//与操作数的交换 arr[left] = arr[l]; arr[l] = temp; return l; } （3）填数定义两个指针分别指向数组的头与尾。用临时变量将参照数存储起来。
a. 判断尾指针所在元素是否小于参照数（即头指针指向的数），不小于，尾指针就一直向左移，直到找到小于参照数的数或到达头指针（两指针相遇，循环就结束），用尾指针的元素将头指针的元素覆盖。
b.接着判断头指针所在元素是否大于参照数（即尾指针指向的数），不大于，头指针就一直向右移，直到找到大于参照数的数或到达尾指针（两指针相遇，循环就结束），用头指针的元素将尾指针的元素覆盖。
c.反复进行步骤ab，直到头尾指针相遇，用参照数将该处元素覆盖。
图解：
这里还以arr={5, 4, 8, 2, 7, 1}为例
将参照数存储，右边先动，找到，覆盖。
左边开始找。
找到，覆盖。
右边开始找。
找到，覆盖。
左边开始找。
两指针相遇，操作数进行覆盖。
完成。
代码：
public static int change3(int[] arr, int left, int right){ int l =left;//左指针 int r = right;//右指针 int temp = arr[left];//存储参照数 while(l < r){ while(temp <= arr[r] && l < r){//左边找 r--; } arr[l] = arr[r];//覆盖 while(temp >= arr[l] && l < r){//右边找 l++; } arr[r] = arr[l];//覆盖 } arr[r] = temp;//覆盖 return r; } （4）三种方法简析看代码量与实际操作数量，第三种效果最好，第一种最差。
3.2递归实现快排代码:
public static void quickSort(int[] arr, int left, int right){ if(right <= left){ return; } int r = change3(arr,left,right); quickSort(arr,left,r-1); quickSort(arr,r+1,right); } 四、完整代码 public class QuickSort { public static void main(String[] args) { int arr[] = {4,5,65,20,855,87,12,8,0,6,54,879,32,45,321,65,58,654,23,8,15}; quickSort(arr,0,arr.length-1); System.out.println(Arrays.toString(arr)); } public static void quickSort(int[] arr, int left, int right){ if(right <= left){ return; } int r = change3(arr,left,right); quickSort(arr,left,r-1); quickSort(arr,r+1,right); } public static int change3(int[] arr, int left, int right){ int l =left;//左指针 int r = right;//右指针 int temp = arr[left];//存储参照数 while(l < r){ while(temp <= arr[r] && l < r){ r--; } arr[l] = arr[r]; while(temp >= arr[l] && l < r){ l++; } arr[r] = arr[l]; } arr[r] = temp; return r; }}