排序算法性能王——快速排序

简介: 这篇文章主要介绍在常见的排序算法中综合性能最高的算法——快速排序

1.思路梳理与确定基准位置


思想:

实现快排的思想就是在待排序列中找一个基准值,让待排序列中比基准值小的元素放在基准值左边,比基准值大的元素放在基准值右边,这样就确定了基准值在待排序列中的位置,再让基准值左侧和右侧的区间分别进行相同的操作,直到区间中只剩下一个元素时,待排序列中的所有元素就有序了。


简单实现方法都是先让数组第一个元素作为基准值,然后通过数组中其他元素与该值的比较来确定该基准值应该在的位置。

将区间按照基准值划分为左右两半部分的常见方式有三种:


  • 挖坑法
  • Hoare法
  • 前后指针法


挖坑法实现思路:


1.选取数组中第一个元素作为基准值,存储该元素并将该位置腾出坑位。

2.设立两个指针分别位于数组的始末,先让后边的指针往前走,遇到比基准值小的元素,就让该元素移至坑位。

3.让前边的指针往前走,遇到比基准值大的元素再填入新坑位

4.前后指针交替进行相同的操作,直到两个指针相遇时,将之前存储的元素至于该坑位,区间划分完毕。


微信图片_20230111025447.gif

代码实现:


private static int partitionHole(int[] array,int start,int end) {
        int key=array[start];
        while (start<end) {
            while (start<end&&array[end]>=key) {
                end--;
            }
            array[start]=array[end];
            while (start<end&&array[start]<=key) {
                start++;
            }
            array[end]=array[start];
        }
        array[start]=key;
        return start;
    }


Hoare法实现思路:

1.选取数组中第一个元素作为基准值,设立两个指针分别位于数组的始末。

2.让后指针先走,遇到比基准值小的元素停下;前指针后走,遇到比基准值大的元素停下,前后两指针所在位置元素交换。

3.交换完毕后继续相同操作,直至两指针相遇,让区间第一个元素与相遇位置元素互换。


微信图片_20230111025444.gif

代码实现:


 

private static int partitionHoare(int[] array,int start,int end) {
        int i=start;//先存储好start下标,用于最后的交换
        int key=array[start];
        while (start<end) {
          //为什么取等号?为什么后指针先走?在下边分析中解释
            while (start<end&&array[end]>=key) {
                end--;
            }
            while (start<end&&array[start]<=key) {
                start++;
            }
            swap(array,start,end);
        }
        swap(array,start,i);
        return start;
    }


细节问题分析:


1.为什么取等号?

若遇到像下图这样的情况,将会进入死循环,所以必须加上等号


微信图片_20230111025440.png

2.为什么让后指针先走?

让后指针先走,前指针后走,重复这样的操作直到两指针相遇时,能保证相遇位置元素一定比区间起始位置元素小,才能让两者交换后保证基准值前边的元素都小于基准值,后边的元素都大于基准值。


前后指针法实现思路:

1.选取区间第一个元素作为基准值,第一个元素先不动

2.设立快慢指针从前往后遍历,遇到比基准值大的元素,快指针走慢指针不走,再次符合条件时进行交换

3.最后快指针走完后,让区间起始位置元素与慢指针位置元素交换


代码实现:


public static int partition(int[] array,int start,int end) {
        int prev=start;
        int cur=start+1;
        while (cur<=end) {
            if(array[cur]<array[start]&&array[++prev]!=array[cur]) {
                swap(array,cur,prev);
            }
            cur++;
        }
        swap(array,prev,start);
        return prev;
    }

2.实现并优化


在1中,我们已经确定了基准位置,现在我们可以通过1中思路的梳理来简单实现快排(以Hoare法为例)

简单实现:


 

private static void quick(int[] array,int left,int right) {
    //在升序或降序的极端情况下,会出现left>right的情况
        if(left>=right) {
            return;
        }
        int pivot=partitionHoare(array,left,right);
        quick(array,left,pivot-1);
        quick(array,pivot+1,right);
    }
    public static void quickSort(int[] array) {
        quick(array,0,array.length-1);
    }


