❤️全面图解快速排序，详细图文并茂解析！❤️

写在前面：

大家好，我是时光。

思维导图：

1，快速排序概念

通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。主要采用分治法和挖坑填数等方法，分治法就是大问题分解成各个小问题，堆小问题求解，使得大问题得以解决。

2，算法思路

我们先搞清楚这个堆排序思想，先把逻辑搞清楚，不着急写代码。

我们首先有一个无序数组，比方说

int[] arr={ 
   4,2,8,0,5,7,1,3,9}; 

2.1，第一步，取基准数

基准数（枢轴），取数组的第一个元素，此时基准数：arr[0]=4

并定义两个变量i和j分别指向无序数组的第一个元素start和最后一个元素end。

//起始 int i=start; int j=end; //获取基准数 int temp=arr[start]; 

2.2，第二步，分区过程

分区过程，将比基准数大的数全放到它的右边，比基准数小的或者相等的数全放到它的左边。

我们首先把第一个元素arr[0]=4定义为基准元素，此时数组第一个位置就是坑，那么我们要从数组的右边向左开始查找小于基准数的元素，并与坑互换位置。

while(i<j){ 
    //从右向左去找比基准数小的 while(i<j&&arr[j]>=temp){ 
    j--; } //判断相等，填坑 if(i<j){ 
    arr[i]=arr[j]; i++; } } 

换好位置之后，现在转换，从数组的左边向右边查找比基准数大的元素：

while(i<j){ 
    //从右向左去找比基准数小的 while(i<j&&arr[j]>=temp){ 
    j--; } //判断相等，填坑 if(i<j){ 
    arr[i]=arr[j]; i++; } //从左向右去找比基准数大的 while(i<j&&arr[i]<temp){ 
    i++; } //判断相等，填坑 if(i<j){ 
    arr[j]=arr[i]; j--; } } 

换好位置之后，现在又重新开始从数组右边向左边开始查找，比基准数小的元素：

不断重复此类操作，直到分成左右两个分区，再把基准数填入坑中，这样第一趟排序完成。如下：

//把基准数放到i=j的位置 arr[i]=temp; 

2.3，第三步，对两个区间重复进行分区操作

这里，我们对分好的两个区间重复进行上述分区操作，直到每个区间只有一个元素为止。

重复进行以上操作，直到左右两边分区都是有序排列，整个排序过程也就完成了：

//对左半边部分进行快排 QuickSort(arr,start,i-1); //对右半边部分进行快排 QuickSort(arr,i+1,end); 

3，完整代码

import java.util.Arrays; public class Quick_Sort { 
    public static void main(String[] args) { 
    int[] arr=new int[]{ 
   4,2,8,0,5,7,1,3,9}; System.out.println(Arrays.toString(QuickSort(arr,0,arr.length-1))); } public static int[] QuickSort(int[] arr,int start,int end){ 
    //起始 int i=start; int j=end; //获取基准数 int temp=arr[start]; //i 
    
    if 
    (i 
    <j 
    ) 
    { 
      
    while 
    (i 
    <j 
    ) 
    { 
      
    //从右向左去找比基准数小的 
    while 
    (i 
    <j 
    &&arr 
    [j 
    ] 
    >=temp 
    ) 
    { 
      j 
    -- 
    ; 
    } 
    //判断相等，填坑 
    if 
    (i 
    <j 
    ) 
    { 
      arr 
    [i 
    ] 
    =arr 
    [j 
    ] 
    ; i 
    ++ 
    ; 
    } 
    //从左向右去找比基准数大的 
    while 
    (i 
    <j 
    &&arr 
    [i 
    ] 
    <temp 
    ) 
    { 
      i 
    ++ 
    ; 
    } 
    //判断相等，填坑 
    if 
    (i 
    <j 
    ) 
    { 
      arr 
    [j 
    ] 
    =arr 
    [i 
    ] 
    ; j 
    -- 
    ; 
    } 
    } 
    //把基准数放到i=j的位置 arr 
    [i 
    ] 
    =temp 
    ; 
    //对左半边部分进行快排 
    QuickSort 
    (arr 
    ,start 
    ,i 
    - 
    1 
    ) 
    ; 
    //对右半边部分进行快排 
    QuickSort 
    (arr 
    ,i 
    + 
    1 
    ,end 
    ) 
    ; 
    } 
    return arr 
    ; 
    } 
    } 
   

4，算法分析

4.1，时间复杂度

快速排序最坏时间复杂度是O(n^2)，最好的时间复杂度为O(nlogn)，从而平均时间复杂度最后算出来也是O(nlogn)。

4.2，空间复杂度

空间复杂度是O(1)，因为没有用到额外开辟的集合空间。

4.3，算法稳定性

快速排序是不稳定的排序算法。因为我们无法保证相等的数据按顺序被扫描到和按顺序存放。

最坏时间复杂度是O(n^2)，最好的时间复杂度为O(nlogn)，从而平均时间复杂度最后算出来也是O(nlogn)。

4.2，空间复杂度

空间复杂度是O(1)，因为没有用到额外开辟的集合空间。

4.3，算法稳定性

快速排序是不稳定的排序算法。因为我们无法保证相等的数据按顺序被扫描到和按顺序存放。

5，其他排序算法

6，基本数据结构