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);//对高字表进行递归排序 }
感谢阅读,希望能帮助到大家,谢谢大家对本站的支持!
相关推荐
-
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.概念: 有n个记录的序列{R1,R2,.......,Rn}(此处注意:1,2,n 是下表序列,以下是相同的作用),其相应关键字的序列是{K1,K2,.........,Kn}.通过排序,要求找出当前下标序列1,2,......,n的一种排列p1,p2,........pn,使得相应关键
-
java数据结构与算法之快速排序详解
本文实例讲述了java数据结构与算法之快速排序.分享给大家供大家参考,具体如下: 交换类排序的另一个方法,即快速排序. 快速排序:改变了冒泡排序中一次交换仅能消除一个逆序的局限性,是冒泡排序的一种改进:实现了一次交换可消除多个逆序.通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列. 步骤: 1.从数列中挑出一个元素,称为 "基准"(piv
-
Java 选择排序、插入排序、希尔算法实例详解
1.基本思想: 在要排序的一组数中,选出最小的一个数与第一个位置的数交换:然后在剩下的数当中再找最小的与第二个位置的数交换,如此循环到倒数第二个数和最后一个数比较为止. 2.实例 3.算法实现 /** * 选择排序算法 * 在未排序序列中找到最小元素,存放到排序序列的起始位置 * 再从剩余未排序元素中继续寻找最小元素,然后放到排序序列末尾. * 以此类推,直到所有元素均排序完毕. * @param numbers */ public static void selectSort(int[] nu
-
java 基本算法之归并排序实例代码
java 基本算法之归并排序实例代码 原理:归并(Merge)排序法是将两个(或两个以上)有序表合并成一个新的有序表, * 即把待排序序列分为若干个子序列,每个子序列是有序的. * 然后再把有序子序列合并为整体有序序列. 实例代码: public class MergeSort { /** * * * * @param args */ public static void main(String[] args) { int a[] = { 49, 38, 65, 97, 76, 13,
-
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算法导论之FloydWarshall算法实现代码
摘要: 算法导论之FloydWarshall算法 求一个图中任意两点之间的最短路径 FloydWarshall算法是通过动态规划来计算任意两点之间的最短路径 如果普通求最短路径,可以对图进行V次(顶点数)BellmanFord算法. 这样的话时间复杂度为EV^2 如果是稀疏图,则近似于V^3 但是如果是密集图,则时间复杂度会近似达到V^4,这种情况需要优化,这里FloydWarshall通过动态规划进行优化 ,并且使用邻接矩阵来表示图. 实例代码: package org.loda.graph;
-
java数据结构与算法之希尔排序详解
本文实例讲述了java数据结构与算法之希尔排序.分享给大家供大家参考,具体如下: 这里要介绍的是希尔排序(缩小增量排序法). 希尔排序:通过比较相距一定间隔的元素来工作:各趟比较所用的距离(增量)随着算法的进行而减小,直到只比较相邻元素的最后一趟排序为止.是插入排序的一种,是针对直接插入排序算法的改进. 算法思想:先将要排序的序列按某个增量d分成若干个子序列,对每个子序列中全部元素分别进行直接插入排序,然后再用一个较小的增量对它进行分组,在每组中再进行排序.当增量减到1时,整个要排序的数被分成一
-
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算法-冒泡排序练习 所谓冒泡就是一堆数据相邻的互相比较,把大的数据往后移,小的数据往前移. 百度上找了张图 大家自己想一想这个逻辑 想明白了,直接看代码. 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实现快速排序算法可视化的示例代码
实现效果 示例代码 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算法之堆排序代码示例
堆是一种特殊的完全二叉树,其特点是所有父节点都比子节点要小,或者所有父节点都比字节点要大.前一种称为最小堆,后一种称为最大堆. 比如下面这两个: 那么这个特性有什么作用?既然题目是堆排序,那么肯定能用来排序.想要用堆排序首先要创建一个堆,如果对4 3 6 2 7 1 5这七个数字做从小到大排序,需要用这七个数创建一个最大堆,来看代码: public class HeapSort { private int[] numbers; private int length; public HeapSor
-
详解Java双轴快速排序算法
目录 一.前言 二.回顾单轴快排 三.双轴快排分析 3.1.总体情况分析 3.2.k交换过程 3.3.收尾工作 四.双轴快排代码 一.前言 首选,双轴快排也是一种快排的优化方案,在JDK的Arrays.sort()中被主要使用.所以,掌握快排已经不能够满足我们的需求,我们还要学会双轴快排的原理和实现才行. 二.回顾单轴快排 单轴快排也就是我们常说的普通快速排序,对于快速排序我想大家应该都很熟悉:基于递归和分治的,时间复杂度最坏而O(n2),最好和平均情况为O(nlogn). 而快排的具体思路也很
-
java 排序算法之快速排序
目录 简单介绍 基本思想 思路分析 代码实现 推导实现 完整实现 大数据量耗时测试 性能分析 简单介绍 快速排序(Quicksort) 是对 冒泡排序的一种改进. 基本思想 快速排序算法通过多次比较和交换来实现排序,其排序流程如下: (1)首先设定一个分界值(基准值),通过该分界值将数组分成左右两部分. (2)将大于或等于分界值的数据集中到数组右边,小于分界值的数据集中到数组的左边.此时,左边部分中各元素都小于或等于分界值,而右边部分中各元素都大于或等于分界值. (3)然后,左边和右边的数据可以
随机推荐
- JSONP原理及简单实现
- 基于Angular.js实现的触摸滑动动画实例代码
- java8 集合之Stack详解及实例
- 基于oracle小数点前零丢失的问题分析
- 深入理解PHP之数组(遍历顺序) Laruence原创
- 重新应用默认的安全设置 : 安全配置和分析
- 详解C语言中结构体的自引用和相互引用
- 从零开始学习jQuery (二) 万能的选择器
- 【经典源码收藏】基于jQuery的项目常见函数封装集合
- Android中使用Intent在Activity之间传递对象(使用Serializable或者Parcelable)的方法
- serv-u安全配置完整版
- linux配置jdk环境变量简单教程
- 浅谈C#各种数组直接的数据复制/转换
- 路由选择协议 Routing Protocols
- Android绘图之Paint的使用方法详解
- Python爬虫实现验证码登录代码实例
- 一步一步跟我学易语言之判断与选择
- PHP进阶学习之类的自动加载机制原理分析
- 解决python super()调用多重继承函数的问题
- mysql本地登录无法使用端口号登录的解决方法