图解Java经典算法快速排序的原理与实现

目录
  • 快速排序
  • 算法原理
  • 图解
  • Java代码实现
  • 算法分析

快速排序

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

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

算法原理

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

图解

问题描述：

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

示例：

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

图解如下：

Java代码实现

核心代码

public class QuickSort {
    //比较 v 是否小于 w
    public static boolean less(Comparable v,Comparable w){
        return v.compareTo(w) < 0;
    }
    //数组元素交换位置
    private static void swap(Comparable[] a,int i,int j){
        Comparable temp;
        temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
    //排序
    public static void sort(Comparable[] a){
        int l = 0;
        int h = a.length - 1;
        sort(a,l,h);
    }
    private static void sort(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);
    }
    public static int partition(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;
    }
}
public class QuickSortTest {
    public static void main(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)。

到此这篇关于图解Java经典算法快速排序的原理与实现的文章就介绍到这了,更多相关Java快速排序内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！

赞 (0)

相关推荐

  • 图解Java经典算法归并排序的原理与实现

    图解Java经典算法归并排序的原理与实现

    目录 归并排序 算法原理 动图演示 代码实现 复杂度 归并排序 归并排序主要分成两部分实现,分.合两部分,分是把数组分成两半,再递归的对子数组进行 分 操作,直到分成一个个单独的数.合是把两个数组合并为有序数组,在对有序数组进行合并,直到全部子数组合并为一个完整的数组. 算法原理 申请空间,使其大小为两个已经排序序列之和,该空间用来存放合并后的序列 设定两个指针,最初位置分别为两个已经排序序列的起始位置 比较两个指针所指向的元素,选择相对小的元素放入到合并空间,并移动指针到下一位置 重复步骤c直

  • Java实现归并排序的示例代码

    Java实现归并排序的示例代码