分析思路与代码可以发现,通过递归实现的快排,如果在理想状态下,每次的基准值都位于区间的正中间,就会构成一棵完全二叉树(如下图),分析上边的代码可以发现,快排方法的时间复杂度理想状态为O(N*log2N),空间复杂度为递归深度O(log2N);


quick(array,left,pivot-1); 求pivot的时间复杂度为O(N),递归深度如果为完全二叉树就是log2N.


微信图片_20230111025434.png


但如果待排序列为升序或者降序时,如果取区间起始位置或结束位置为基准值进行递归,将会得到的是一课只有左孩子的树或者只有右孩子的树,其深度为N,这样的时间复杂度将会变为O(N^2),空间复杂度为O(N).(如果真的是这样的极端情况,递归的深度太深,如果数据量较大将会栈溢出)


所以我们可以通过调整基准值的选取方式来优化递归,采用的方法为三数取中法选取基准值

,就是通过选取区间两个边界和中间位置三个元素的中数作为基准值的方式,才会减少递归的深度。


private static int midNumIndex(int[] array,int left,int right) {
        int mid = (left+right) / 2 ;
        if(array[left] < array[right]) {
            if(array[mid] < array[left]) {
                return left;
            }else if(array[mid] > array[right]) {
                return right;
            }else {
                return mid;
            }
        }else {
            if(array[mid] < array[right]) {
                return right;
            }else if(array[mid] > array[left]){
                return left;
            }else {
                return mid;
            }
        }
    }


再有就是当递归深度足够深时,区间内的元素基本已经趋于有序,这时可以在小区间改用直接插入排序的方式再次减少递归深度。


此时的直接插入需要稍作改动:


private static void insertSort(int[] array,int start,int end) {
        for (int i = start+1; i <=end ; i++) {
            int tmp=array[i];
            int j=i-1;
            for (; j >=start ; j--) {
                if(array[j]>tmp) {
                    array[j+1]=array[j];
                }else {
                    break;
                }
            }
            array[j+1]=tmp;
        }
    }


最后优化后的代码:


public static void swap(int[] array,int i,int j) {
        int tmp=array[i];
        array[i]=array[j];
        array[j]=tmp;
  }
   private static void quick(int[] array,int left,int right) {
        if(left>=right) {
            return;
        }
        //小区间使用直接插入排序: 主要 优化了递归的深度
        if(right-left+1<=7) {
            insertSort(array, left, right);
            return;
        }
        //三数取中:解决递归深度问题 基本上 有了三数取中  你的待排序序列 基本上每次都是二分N*logn
        int index = midNumIndex(array,left,right);
        swap(array,left,index);
        int pivot=partitionHoare(array,left,right);
        quick(array,left,pivot-1);
        quick(array,pivot+1,right);
    }
    public static void quickSort(int[] array) {
        quick(array,0,array.length-1);
    }


通过优化,时间复杂度就可以达到O(N*log2N),空间复杂度就是递归的深度O(log2N)


3.非递归实现


通过利用栈来非递归的实现排序

思路:

先将基准值放在指定位置,然后分别入栈基准值左区间的边界角标和基准值右区间的边界角标(当区间元素只剩1时不入栈),弹出两个栈顶元素分别作为新区间的始末位置再找基准,重复相同操作直至所有元素完成排序。


代码实现:


public static void quickSort2(int[] array) {
        Stack<Integer> stack=new Stack<>();
        int left=0;
        int right=array.length-1;
        int index=midNumIndex(array,left,right);
        swap(array,left,index);
        int pivot=partitionHole(array,left,right);
        if(pivot>left+1) {
            stack.push(left);
            stack.push(pivot-1);
        }
        if (pivot<right-1) {
            stack.push(pivot+1);
            stack.push(right);
        }
        while (!stack.empty()) {
            right=stack.pop();
            left=stack.pop();
            index=midNumIndex(array,left,right);
            swap(array,left,index);
            pivot=partitionHole(array,left,index);
            if(pivot>left+1) {
                stack.push(left);
                stack.push(pivot-1);
            }
            if(pivot<right-1) {
                stack.push(pivot+1);
                stack.push(right);
            }
        }
    }

