java 算法之快速排序实现代码

java 算法之快速排序实现代码

摘要: 常用算法之一的快速排序算法的java实现

原理：选择一个基准元素,通常选择第一个元素或者最后一个元素,通过一趟扫描， 将待排序列分成两部分,一部分比基准元素小,一部分大于等于基准元素, 此时基准元素在其排好序后的正确位置,然后再用同样的方法递归地排序划分的两部分。

  /**
   *
   * @author 阿信sxq-2015年7月16日
   *
   * @param args
   */
  public static void main(String[] args) {
    int a[] = { 49, 38, 65, 97, 76, 13, 27, 49, 78, 34, 12, 64, 5, 4,
        62, 99, 98, 54, 56, 17, 18, 23, 34, 15, 35, 25, 53, 51 };
    if (a.length > 0) {//查看数组是否为空
      _quickSort(a, 0, a.length - 1);
    }
    System.out.println(Arrays.toString(a));

  }

  public static void _quickSort(int[] arr, int left, int right) {
    if (left >= right) {
      return;
    }
    int low = left;
    int high = right;
    int tmp = arr[low];//数组的第一个作为中轴
    while (low < high) {
      while (low < high && arr[high] >= tmp) {
        high--;
      }
      arr[low] = arr[high];//比中轴小的记录移到低端  

      while (low < high && arr[low] <= tmp) {
        low++;
      }
      arr[high] = arr[low];//比中轴大的记录移到高端
    }
    arr[low] = tmp;//中轴记录到尾
    _quickSort(arr, left, low - 1);//对低字表进行递归排序
    _quickSort(arr, low + 1, right);//对高字表进行递归排序
  }

感谢阅读，希望能帮助到大家，谢谢大家对本站的支持！

赞 (0)

