图文讲解Java中实现quickSort快速排序算法的方法

相对冒泡排序、选择排序等算法而言,快速排序的具体算法原理及实现有一定的难度。为了更好地理解快速排序,我们仍然以举例说明的形式来详细描述快速排序的算法原理。在前面的排序算法中,我们以5名运动员的身高排序问题为例进行讲解,为了更好地体现快速排序的特点,这里我们再额外添加3名运动员。实例中的8名运动员及其身高信息详细如下(F、G、H为新增的运动员): A(181)、B(169)、C(187)、D(172)、E(163)、F(191)、G(189)、H(182)

在前面的排序算法中,这些排序都是由教练主导完成了,现在运动员人数增加了,教练也想趁机去休息一下,于是教练叫来了两名助手,让这两名助手以快速排序法的排序方式来实现对8名运动员的身高从左到右、从低到高的排序。

按照快速排序法的算法原理,两名助手分别站在运动员排列的两侧,如下图所示:

首先,助手1从排列中选出一名运动员(一般选择左侧第1位运动员或最中间的运动员),这里选择运动员A(181)。由于排序是从左到右、从低到高,所以助手1需要一个身高比A(181)更小的运动员(选出来的A(181)作为比较的基准,本轮所有的比较,都是与最初选出来的运动员A(181)比较):

下面我们来继续参考快速排序第一轮的详细示意图。

当两名助手在排序寻找的过程中相遇后,就停止当前轮次的比较,并把最初选出来的运动员A(181)放在两名助手相遇的空位上:

在快速排序中,当两名助手相遇时,本轮排序就结束了。此时,我们发现,以两名运动员相遇的位置A(181)作为分割点,排列左边的都是身高比A(181)小的运动员,排列右侧的都是身高比A(181)大的运动员。这个时候,我们再把A(181)左侧和右侧的两个排序分开来看,如果我们继续使用上述两名助手的排序方法分别对两边的排列进行排序,那么经过多次排列后,最后就能够得到我们所需要的排序结果。

上面就是快速排序的整个排序实现过程。快速排序就是利用上述的排序规则,将一个排列分为两个排列,两个排列分为四个排列,直到无排列可分为止,最后就得到了我们所需要的排序结果。

现在,我们依然编程Java代码来实现使用快速排序对上述8名运动员的身高进行排序:

/**
 * 对指定的数组中索引从start到end之间的元素进行快速排序
 *
 * @param array 指定的数组
 * @param start 需要快速排序的数组索引起点
 * @param end 需要快速排序的数组索引终点
 */
public static final void quickSort(int[] array, int start, int end) {
  // i相当于助手1的位置,j相当于助手2的位置
  int i = start, j = end;
  int pivot = array[i]; // 取第1个元素为基准元素
  int emptyIndex = i; // 表示空位的位置索引,默认为被取出的基准元素的位置
  // 如果需要排序的元素个数不止1个,就进入快速排序(只要i和j不同,就表明至少有2个数组元素需要排序)
  while (i < j) {
    // 助手2开始从右向左一个个地查找小于基准元素的元素
    while (i < j && pivot <= array[j])
      j--;
    if (i < j) {
      // 如果助手2在遇到助手1之前就找到了对应的元素,就将该元素给助手1的"空位",j成了空位
      array[emptyIndex] = array[emptyIndex = j];
    }

    // 助手1开始从左向右一个个地查找大于基准元素的元素
    while (i < j && array[i] <= pivot)
      i++;
    if (i < j) {
      // 如果助手1在遇到助手2之前就找到了对应的元素,就将该元素给助手2的"空位",i成了空位
      array[emptyIndex] = array[emptyIndex = i];
    }
  }
  // 助手1和助手2相遇后会停止循环,将最初取出的基准值给最后的空位
  array[emptyIndex] = pivot;

  // =====本轮快速排序完成=====

  // 如果分割点i左侧有2个以上的元素,递归调用继续对其进行快速排序
  if (i - start > 1) {
    quickSort(array, 0, i - 1);
  }
  // 如果分割点j右侧有2个以上的元素,递归调用继续对其进行快速排序
  if (end - j > 1) {
    quickSort(array, j + 1, end);
  }
}

//主方法
public static void main(String[] args) {
  // =====使用快速排序法对表示8名运动员身高的数组heights进行从低到高的排序=====
  // A(181)、B(169)、C(187)、D(172)、E(163)、F(191)、G(189)、H(182)
  int[] heights = { 181, 169, 187, 172, 163, 191, 189, 182 };
  // 调用快速排序方法
  quickSort(heights, 0, heights.length - 1);
  // 输出排序后的结果
  for (int height : heights) {
    System.out.println(height);
  }
}

以上Java代码运行结果输出如下:

163
169
172
181
182
187
189
191

注意:由于局部思维差异,上述快速排序的代码实现可能存在多种变体。不过,无论何种形式的变体,快速排序的核心思想并不会发生改变。