4.特性总结


  • 经过优化后的快速排序,综合性能和使用场景都是比较好的,所以才叫做快速排序
  • 时间复杂度(优化后) O(N*log2N)
  • 空间复杂度(优化后) O(log2N)
  • 稳定性:不稳定
相关文章
|
10天前
|
搜索推荐 C语言
【排序算法】快速排序升级版--三路快排详解 + 实现(c语言)
本文介绍了快速排序的升级版——三路快排。传统快速排序在处理大量相同元素时效率较低,而三路快排通过将数组分为三部分(小于、等于、大于基准值)来优化这一问题。文章详细讲解了三路快排的实现步骤,并提供了完整的代码示例。
36 4
|
1月前
|
算法 搜索推荐 Shell
数据结构与算法学习十二:希尔排序、快速排序(递归、好理解)、归并排序(递归、难理解)
这篇文章介绍了希尔排序、快速排序和归并排序三种排序算法的基本概念、实现思路、代码实现及其测试结果。
21 1
|
1月前
|
搜索推荐 Java Go
深入了解快速排序算法
深入了解快速排序算法
32 2
|
1月前
|
存储 搜索推荐 算法
【排序算法(二)】——冒泡排序、快速排序和归并排序—>深层解析
【排序算法(二)】——冒泡排序、快速排序和归并排序—>深层解析
|
1月前
|
算法 Python
Python算法编程:冒泡排序、选择排序、快速排序
Python算法编程:冒泡排序、选择排序、快速排序
|
1月前
|
搜索推荐 C语言 C++
【C语言】指针篇-精通库中的快速排序算法:巧妙掌握技巧(4/5)
【C语言】指针篇-精通库中的快速排序算法:巧妙掌握技巧(4/5)
|
3月前
|
搜索推荐 算法 Java
现有一个接口DataOperation定义了排序方法sort(int[])和查找方法search(int[],int),已知类QuickSort的quickSort(int[])方法实现了快速排序算法
该博客文章通过UML类图和Java源码示例,展示了如何使用适配器模式将QuickSort类和BinarySearch类的排序和查找功能适配到DataOperation接口中,实现算法的解耦和复用。
40 1
现有一个接口DataOperation定义了排序方法sort(int[])和查找方法search(int[],int),已知类QuickSort的quickSort(int[])方法实现了快速排序算法
|
3月前
|
算法 搜索推荐
算法设计 (分治法应用实验报告)基于分治法的合并排序、快速排序、最近对问题
这篇文章是关于分治法应用的实验报告,详细介绍了如何利用分治法实现合并排序和快速排序算法,并探讨了使用分治法解决二维平面上的最近对问题的方法,包括伪代码、源代码实现及时间效率分析,并附有运行结果和小结。
|
4月前
|
算法 搜索推荐 编译器
算法高手养成记:Python快速排序的深度优化与实战案例分析
【7月更文挑战第11天】快速排序是编程基础,以O(n log n)时间复杂度和原址排序著称。其核心是“分而治之”,通过选择基准元素分割数组并递归排序两部分。优化包括:选择中位数作基准、尾递归优化、小数组用简单排序。以下是一个考虑优化的Python实现片段,展示了随机基准选择。通过实践和优化,能提升算法技能。**
56 3
|
5月前
|
搜索推荐 算法 Java
Java中的快速排序、归并排序和堆排序是常见的排序算法。
【6月更文挑战第21天】Java中的快速排序、归并排序和堆排序是常见的排序算法。快速排序采用分治,以基准元素划分数组并递归排序;归并排序同样分治,先分割再合并有序子数组;堆排序通过构建堆来排序,保持堆性质并交换堆顶元素。每种算法各有优劣:快排平均高效,最坏O(n²);归并稳定O(n log n)但需额外空间;堆排序O(n log n)且原地排序,但不稳定。
47 3