文章目录

一、快速排序介绍二、图解三、代码分析3.1交换函数（1）一直交换（2）左右交换（3）填数（4）三种方法简析 3.2递归实现快排 四、完整代码

一、快速排序介绍

1.快速排序是对冒泡排序的改进。冒泡排序每次交换只能使原序列的逆序数减一（相邻元素的交换），而快速排序可以进行不相邻元素的交换，逆序数至少减少1。（当排序序列逆序数为0时，排序就完成了）

百度百科的逆序数解释：

2.基本思想（以升序排序为例）：

选定数组中的一个数作为参照数，将比其小的数放在其左边，大的放在其右边。将其左边和右边的数看成新的数组，分别进行第一步的过程，之后循环进行，直到新的数组中只剩一个元素为止。

二、图解

下图中只用看思想，排序过程中实际数的顺序不一定是这样的。这里选每个数组中第一个数当参照数，实际参照数可以有多种选择方案。

三、代码分析

3.1交换函数

快排中最重要就是将比参照数小的放在其左边，大的放在其右边的方法。这里我看了一些文章，结合自己的思考，总结了三个方法。

（1）一直交换

这里定义两个指针分别指向数组的头与尾。

a. 判断尾指针所在元素是否小于参照数（即头指针指向的数），不小于，尾指针就一直向左移，直到找到小于参照数的数或到达头指针（两指针相遇，循环就结束），将头尾指针元素交换。

b.接着判断头指针所在元素是否大于参照数（即尾指针指向的数），不大于，头指针就一直向右移，直到找到大于参照数的数或到达尾指针（两指针相遇，循环就结束），将头尾指针元素交换。

c.反复进行步骤ab，直到头尾指针相遇。

**思考：**这样可以保证头指针前的都是小于参照数的，尾指针后的都是大于参照数的。

图解： 这里以arr={5, 4, 8, 2, 7, 1}为例 尾指针小于5，交换。（一定要尾指针先判断，因为头指针记录着参照数。） 头指针开始判断： 找到，交换。 尾指针开始判断。 找到，交换。 头指针开始判断。 两指针相遇，结束。 代码：

public static int change(int[] arr, int left, int right) { int l = left;//头指针 int r = right;//尾指针 while(l < r){ while(arr[r] >= arr[l] && l < r){ r--; } int temp = arr[r];//交换 arr[r] = arr[l]; arr[l] = temp; while(arr[l] <= arr[r] && l < r){ l++; } temp = arr[r];//交换 arr[r] = arr[l]; arr[l] = temp; } return r; }

（2）左右交换

定义两个指针分别指向数组的头与尾。

a. 判断尾指针所在元素是否小于参照数（即头指针指向的数），不小于，尾指针就一直向左移，直到找到小于参照数的数或到达头指针（两指针相遇，循环就结束），这里先不进行交换。

b.接着判断头指针所在元素是否大于参照数（即尾指针指向的数），不大于，头指针就一直向右移，直到找到大于参照数的数或到达尾指针（两指针相遇，循环就结束），这时进行交换。

c.反复进行步骤ab，直到头尾指针相遇，将该处元素与参照数互换。

图解： 这里还以arr={5, 4, 8, 2, 7, 1}为例 右边判断找到，左边开始判断。 两边都找到，交换。 右边开始找。 找到，左边开始找。 两指针相遇，此处元素与参照数互换。（这里可以看出一定要右边指针先判断，否则两指针相遇时所指向的元素大于参照数） 完成。

代码：

public static int change2(int[] arr, int left, int right){ int l = left;//头指针 int r = right;//尾指针 while(l < r){ while(arr[r] >= arr[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; } }