目录

快速排序

排序原理

切分原理

代码展示

快速排序和归并排序的区别

快速排序时间复杂度分析

      大家好，我是Nick，这篇文章讲的是快速排序，有点类似于冒泡排序的升级版，有有点像归并排序，但不全是哦！跟着Nick一起来看看吧。

      

      有一定编程基础的家人们欢迎在评论区指点江山~ （萌新请绕道，建议收藏,后期看哦~）

快速排序

      快速排序是对冒泡排序的一种改进。它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

　　　   

需求：

排序前:{6,1,2,7,9,3,4,5,8}

排序后:{1,2,3,4,5,6,7,8,9}

   

排序原理

• 首先设定一个分界值，通过该分界值将数组分成左右两部分;
• 将大于或等于分界值的数据放到到数组右边，小于分界值的数据放到数组的左边。此时左边部分中各元素都小于或等于分界值，而右边部分中各元素都大于或等于分界值;
• 然后，左边和右边的数据可以独立排序。对于左侧的数组数据，又可以取一个分界值，将该部分数据分成左右两部分，同样在左边放置较小值，右边放置较大值。右侧的数组数据也可以做类似处理。
• 重复上述过程，可以看出，这是一个递归定义。通过递归将左侧部分排好序后，再递归排好右侧部分的顺序。当左侧和右侧两个部分的数据排完序后，整个数组的排序也就完成了。

      

    

切分原理

把一个数组切分成两个子数组的基本思想︰

1. 找一个基准值，用两个指针分别指向数组的头部和尾部;
2. 先从尾部向头部开始搜索一个比基准值小的元素，搜索到即停止，
3. 并记录指针的位置;
4. 再从头部向尾部开始搜索一个比基准值大的元素，搜索到即停止，并记录指针的位置;
5. 交换当前左边指针位置和右边指针位置的元素;
6. 重复2,3,4步骤，直到左边指针的值大于右边指针的值停止。

     

代码展示

Quick方法类

public class Quick {    /*比较v元素是否小于w元素*/    private static boolean less(Comparable v,Comparable w){ return v.compareTo(w)<0;    }    /*数组元素i和j交换位置*/    private static void exch(Comparable[] a,int i,int j){ Comparable temp = a[i]; a[i] = a[j]; a[j] = temp;    }    /*对数组内的元素进行排序*/    public static void sort(Comparable[] a){ //这两个值就是a数组中所有元素 int lo = 0; int hi = a.length-1; sort(a,lo,hi);}    /*对数组a中从索引lo到索引hi之间的元素进行排序*/    private static void sort(Comparable[] a,int lo,int hi) { //安全性校验 if(hi=right,如果是，则证明元素扫描完毕，结束循环，如果不是，则交换     if(left>=right){  break;     }else{  exch(a,left,right);     } } //partion函数中最后的交换，以及返回的分界索引，必须采用right，采用left是错误的，原因是外部while循环结束时，可能出现left比right大1的情况，示例数组为{1， 3， 2} //交换分界值 exch(a,lo,right); return right;    }}

测试类

import 快速排序.service.Quick;import java.util.Arrays;public class QuickTest {    public static void main(String[] args) { Integer[] arr ={8,4,5,7,1,3,6,3}; Quick.sort(arr); System.out.println(Arrays.toString(arr));    }}

      

快速排序和归并排序的区别

      快速排序是另外一种分治的排序算法，它将一个数组分成两个子数组，将两部分独立的排序。

    

      快速排序和归并排序是互补的∶归并排序将数组分成两个子数组分别排序，并将有序的子数组归并从而将整个数组排序，而快速排序的方式则是当两个数组都有序时，整个数组自然就有序了。

  

      在归并排序中，一个数组被等分为两半，归并调用发生在处理整个数组之前，在快速排序中，切分数组的位置取决于数组的内容，递归调用发斯在处理整个数组之后。

     

快速排序时间复杂度分析

      快速排序的一次切分从两头开始交替搜索，直到left和right重合，因此，一次切分算法的时间复杂度为O(n)但整个快速排序的时间复杂度和切分的次数相关。

     

      最优情况∶每一次切分选择的基准数字刚好将当前序列等分。

        

     

      如果我们把数组的切分看做是一个树，那么上图就是它的最优情况的图示，共切分了logn次，所以，最优情况下快速排序的时间复杂度为O(nlogn); 最坏情况:每一次切分选择的基准数字是当前序列中最大数或者最小数，这使得每次切分都会有一个子组，那么总共就得切分n次，所以，最坏情况下，快速排序的时间复杂度为O(n^2);

          

       

      平均情况:每一次切分选择的基准数字不是最大值和最小值，也不是中值，这种情况我们也可以用数学归纳法证明，快速排序的时间复杂度为O(nlogn),由于数学归纳法有很多数学相关的知识，容易使我们混乱，所以这里就不对平均情况的时间复杂度做证明了。

     

---

 到这里快速排序就告一段落啦~

数据结构需要每天练习，

相信在不断的努力下，

每个人都有质变的进步！

我们下一篇再见！

​