相关推荐

  • java数据结构与算法之希尔排序详解

    本文实例讲述了java数据结构与算法之希尔排序.分享给大家供大家参考,具体如下: 这里要介绍的是希尔排序(缩小增量排序法). 希尔排序:通过比较相距一定间隔的元素来工作:各趟比较所用的距离(增量)随着算法的进行而减小,直到只比较相邻元素的最后一趟排序为止.是插入排序的一种,是针对直接插入排序算法的改进. 算法思想:先将要排序的序列按某个增量d分成若干个子序列,对每个子序列中全部元素分别进行直接插入排序,然后再用一个较小的增量对它进行分组,在每组中再进行排序.当增量减到1时,整个要排序的数被分成一

  • java数据结构与算法之快速排序详解

    本文实例讲述了java数据结构与算法之快速排序.分享给大家供大家参考,具体如下: 交换类排序的另一个方法,即快速排序. 快速排序:改变了冒泡排序中一次交换仅能消除一个逆序的局限性,是冒泡排序的一种改进:实现了一次交换可消除多个逆序.通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列. 步骤: 1.从数列中挑出一个元素,称为 "基准"(piv

  • java数据结构与算法之插入排序详解

    本文实例讲述了java数据结构与算法之插入排序.分享给大家供大家参考,具体如下: 复习之余,就将数据结构中关于排序的这块知识点整理了一下,写下来是想与更多的人分享,最关键的是做一备份,为方便以后查阅. 排序 1.概念: 有n个记录的序列{R1,R2,.......,Rn}(此处注意:1,2,n 是下表序列,以下是相同的作用),其相应关键字的序列是{K1,K2,.........,Kn}.通过排序,要求找出当前下标序列1,2,......,n的一种排列p1,p2,........pn,使得相应关键

  • Java 归并排序算法、堆排序算法实例详解

    Java 归并排序算法、堆排序算法实例详解

    基本思想: 归并(Merge)排序法是将两个(或两个以上)有序表合并成一个新的有序表,即把待排序序列分为若干个子序列,每个子序列是有序的.然后再把有序子序列合并为整体有序序列. 归并排序示例: 合并方法: 设r[i-n]由两个有序子表r[i-m]和r[m+1-n]组成,两个子表长度分别为n-i +1.n-m. j=m+1:k=i:i=i; //置两个子表的起始下标及辅助数组的起始下标 若i>m 或j>n,转⑷ //其中一个子表已合并完,比较选取结束 //选取r[i]和r[j]较小的存入辅助数组

  • Java 选择排序、插入排序、希尔算法实例详解

    Java 选择排序、插入排序、希尔算法实例详解

    1.基本思想: 在要排序的一组数中,选出最小的一个数与第一个位置的数交换:然后在剩下的数当中再找最小的与第二个位置的数交换,如此循环到倒数第二个数和最后一个数比较为止. 2.实例 3.算法实现 /** * 选择排序算法 * 在未排序序列中找到最小元素,存放到排序序列的起始位置 * 再从剩余未排序元素中继续寻找最小元素,然后放到排序序列末尾. * 以此类推,直到所有元素均排序完毕. * @param numbers */ public static void selectSort(int[] nu

  • java算法导论之FloydWarshall算法实现代码

    摘要: 算法导论之FloydWarshall算法 求一个图中任意两点之间的最短路径 FloydWarshall算法是通过动态规划来计算任意两点之间的最短路径 如果普通求最短路径,可以对图进行V次(顶点数)BellmanFord算法. 这样的话时间复杂度为EV^2 如果是稀疏图,则近似于V^3 但是如果是密集图,则时间复杂度会近似达到V^4,这种情况需要优化,这里FloydWarshall通过动态规划进行优化 ,并且使用邻接矩阵来表示图. 实例代码: package org.loda.graph;

  • java数据结构与算法之简单选择排序详解

    本文实例讲述了java数据结构与算法之简单选择排序.分享给大家供大家参考,具体如下: 在前面的文章中已经讲述了交换类的排序算法,这节中开始说说选择类的排序算法了,首先来看一下选择排序的算法思想: 选择排序的基本算法思想: 每一趟在 n-i+1 (i=1,2,3,--,n-1)个记录中选取关键字最小的记录作为有序序列中第i个记录. 简单选择排序: 设所排序序列的记录个数为n.i取1,2,-,n-1,从所有n-i+1个记录(Ri,Ri+1,-,Rn)中找出排序码最小的记录,与第i个记录交换.执行n-

  • java 基本算法之归并排序实例代码

    java 基本算法之归并排序实例代码 原理:归并(Merge)排序法是将两个(或两个以上)有序表合并成一个新的有序表, * 即把待排序序列分为若干个子序列,每个子序列是有序的.      * 然后再把有序子序列合并为整体有序序列. 实例代码: public class MergeSort { /** * * * * @param args */ public static void main(String[] args) { int a[] = { 49, 38, 65, 97, 76, 13,

  • java 算法之快速排序实现代码

    java 算法之快速排序实现代码 摘要: 常用算法之一的快速排序算法的java实现 原理:选择一个基准元素,通常选择第一个元素或者最后一个元素,通过一趟扫描, 将待排序列分成两部分,一部分比基准元素小,一部分大于等于基准元素, 此时基准元素在其排好序后的正确位置,然后再用同样的方法递归地排序划分的两部分. /** * * @author 阿信sxq-2015年7月16日 * * @param args */ public static void main(String[] args) { int

  • Java 冒泡排序、快速排序实例代码

    冒泡排序 冒泡排序是一种简单的排序算法.它重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来.走访数列的工作是重复地 进行直到没有再需要交换,也就是说该数列已经排序完成.这个算法的名字由来是因为越小的元素会经由交换慢慢"浮"到数列的顶端. 冒泡排序的算法实现如下:[排序后,数组从小到大排列] /** * 冒泡排序 * 比较相邻的元素.如果第一个比第二个大,就交换他们两个. * 对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对.在这一点,最后的元素应

  • Java算法之数组冒泡排序代码实例讲解

    冒泡排序是数组查找算法中最为简单的算法 冒泡排序原理: 假设一个数组长度为k(最高索引k-1),遍历前k - 1个(最高索引k-2)元素,若数组中的元素a[i]都与相邻的下一个元素a[i+1]进行比较,若a[i] > a[i+1] ,则这两个元素交换位置.以此类推,若a[i+1] > a[i+2],则交换位置-直至a[k-2]与a[k-1]比较完毕后,第0轮迭代结束.此时,a[k-1]为数组元素中的最大值. 第1轮迭代,再对数组a的前k-1个元素重复进行以上操作. - 第k-2轮迭代,对数组a

  • Java算法之冒泡排序实例代码

    Java算法之冒泡排序实例代码

    java算法-冒泡排序练习 所谓冒泡就是一堆数据相邻的互相比较,把大的数据往后移,小的数据往前移. 百度上找了张图 大家自己想一想这个逻辑 想明白了,直接看代码. public class Two { public static void main(String[] args) { int arg[] = {25,36,15,274}; sort(arg); } private static void sort(int[] array) { for (int j = 1; j < array.l

  • Java编程基于快速排序的三个算法题实例代码

    快速排序原理简介 快速排序是我们之前学习的冒泡排序的升级,他们都属于交换类排序,都是采用不断的比较和移动来实现排序的.快速排序是一种非常高效的排序算法,它的实现,增大了记录的比较和移动的距离,将关键字较大的记录从前面直接移动到后面,关键字较小的记录从后面直接移动到前面,从而减少了总的比较次数和移动次数.同时采用"分而治之"的思想,把大的拆分为小的,小的拆分为更小的,其原理如下:对于给定的一组记录,选择一个基准元素,通常选择第一个元素或者最后一个元素,通过一趟扫描,将待排序列分成两部分,

  • 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算法之堆排序代码示例

    堆是一种特殊的完全二叉树,其特点是所有父节点都比子节点要小,或者所有父节点都比字节点要大.前一种称为最小堆,后一种称为最大堆. 比如下面这两个: 那么这个特性有什么作用?既然题目是堆排序,那么肯定能用来排序.想要用堆排序首先要创建一个堆,如果对4 3 6 2 7 1 5这七个数字做从小到大排序,需要用这七个数创建一个最大堆,来看代码: public class HeapSort { private int[] numbers; private int length; public HeapSor

  • 详解Java双轴快速排序算法

    详解Java双轴快速排序算法

    目录 一.前言 二.回顾单轴快排 三.双轴快排分析 3.1.总体情况分析 3.2.k交换过程 3.3.收尾工作 四.双轴快排代码 一.前言 首选,双轴快排也是一种快排的优化方案,在JDK的Arrays.sort()中被主要使用.所以,掌握快排已经不能够满足我们的需求,我们还要学会双轴快排的原理和实现才行. 二.回顾单轴快排 单轴快排也就是我们常说的普通快速排序,对于快速排序我想大家应该都很熟悉:基于递归和分治的,时间复杂度最坏而O(n2),最好和平均情况为O(nlogn). 而快排的具体思路也很

  • java 排序算法之快速排序

    java 排序算法之快速排序

    目录 简单介绍 基本思想 思路分析 代码实现 推导实现 完整实现 大数据量耗时测试 性能分析 简单介绍 快速排序(Quicksort) 是对 冒泡排序的一种改进. 基本思想 快速排序算法通过多次比较和交换来实现排序,其排序流程如下: (1)首先设定一个分界值(基准值),通过该分界值将数组分成左右两部分. (2)将大于或等于分界值的数据集中到数组右边,小于分界值的数据集中到数组的左边.此时,左边部分中各元素都小于或等于分界值,而右边部分中各元素都大于或等于分界值. (3)然后,左边和右边的数据可以

随机推荐