另一种实现:单向扫描
快速排序的数组切分还有另一种单向扫描的版本,具体步骤是选择数组中最后一个元素作为切分元素,同样设置两个指针,指针i指向数组中第一个元素前面一个位置,j则指向数组中第一个元素。j从前左右往右扫描,遇到小于等于切分元素时就把i加一,然后交换i和j指向的元素。最后把i+1位置的元素和切分元素交换即可完成一次数组划分。代码实现如下:

int partition(int[] a, int lo, int hi) {
  int i = lo - 1, j = lo;
  int v = a[hi];
  while (j < hi) {
    if (a[j] <= v) {
      swap(a, ++i, j);
    }
    j++;
  }
  swap(a, i + 1, hi);
  return i + 1;
}
(0)

相关推荐

  • 堆排序算法的讲解及Java版实现

    堆是数据结构中的一种重要结构,了解了"堆"的概念和操作,可以快速掌握堆排序. 堆的概念 堆是一种特殊的完全二叉树(complete binary tree).如果一棵完全二叉树的所有节点的值都不小于其子节点,称之为大根堆(或大顶堆):所有节点的值都不大于其子节点,称之为小根堆(或小顶堆). 在数组(在0号下标存储根节点)中,容易得到下面的式子(这两个式子很重要): 1.下标为i的节点,父节点坐标为(i-1)/2: 2.下标为i的节点,左子节点坐标为2*i+1,右子节点为2*i+2. 堆

  • 详解堆排序算法原理及Java版的代码实现

    概述 堆排序是一种树形选择排序,是对直接选择排序的有效改进. 堆的定义如下:具有n个元素的序列(k1,k2,...,kn), 当且仅当满足: 时称之为堆.由堆的定义可以看出,堆顶元素(即第一个元素)必为最小项(小顶堆)或最大项(大顶堆). 若以一维数组存储一个堆,则堆对应一棵完全二叉树,且所有非叶结点(有子女的结点)的值均不大于(或不小于)其子女的值,根结点(堆顶元素)的值是最小(或最大)的. (a)大顶堆序列:(96, 83, 27, 38, 11, 09) (b)小顶堆序列:(12, 36,

  • java实现的各种排序算法代码示例

    折半插入排序 折半插入排序是对直接插入排序的简单改进.此处介绍的折半插入,其实就是通过不断地折半来快速确定第i个元素的 插入位置,这实际上是一种查找算法:折半查找.Java的Arrays类里的binarySearch()方法,就是折半查找的实现,用 于从指定数组中查找指定元素,前提是该数组已经处于有序状态.与直接插入排序的效果相同,只是更快了一些,因 为折半插入排序可以更快地确定第i个元素的插入位置 代码: package interview; /** * @author Administrat

  • Java实现冒泡排序算法及对其的简单优化示例

    原理 冒泡排序大概是所有程序员都会用的算法,也是最熟悉的算法之一. 它的思路并不复杂: 设现在要给数组arr[]排序,它有n个元素. 1.如果n=1:显然不用排了.(实际上这个讨论似乎没什么必要) 2.如果n>1: (1)我们从第一个元素开始,把每两个相邻元素进行比较,如果前面的元素比后面的大,那么在最后的结果里面前者肯定排在后面.所以,我们把这两个元素交换.然后进行下两个相邻的元素的比较.如此直到最后一对元素比较完毕,则第一轮排序完成.可以肯定,最后一个元素一定是数组中最大的(因为每次都把相对

  • 三种简单排序算法(使用java实现)

    一.冒泡排序 算法思想:遍历待排序的数组,每次遍历比较相邻的两个元素,如果他们的排列顺序错误就交换他们的位置,经过一趟排序后,最大的元素会浮置数组的末端.重复操 作,直到排序完成. 示例演示: 算法实现: for(int i=0;i<array.length-1;i++){//最多排序n-1次 for(int j=0;j<array.length-i-1;j++){//需要交换的次数 if(array[j]>array[j+1]){ int temp=array[j]; array[j]

  • 图文讲解Java中实现quickSort快速排序算法的方法

    相对冒泡排序.选择排序等算法而言,快速排序的具体算法原理及实现有一定的难度.为了更好地理解快速排序,我们仍然以举例说明的形式来详细描述快速排序的算法原理.在前面的排序算法中,我们以5名运动员的身高排序问题为例进行讲解,为了更好地体现快速排序的特点,这里我们再额外添加3名运动员.实例中的8名运动员及其身高信息详细如下(F.G.H为新增的运动员): A(181).B(169).C(187).D(172).E(163).F(191).G(189).H(182) 在前面的排序算法中,这些排序都是由教练主

  • Java中七种排序算法总结分析

    目录 前言:对文章出现的一些名词进行解释 一.插入排序 1.基本思想 2.直接插入排序 3.希尔排序(缩小增量排序) 二.选择排序 1.基本思想 2.直接选择排序 3.堆排序 三.交换排序 1.基本思想 2.冒泡排序 3.快速排序(递归与非递归) 1.Hoare版 2.挖坑法 3.前后标记法(难理解) 4.快速排序优化 5.快速排序非递归 6.相关特性总结 四.归并排序(递归与非递归) 前言:对文章出现的一些名词进行解释 排序: 使一串记录,按照其中的某个或某些关键字的大小,递增或者递减排列起来

  • java 中模式匹配算法-KMP算法实例详解

    java 中模式匹配算法-KMP算法实例详解 朴素模式匹配算法的最大问题就是太低效了.于是三位前辈发表了一种KMP算法,其中三个字母分别是这三个人名的首字母大写. 简单的说,KMP算法的对于主串的当前位置不回溯.也就是说,如果主串某次比较时,当前下标为i,i之前的字符和子串对应的字符匹配,那么不要再像朴素算法那样将主串的下标回溯,比如主串为"abcababcabcabcabcabc",子串为"abcabx".第一次匹配的时候,主串1,2,3,4,5字符都和子串相应的

  • 简单讲解java中throws与throw的区别

    Java中throws和throw的区别讲解 当然,你需要明白异常在Java中式以一个对象来看待. 并且所有系统定义的编译和运行异常都可以由系统自动抛出,称为标准异常,但是一般情况下Java 强烈地要求应用程序进行完整的异常处理,给用户友好的提示,或者修正后使程序继续执行. 直接进入正题哈: 1.用户程序自定义的异常和应用程序特定的异常,必须借助于 throws 和 throw 语句来定义抛出异常. 1.1   throw是语句抛出一个异常. 语法:throw (异常对象);         

  • 实例讲解Java中的synchronized

    一.使用场景 在负责后台开发的时候,很多时候都是提供接口给前端开发人员去调用,会遇到这样的场景: 需要提供一个领奖接口,每个用户名只能领取一次,我们可以将成功领取的用户在数据库用个标记保存起来.如果这个用户再来领取的时候,查询数据库看该用户是否领取过. 但是问题来了,假设用户手速很快,极短时间内点了两次领奖按钮(前端没有进行控制,我们也不能依赖前端去控制).那么可能掉了两次领奖接口,而且有可能第二次调用的时候查询数据库的时候,第一次领奖还没有执行完成更新领奖标记. 这种场景就可以使用到synch

  • 深入浅出讲解Java中的枚举类

    目录 一.枚举类的使用 二.如何定义枚举类 背景:类的对象只有有限个,确定的.举例如下: > 星期: Monday (星期一).-.. Sunday (星期天) > 性别: Man (男). Woman (女) > 季节: Spring (春节).--.. Winter (冬天) > 支付方式: Cash (现金). WeChatPay (微信). Alipay (支付宝) BankCard (银 行卡). CreditCard (信用卡) > 就职状态: Busy . Fr

  • 详解5种Java中常见限流算法

    目录 01固定窗口 02滑动窗口 03漏桶算法 04令牌桶 05滑动日志 06分布式限流 07总结 1.瞬时流量过高,服务被压垮? 2.恶意用户高频光顾,导致服务器宕机? 3.消息消费过快,导致数据库压力过大,性能下降甚至崩溃? ...... 在高并发系统中,出于系统保护角度考虑,通常会对流量进行限流:不但在工作中要频繁使用,而且也是面试中的高频考点. 今天我们将图文并茂地对常见的限流算法分别进行介绍,通过各个算法的特点,给出限流算法选型的一些建议,并给出Java语言实现的代码示例. 01固定窗

  • 超详细解析C++实现快速排序算法的方法

    目录 一.前言 1.分治算法 2.分治算法解题方法 二.快速排序 1.问题分析 2.算法设计 3.算法分析 三.AC代码 一.前言 1.分治算法 快速排序,其实是一种分治算法,那么在了解快速排序之前,我们先来看看什么是分治算法.在算法设计中,我们引入分而治之的策略,称为分治算法,其本质就是将一个大规模的问题分解为若干个规模较小的相同子问题,分而治之. 2.分治算法解题方法 1.分解: 将要解决的问题分解为若干个规模较小.相互独立.与原问题形式相同的子问题. 2.治理: 求解各个子问题.由于各个子

  • Java中RSA加密解密的实现方法分析

    本文实例讲述了Java中RSA加密解密的实现方法.分享给大家供大家参考,具体如下: public static void main(String[] args) throws Exception { // TODO Auto-generated method stub HashMap<String, Object> map = RSAUtils.getKeys(); //生成公钥和私钥 RSAPublicKey publicKey = (RSAPublicKey) map.get("

  • java中hashCode、equals的使用方法教程

    前言 众所周知Java.lang.Object 有一个hashCode()和一个equals()方法,这两个方法在软件设计中扮演着举足轻重的角色.在一些类中重写这两个方法以完成某些重要功能. 1.为什么要用 hashCode()? 集合Set中的元素是无序且不可重复的,那判断两个元素是否重复的依据是什么呢? 有人说:比较对象是否相等当然用Object.equal()了.但是,Set中存在大量对象,后添加到集合Set中的对象元素比较次数会逐渐增多,大大降低了程序运行效率. Java中采用哈希算法(

随机推荐