Java基于分治法实现的快速排序算法示例

2024-02-19 02:06:00

本文实例讲述了Java基于分治法实现的快速排序算法。分享给大家供大家参考，具体如下：

package cn.nwsuaf.quick;
/**
 * 随机产生20个数，并对其进行快速排序
 *
 * @author 刘永浪
 *
 */
public class Quick {
  /**
   * 交换函数，实现数组中两个数的交换操作
   *
   * @param array
   *      待操作数组
   * @param i
   *      交换数组的第一个下标
   * @param j
   *      交换数组的第二个下标
   */
  public static void swap(int[] array, int i, int j) {
    int temp = array[i];
    array[i] = array[j];
    array[j] = temp;
  }
  /**
   * 分治法划分算法
   *
   * @param array
   *      待操作数组
   * @param low
   *      划分中模块的起始地址
   * @param height
   *      划分中模块的结束地址
   * @return 基准元素的位置下标
   */
  public static int quick(int[] array, int low, int height) {
    // 设置第一个数为基准元素
    int pivot = array[low];
    // 从右向左扫描，查找第1个小于pivot的元素
    while (low < height) {
      while (low < height && array[height] >= pivot)
        height--;
      // 表示找到了小于pivot的元素
      if (low < height)
        // 交换后low执行+1操作
        swap(array, low++, height);
      // 从左向右扫描，查找第1个大于pivot的元素
      while (low < height && array[low] <= pivot)
        low++;
      // 表示找到了大于pivot的元素
      if (low < height)
        // 交换后heigh执行-1操作
        swap(array, low, height--);
    }
    // 返回基准元素最终位置下标
    return height;
  }
  /**
   * 对array快速排序
   *
   * @param array
   *      待操作数组
   * @param low
   *      低位
   * @param height
   *      高位
   */
  public static void sort(int[] array, int low, int height) {
    // 记录划分后的基准元素所对应的位置
    int temp;
    // 仅当区间长度大于1时才须排序
    if (low < height) {
      // 对array做划分
      temp = quick(array, low, height);
      // 对左区间递归排序
      sort(array, low, temp - 1);
      // 对右区间递归排序
      sort(array, temp + 1, height);
    }
  }
  public static void main(String[] args) {
    int[] array = new int[20];
    System.out.println("我们测试结果:");
    System.out.print("排序前序列:");
    for (int i = 0; i < array.length; i++) {
      // 随机产生20个0-99的整数
      array[i] = (int) (Math.random() * 100);
      System.out.print(array[i] + " ");
    }
    System.out.print("\n排序后序列:");
    sort(array, 0, array.length - 1);
    for (int i = 0; i < array.length; i++)
      System.out.print(array[i] + " ");
  }
}

运行结果：

PS：这里再为大家推荐一款关于排序的演示工具供大家参考：

在线动画演示插入/选择/冒泡/归并/希尔/快速排序算法过程工具：
http://tools.jb51.net/aideddesign/paixu_ys

更多关于java算法相关内容感兴趣的读者可查看本站专题：《Java数据结构与算法教程》、《Java操作DOM节点技巧总结》、《Java文件与目录操作技巧汇总》和《Java缓存操作技巧汇总》

希望本文所述对大家java程序设计有所帮助。

Java分治归并排序算法实例详解

本文实例讲述了Java分治归并排序算法.分享给大家供大家参考,具体如下: 1.分治法许多有用的算法在结构上是递归的:为了解决一个给定的问题,算法一次或多次递归地调用其自身以解决紧密相关的若干子问题.这些算法典型地遵循分治法的思想:将原问题分解为几个规模较小但类似于原问题的子问题,递归地求解这些子问题,然后再合并这些子问题的解来建立原问题的解. 分治模式在每层递归时都有三个步骤: (1)分解原问题为若干子问题,这些子问题是原问题的规模较小的实例. (2)解决这些子问题,递归地求解各子问题.然而,
java实现的各种排序算法代码示例

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