    目录 1.算法理解 2.实现代码 3.实现效果 1.算法理解 参考:图解Java中归并排序算法的原理与实现 2.实现代码 import java.lang.reflect.Array; import java.util.*; public class MergeSort{ // 我们的算法类不允许产生任何实例 private MergeSort(){} // 将arr[l...mid]和arr[mid+1...r]两部分进行归并 private static void merge(Compara

  • JAVA十大排序算法之基数排序详解

    JAVA十大排序算法之基数排序详解

    目录 基数排序 代码实现 时间复杂度 算法稳定性 基数排序 vs 桶排序 vs 计数排序 总结 基数排序 常见的数据元素一般是由若干位组成的,比如字符串由若干字符组成,整数由若干位0~9数字组成. 基数排序按照从右往左的顺序,依次将每一位都当做一次关键字,然后按照该关键字对数组排序,同时每一轮排序都基于上轮排序后的结果:当我们将所有的位排序后,整个数组就达到有序状态.基数排序不是基于比较的算法. 基数是什么意思?对于十进制整数,每一位都只可能是0~9中的某一个,总共10种可能.那10就是它的基,

  • 图解Java中归并排序算法的原理与实现

    图解Java中归并排序算法的原理与实现

    目录 一.基本思想 二.算法分析 1.算法描述 2.过程分析 3.动图演示 三.算法实现 一.基本思想 归并排序是建立在归并操作上的一种有效的排序算法.该算法是采用分治法(Divide and Conquer)的一个非常典型的应用.将已有序的子序列合并,得到完全有序的序列:即先使每个子序列有序,再使子序列段间有序.若将两个有序表合并成一个有序表,称为2-路归并. 二.算法分析 1.算法描述 把长度为n的输入序列分成两个长度为n/2的子序列:对这两个子序列分别采用归并排序:将两个排序好的子序列合并

  • 基数排序简介及Java语言实现

    基数排序简介及Java语言实现

    基本思想 基数排序(RadixSort)是在桶排序的基础上发展而来的,两种排序都是分配排序的高级实现.分配排序(DistributiveSort)的基本思想:排序过程无须比较关键字,而是通过"分配"和"收集"过程来实现排序.它们的时间复杂度可达到线性阶:O(n). 基数排序是一种稳定的排序算法,但有一定的局限性: 1.关键字可分解. 2.记录的关键字位数较少,如果密集更好 3.如果是数字时,最好是无符号的,否则将增加相应的映射复杂度,可先将其正负分开排序. 先来看一

  • Java快速排序与归并排序及基数排序图解示例

    Java快速排序与归并排序及基数排序图解示例

    目录 一.快速排序 1.基本介绍 2.代码实现 二.归并排序 1.基本介绍 2.代码实现 三.基数排序 1.基本介绍 2.代码实现 一.快速排序 1.基本介绍 以上面的数组为例分析快速排序. 首先要传入三个值,数组arr[ ] ,最左边下标left ,最右边下标 right.然后将根据左右的下标值计算出中间值mid. 我们要做的就是将左边的值大于mid的放到右边,将右边小于mid的值放到左边. 左右两边分别单独循环,左边找到比mid大的数,右边找到比mid小的数. 两边分别找到符合条件的数后,进

  • Java语言实现基数排序代码分享

    Java语言实现基数排序代码分享

    算法思想:依次按个位.十位...来排序,每一个pos都有分配过程和收集过程,array[i][0]记录第i行数据的个数. package sorting; /** * 基数排序 * 平均O(d(n+r)),最好O(d(n+r)),最坏O(d(n+r));空间复杂度O(n+r);稳定;较复杂 * d为位数,r为分配后链表的个数 * @author zeng * */ public class RadixSort { //pos=1表示个位,pos=2表示十位 public static int g

  • Java实现快速排序算法可视化的示例代码

    Java实现快速排序算法可视化的示例代码

    实现效果 示例代码 import java.awt.*; public class AlgoVisualizer { private static int DELAY = 100; private SelectionSortData data; private AlgoFrame frame; public AlgoVisualizer(int sceneWidth, int sceneHeight, int N){ data = new SelectionSortData(N, sceneHe

  • 图解Java经典算法快速排序的原理与实现

    图解Java经典算法快速排序的原理与实现

    目录 快速排序 算法原理 图解 Java代码实现 算法分析 快速排序 通过一趟排序将待排元素分成独立的两部分,其中一部分为比基准数小的元素,另一部分则是比基准数大的元素.然后对这两部分元素再按照前面的算法进行排序,直到每一部分的元素都只剩下一个. 本质上来看,快速排序应该算是在冒泡排序基础上的递归分治法. 算法原理 从数列中挑出一个元素作为基准点 重新排序数列,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面 然后基准值左右两边,重复上述步骤 通过递归把基准值元素左右两侧的

  • 图解Java经典算法插入排序的原理与实现

    图解Java经典算法插入排序的原理与实现

    目录 一.算法介绍 二.算法思想 三.算法原理 四.动图演示 五.代码实现 六.算法分析 6.1 时间复杂度 6.2 空间复杂度 一.算法介绍 插入排序,也称为直接插入排序.插入排序是简单排序中效率最好的一种,它也是学习其他高级排序的基础,比如希尔排序/快速排序,所以非常重要,而它相对于选择排序的优点就在于比较次数几乎是少了一半. 二.算法思想 每次将待排序的元素插入到已排序的序列中,直至全部插入完成. 三.算法原理 把所有元素分为两个序列,将第一待排序序列第一个元素看做一个有序序列,把第二个元

  • 图解Java经典算法冒泡选择插入希尔排序的原理与实现

    图解Java经典算法冒泡选择插入希尔排序的原理与实现

    目录 一.冒泡排序 1.基本介绍 2.代码实现 二. 选择排序 1.基本介绍 2.代码实现 三.插入排序 1.基本介绍 2.代码实现 四.希尔排序 1.基本介绍 2.代码实现(交换排序) 3.代码实现(移位排序) 一.冒泡排序 1.基本介绍 冒泡排序是重复地走访要排序的元素,依次比较两个相邻的元素,如果它们的顺序与自己规定的不符合,则把两个元素的位置交换.走访元素重复地进行,直到没有相邻元素需要交换为止,完成整个排序过程. 算法原理 1.比较相邻元素,如果前一个元素大于后一个元素,则交换. 2.

  • 图解Java经典算法希尔排序的原理与实现

    目录 希尔排序 算法思想 图解 代码实现(Java) 希尔排序 希尔排序时插入排序的一种,也称缩小增量排序,是直接插入排序的一种更高效的改进版本.希尔排序是非稳定排序算法. 算法思想 希尔排序是把记录按下标的一定增量分组,对每组使用直接插入排序算法排序,随着增量逐渐减少,每组包含的数越来越多当增量减至1时,整个序列恰好被分成一组,算法完成. 我们以增序排序为例,希尔排序基本步骤:选择初始增量gap=length/2,缩小增量继续以gap=gap/2的方式进行,直到增量gap=1为止,增量的每次变

  • Java经典设计模式之适配器模式原理与用法详解

    Java经典设计模式之适配器模式原理与用法详解

    本文实例讲述了Java经典设计模式之适配器模式.分享给大家供大家参考,具体如下: 适配器模式是把一个类的接口适配成用户所期待的,使得原本由于接口不兼容而不能一起工作的一些类可以在一起工作从而实现用户所期望的功能. 适配器模式的优势: 1. 通过适配器,客户端可以调用统一接口,操作简单直接,并且代码逻辑紧凑,使用起来方便. 2. 代码复用,适配器模式就是解决因为环境要求不相同 的问题,通过适配实现代码复用. 3. 将目标类和适配器类解耦,通过新建一个适配器类来重用现在的类,不用再去重复修改原有代码

  • Java经典设计模式之观察者模式原理与用法详解

    本文实例讲述了Java经典设计模式之观察者模式.分享给大家供大家参考,具体如下: 观察者模式:对象间的一种一对多的依赖关系,让多个观察者对象同时监听某一个主题对象(被观察). 以便一个对象的状态发生变化时,所有依赖于它的对象都得到通知并发生相应的变化. 观察者模式有很多实现方式:该模式必须包含观察者和被观察对象两种角色.观察者和被观察者之间存在"观察"的逻辑关系,当被观察者发生改变的时候,观察者就会观察到这样的变化,发出相应的改变. /** * 观察者接口:观察者,需要用到观察者模式的

  • 图解Java排序算法之快速排序的三数取中法

    图解Java排序算法之快速排序的三数取中法

    目录 基本步骤 三数取中 根据枢纽值进行分割 代码实现 总结 基本步骤 三数取中 在快排的过程中,每一次我们要取一个元素作为枢纽值,以这个数字来将序列划分为两部分.在此我们采用三数取中法,也就是取左端.中间.右端三个数,然后进行排序,将中间数作为枢纽值. 根据枢纽值进行分割 代码实现 package sortdemo; import java.util.Arrays; /** * Created by chengxiao on 2016/12/14. * 快速排序 */ public class

  • Java经典算法汇总之顺序查找(Sequential Search)

    Java经典算法汇总之顺序查找(Sequential Search)

    a)原理:顺序查找就是按顺序从头到尾依次往下查找,找到数据,则提前结束查找,找不到便一直查找下去,直到数据最后一位. b)图例说明: 原始数据:int[]a={4,6,2,8,1,9,0,3}; 要查找数字:8 找到数组中存在数据8,返回位置. 代码演示: import java.util.Scanner; /* * 顺序查找 */ public class SequelSearch { public static void main(String[] arg) { int[] a={4,6,2

  • 图解Java排序算法之希尔排序

    图解Java排序算法之希尔排序

    目录 基本思想 代码实现 总结 希尔排序是希尔(Donald Shell)于1959年提出的一种排序算法.希尔排序也是一种插入排序,它是简单插入排序经过改进之后的一个更高效的版本,也称为缩小增量排序,同时该算法是冲破O(n2)的第一批算法之一.本文会以图解的方式详细介绍希尔排序的基本思想及其代码实现. 基本思想 希尔排序是把记录按下标的一定增量分组,对每组使用直接插入排序算法排序:随着增量逐渐减少,每组包含的关键词越来越多,当增量减至1时,整个文件恰被分成一组,算法便终止. 简单插入排序很循规蹈

随机推荐