经典算法之快速排序（QuickSort）

​

活动地址：CSDN21天学习挑战赛

目录

快速排序

   通过一趟排序将待排元素分成独立的两部分，其中一部分为比基准数小的元素，另一部分则是比基准数大的元素。然后对这两部分元素再按照前面的算法进行排序，直到每一部分的元素都只剩下一个。

本质上来看，快速排序应该算是在冒泡排序基础上的递归分治法。

算法原理

• 从数列中挑出一个元素作为基准点
• 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面
• 然后基准值左右两边，重复上述步骤
• 通过递归把基准值元素左右两侧的数组排序，排完之后，整个数组就排序完成了

图解

问题描述：
给定一个无序排列的数组 nums，使其能够按照有序输出

示例：

输入: nums =[4，3，1，2，9，6],
输出: nums =[1，2，3，4，6，9]

图解如下：

Java代码实现

核心代码

publicclassQuickSort{//比较 v 是否小于 wpublicstaticbooleanless(Comparable v,Comparable w){return v.compareTo(w)<0;}
​
    //数组元素交换位置privatestaticvoidswap(Comparable[] a,int i,int j){Comparable temp;
        temp = a[i];
        a[i]= a[j];
        a[j]= temp;}//排序publicstaticvoidsort(Comparable[] a){int l =0;int h = a.length -1;sort(a,l,h);}
​
    privatestaticvoidsort(Comparable[] a,int l,int h){if(h <= l)return;//对数组进行分组(左右两个数组)// i 表示分组之后基准值的索引int i =partition(a, l, h);//让左边的数组有序sort(a,l,i -1);//让有边的数组有序sort(a,i +1,h);}
​
    publicstaticintpartition(Comparable[] a,int l,int h){//确定基准值Comparable key = a[l];//定义两个指针int left = l;int right = h +1;//切分while(true){//从右向左扫描，移动right指针找一个比基准值小的元素，找到就停止while(less(key,a[--right])){if(right == l)break;}//从左向右扫描，移动left指针找一个比基准值大的元素，找到就停止while(less(a[++left],key)){if(left == h)break;}if(left>=right){break;}else{swap(a,left,right);}}//交换基准值swap(a,l,right);return right;}}

publicclassQuickSortTest{publicstaticvoidmain(String[] args){Integer[] arr ={3,1,2,4,9,6};QuickSort.sort(arr);System.out.println(Arrays.toString(arr));}}//排序前：{3,1,2,4,9,6}//排序后：{1,2,3,4,6,9}

运行结果：

算法分析

• 时间复杂度

   快速排序的最佳情况就是每一次取到的元素都刚好平分整个数组，由于快速排序用到了递归调用，因此计算其时间复杂度也需要用到递归算法来计算。T[n] = 2T[n/2] + f(n)；此时时间复杂度是O(nlogn)。最坏的情况，则和冒泡排序一样，每次比较都需要交换元素，此时时间复杂度是O(n^2)。
  

因此，快速排序的时间复杂度为：O(nlogn)。

• 空间复杂度

   空间复杂度主要是递归造成的栈空间的使用，最佳情况是，递归树的深度为log2n，此时空间复杂度为O(logn)，最坏情况，则需要进行n‐1递归调用，此时空间复杂度为 O(n)。
  

因此，快速排序的空间复杂度为： O(logn)。