本文实例讲述了Java数组常用排序算法.分享给大家供大家参考,具体如下: 1.冒泡排序法 SortArray_01.java public class SortArray_01 { public static void main(String args[]) { int[] array = { 14, 5, 86, 4, 12, 3, 21, 13, 11, 2, 55, 66, 22 }; // 创建一个初始化的一维数组array System.out.println("未排序的数组:&quo
Java排序算法之归并排序简单实现

算法描述:对于给定的一组记录,首先将每两个相邻的长度为1的子序列进行归并,得到 n/2(向上取整)个长度为2或1的有序子序列,再将其两两归并,反复执行此过程,直到得到一个有序序列. package sorting; /** * 归并排序 * 平均O(nlogn),最好O(nlogn),最坏O(nlogn);空间复杂度O(n);稳定;较复杂 * @author zeng * */ public class MergeSort { public static void merge(int[] a,
Java语言字典序排序算法解析及代码示例

字典序法就是按照字典排序的思想逐一产生所有排列. 在数学中,字典或词典顺序(也称为词汇顺序,字典顺序,字母顺序或词典顺序)是基于字母顺序排列的单词按字母顺序排列的方法. 这种泛化主要在于定义有序完全有序集合(通常称为字母表)的元素的序列(通常称为计算机科学中的单词)的总顺序. 对于数字1.2.3......n的排列,不同排列的先后关系是从左到右逐个比较对应的数字的先后来决定的.例如对于5个数字的排列 12354和12345,排列12345在前,排列12354在后.按照这样的规定,5个数字的所有的
Java堆排序算法详解

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

java 中归并排序算法详解归并排序算法,顾名思义,是一种先分再合的算法,其算法思想是将要排序的数组分解为单个的元素,每个元素就是一个单个的个体,然后将相邻的两个元素进行从小到大或从大到小的顺序排序组成一个整体,每个整体包含一到两个元素,然后对相邻的整体继续"合"并,因为每个整体都是排过序的,因而可以采用一定的算法对其进行合并,合并之后每个整体包含三到四个元素,继续对相邻的整体进行合并,直到所有的整体都合并为一个整体,最终得到的整体就是将原数组进行排序之后的结果. 对于相邻的整体,其
快速排序算法在Java中的实现

快速排序的原理:选择一个关键值作为基准值.比基准值小的都在左边序列(一般是无序的),比基准值大的都在右边(一般是无序的).一般选择序列的第一个元素. 一次循环:从后往前比较,用基准值和最后一个值比较,如果比基准值小的交换位置,如果没有继续比较下一个,直到找到第一个比基准值小的值才交换.找到这个值之后,又从前往后开始比较,如果有比基准值大的,交换位置,如果没有继续比较下一个,直到找到第一个比基准值大的值才交换.直到从前往后的比较索引>从后往前比较的索引,结束第一次循环,此时,对于基准值来说,左右两
Java基于分治法实现的快速排序算法示例

本文实例讲述了Java基于分治法实现的快速排序算法.分享给大家供大家参考,具体如下: package cn.nwsuaf.quick; /** * 随机产生20个数,并对其进行快速排序 * * @author 刘永浪 * */ public class Quick { /** * 交换函数,实现数组中两个数的交换操作 * * @param array * 待操作数组 * @param i * 交换数组的第一个下标 * @param j * 交换数组的第二个下标 */ public static
基于Java实现的一层简单人工神经网络算法示例

本文实例讲述了基于Java实现的一层简单人工神经网络算法.分享给大家供大家参考,具体如下: 先来看看笔者绘制的算法图: 2.数据类 import java.util.Arrays; public class Data { double[] vector; int dimention; int type; public double[] getVector() { return vector; } public void setVector(double[] vector) { this.vect
Python实现基于二叉树存储结构的堆排序算法示例

本文实例讲述了Python实现基于二叉树存储结构的堆排序算法.分享给大家供大家参考,具体如下: 既然用Python实现了二叉树,当然要写点东西练练手. 网络上堆排序的教程很多,但是却几乎都是以数组存储的数,直接以下标访问元素,当然这样是完全没有问题的,实现简单,访问速度快,也容易理解. 但是以练手的角度来看,我还是写了一个二叉树存储结构的堆排序其中最难的问题就是交换二叉树中两个节点. 因为一个节点最多与三个节点相连,那么两个节点互换,就需要考虑到5个节点之间的关系,也需要判断是左右孩子,这将是
Python实现的基于优先等级分配糖果问题算法示例

本文实例讲述了Python实现的基于优先等级分配糖果问题算法.分享给大家供大家参考,具体如下: 问题: 有n个人,每个人有一定的优先等级,等级高的人要比身边等级低得人得到的多,每个人都不会分不到思路: 可以采用两头遍历的方法,顺序遍历保证等级高的人会比左边的人多,倒序遍历可以保证等级高的人比右边的人多下面是具体实现: #!usr/bin/env python #encoding:utf-8 ''''' __AUthor__:沂水寒城功能:分糖果 ''' def split_candy(ra
Java基于JDBC连接数据库及显示数据操作示例

本文实例讲述了Java基于JDBC连接数据库及显示数据操作.分享给大家供大家参考,具体如下: 1. 导入jdbc包 java要连接MySQL数据库需要用到JDBC工具(mysql-connector-java-5.1.39-bin.jar),这是一个jar包,不同的数据库对应不同的jar包,这里用的是MySQL数据库jar包,导入很简单,鼠标对项目右击 - Build Path - Configure Build Path - 右侧选Libraries - Add External JARs,选
Java实现合并两个有序序列算法示例

本文实例讲述了Java实现合并两个有序序列算法.分享给大家供大家参考,具体如下: 问题描述输入:序列A<a0,a1,a2,...aq,aq+1,aq+2,...,ar>,其中a0<a1<...<aq,aq+1<aq+2<...<ar 输出:序列B<b0,b1,...,br>,其中b0<b1<...<br 算法思想创建一个长度为r的数组R,将A中的序列看作是两个有序序列 B=A<a0,a1,a2,...,aq> C
java实现的AES秘钥生成算法示例

本文实例讲述了java实现的AES秘钥生成算法.分享给大家供大家参考,具体如下: import java.security.NoSuchAlgorithmException; import java.security.SecureRandom; import javax.crypto.KeyGenerator; import javax.crypto.SecretKey; public class Test { public static void main(String[] args) { g
java基于移位操作实现二进制处理的方法示例

本文实例讲述了java基于移位操作实现二进制处理的方法.分享给大家供大家参考,具体如下: /** * @author openks * @since 2013-9-21 移位操作实例 */ public class TestDisplacement { /** * @param args */ public static void main(String[] args) { // 十进制数字2向左移3位即二进制的10向左移3位即10000 转换为十进制为2的4次方即16 System.ou
Java基于正则实现的日期校验功能示例

本文实例讲述了Java基于正则实现的日期校验功能.分享给大家供大家参考,具体如下: private void checkDate() throws IOException { // 4种分隔符 String sep = "[-\\./_]"; // 年份 String strPattern = "^(19[4-9]\\d|20\\d{2})" + sep; strPattern += "("; // 月(1,3,5,7,8,10,12) strP
PHP基于递归实现的约瑟夫环算法示例

本文实例讲述了PHP基于递归实现的约瑟夫环算法.分享给大家供大家参考,具体如下: 约瑟夫环问题: 39 个犹太人与Josephus及他的朋友躲到一个洞中,39个犹太人决定宁愿死也不要被敌人抓.于是决定了自杀方式,41个人排成一个圆圈,由第1个人开始报数,每报数到第3人该人就必须自杀.然后下一个重新报数,直到所有人都自杀身亡为止.然而Josephus 和他的朋友并不想遵从,Josephus要他的朋友先假装遵从,他将朋友与自己安排在第16个与第31个位置,于是逃过了这场死亡游戏. <?php $nu

Java基于分治法实现的快速排序算法示例

相关推荐

随机推荐