- 浏览: 177236 次
- 性别:
- 来自: 深圳
文章分类
- 全部博客 (99)
- 备忘录 (48)
- linux (19)
- oracle (10)
- shell (8)
- awk (1)
- java (48)
- just do it (29)
- more and more (46)
- common (29)
- 设计模式 (8)
- Java Web (9)
- Spring (0)
- Structs 2 (2)
- Java 高级 (4)
- 存储 (3)
- Virtual Box (1)
- ant (1)
- maven (0)
- 数据结构 (5)
- 算法 (5)
- javascript (1)
- ajax (1)
- jquery (1)
- xml (1)
- IBM (3)
- 转载 (3)
- English (2)
- html&css (0)
- hibernate (2)
- mysql (1)
- memcached (1)
最新评论
-
飞出四季做的茧:
kris_zhang 写道int temp = 0 ; ...
Java IO流 Zip文件的压缩和解压缩 -
kris_zhang:
int temp = 0 ; while(( ...
Java IO流 Zip文件的压缩和解压缩 -
welcomezhang:
学习了,这块自己还得深挖下
为什么HashMap不是线程安全的 -
fomeiherz:
这个写的最详细了,赞一个
Java的泛型类和泛型方法 -
beijishiqidu:
hanmiao 写道http://yangguangfu.it ...
Java设计模式之策略模式
快速排序使用分治法(Divide and conquer)策略来把一个串行(list)分为两个子串行(sub-lists)。
步骤为:
从数列中挑出一个元素,称为 "基准"(pivot),
重新排序数列,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面(相同的数可以到任一边)。在这个分区退出之后,该基准就处于数列的中间位置。这个称为分区(partition)操作。
递归地(recursive)把小于基准值元素的子数列和大于基准值元素的子数列排序。
递归的最底部情形,是数列的大小是零或一,也就是永远都已经被排序好了。虽然一直递归下去,但是这个算法总会退出,因为在每次的迭代(iteration)中,它至少会把一个元素摆到它最后的位置去。
该方法的白话基本思想是:
1.先从数列中取出一个数作为基准数。
2.分区过程,将比这个数大的数全放到它的右边,小于或等于它的数全放到它的左边。
3.再对左右区间重复第二步,直到各区间只有一个数。
一下代码来自维基百科
http://zh.wikipedia.org/wiki/%E5%BF%AB%E9%80%9F%E6%8E%92%E5%BA%8F
我实例了下上述代码便于理解:
另外一个仁兄给的巧妙的解答,用白话去描述其思想,很清晰,容易懂,作者迫不及待的转过来了。
上述代码的来源:http://www.cnblogs.com/morewindows/archive/2011/08/13/2137415.html
步骤为:
从数列中挑出一个元素,称为 "基准"(pivot),
重新排序数列,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面(相同的数可以到任一边)。在这个分区退出之后,该基准就处于数列的中间位置。这个称为分区(partition)操作。
递归地(recursive)把小于基准值元素的子数列和大于基准值元素的子数列排序。
递归的最底部情形,是数列的大小是零或一,也就是永远都已经被排序好了。虽然一直递归下去,但是这个算法总会退出,因为在每次的迭代(iteration)中,它至少会把一个元素摆到它最后的位置去。
该方法的白话基本思想是:
1.先从数列中取出一个数作为基准数。
2.分区过程,将比这个数大的数全放到它的右边,小于或等于它的数全放到它的左边。
3.再对左右区间重复第二步,直到各区间只有一个数。
一下代码来自维基百科
http://zh.wikipedia.org/wiki/%E5%BF%AB%E9%80%9F%E6%8E%92%E5%BA%8F
package com.fit.quick.sort; import java.util.Comparator; import java.util.Random; public class QuickSort { public static final Random RND = new Random(); private static void swap(Object[] array, int i, int j) { Object tmp = array[i]; array[i] = array[j]; array[j] = tmp; } private static <E> int partition(E[] array, int begin, int end, Comparator<? super E> cmp) { int index = begin + RND.nextInt(end - begin + 1); E pivot = array[index]; swap(array, index, end); for (int i = index = begin; i < end; ++i) { if (cmp.compare(array[i], pivot) <= 0) { swap(array, index++, i); } } swap(array, index, end); return (index); } private static <E> void qsort(E[] array, int begin, int end, Comparator<? super E> cmp) { if (end > begin) { int index = partition(array, begin, end, cmp); qsort(array, begin, index - 1, cmp); qsort(array, index + 1, end, cmp); } } public static <E> void sort(E[] array, Comparator<? super E> cmp) { qsort(array, 0, array.length - 1, cmp); } public static void print(Integer[] array) { StringBuffer sb = new StringBuffer("["); for (int i = 0; i < array.length; i++) { if (i < array.length - 1) { sb.append(array[i]).append(","); } else { sb.append(array[i]); } } sb.append("]"); System.out.println(sb); } public static void main(String[] args) { Integer[] array = new Integer[] { 54, 3, 11, 34, 12, 8, 19 }; print(array); System.out.println("====================="); sort(array, new Comparator<Object>() { @Override public int compare(Object o1, Object o2) { //return o1.compareTo(o2); if(o1 instanceof Integer && o2 instanceof Integer) { Integer temp_o1 = (Integer)o1; Integer temp_o2 = (Integer)o2; return temp_o1.compareTo(temp_o2); } return 0; } }); print(array); } }
我实例了下上述代码便于理解:
package com.fit.quick.sort; import java.util.Random; public class GeneralQuickSort { public static final Random RND = new Random(); public static void sort(int[] array) { qsort(array, 0, array.length - 1); } public static void qsort(int[] array, int begin, int end) { if (begin < end) { int index = partition(array, begin, end); qsort(array, begin, index - 1); qsort(array, begin + 1, end); } } private static int partition(int[] array, int begin, int end) { int index = begin + RND.nextInt(end - begin + 1); int pivot = array[index]; swap(array, index, end); for (int i = index = begin; i < end; ++i) { if (array[i] < pivot) { swap(array, index++, i); } } swap(array, index, end); // System.out.println("----"+array[index]+"----"); // print(array); return index; } private static void swap(int[] array, int i, int j) { int tmp = array[i]; array[i] = array[j]; array[j] = tmp; } public static void print(int[] array) { StringBuffer sb = new StringBuffer("["); for (int i = 0; i < array.length; i++) { if (i < array.length - 1) { sb.append(array[i]).append(","); } else { sb.append(array[i]); } } sb.append("]"); System.out.println(sb); } public static void main(String[] args) { int[] array = new int[] { 54, 3, 11, 34, 12, 8, 19 }; print(array); System.out.println("====================="); sort(array); print(array); } }
另外一个仁兄给的巧妙的解答,用白话去描述其思想,很清晰,容易懂,作者迫不及待的转过来了。
package com.fit.quick.sort; public class CopyOfGeneralQuickSort { public static void print(int[] array) { StringBuffer sb = new StringBuffer("["); for (int i = 0; i < array.length; i++) { if (i < array.length - 1) { sb.append(array[i]).append(","); } else { sb.append(array[i]); } } sb.append("]"); System.out.println(sb); } public static void sort1(int[] array) { quickSort1(array, 0, array.length - 1); } /** * 挖坑填数进行总结 1.i =L; j = R; 将基准数挖出形成第一个坑a[i]。 * 2.j--由后向前找比它小的数,找到后挖出此数填前一个坑a[i]中。 3.i++由前向后找比它大的数,找到后也挖出此数填到前一个坑a[j]中。 * 4.再重复执行2,3二步,直到i==j,将基准数填入a[i]中。 照着这个总结很容易实现挖坑填数的代码: * * @param s * @param l * @param r * @return */ public static int partition1(int[] s, int l, int r) { int x = s[l];// s[l]即s[i]就是第一个坑 int i = l; int j = r; while (i < j) { // 从右向左找小于x的数来填s[i] while (i < j && s[j] >= x) { j--; } if (i < j) { s[i] = s[j]; // 将s[j]填到s[i]中,s[j]就形成了一个新的坑 i++; } // 从左向右找大于或等于x的数来填s[j] while (i < j && s[i] < x) { i++; } if (i < j) { s[j] = s[i]; // 将s[i]填到s[j]中,s[i]就形成了一个新的坑 j--; } s[i] = x; } return i; } public static void quickSort1(int[] array, int l, int r) { if (l < r) { int index = partition1(array, l, r); quickSort1(array, l, index - 1); quickSort1(array, index + 1, r); } } public static void main(String[] args) { int[] array = new int[] { 54, 3, 11, 34, 12, 8, 19 }; print(array); System.out.println("====================="); sort1(array); print(array); } }
上述代码的来源:http://www.cnblogs.com/morewindows/archive/2011/08/13/2137415.html
发表评论
-
为什么HashMap不是线程安全的
2016-06-15 22:27 2203序 最近因为项目的需求,经常会面试一些新人,也就会问他们 ... -
JAVA读取文件夹大小的几种方法实例
2016-04-24 15:39 708总是发现自己的C盘快满了,清理程序也不会帮我自己清理,然后 ... -
Java Regex - Matcher (java.util.regex.Matcher)
2015-03-01 13:59 849The Java Matcher class (java. ... -
Java Regex - Pattern (java.util.regex.Pattern)
2015-03-01 11:22 1525Java中的Pattern类是Java正则表达式API ... -
eclipse中查看jdk的源码
2014-11-23 11:43 1009最近一段时间跟jdk源码打交道的比较多,但是有的时候却是看 ... -
Struts2学习初设系列(一)之环境搭建
2014-07-20 22:47 1069已经毕业很长时间了,回过头来想想都不知道自己做了什么,由于 ... -
算法的时间复杂度分析
2014-07-20 11:14 16412.9.1 算法时间复杂度定义 在进 ... -
解析 Java 类和对象的初始化过程
2014-07-06 18:14 643问题引入 近日我在调试一个枚举类型的解析器程序,该 ... -
Java 中正确使用 hashCode 和 equals 方法
2014-07-05 18:17 638在这篇文章中,我将告诉大家我对hashCode和equals ... -
通过分析 JDK 源代码研究 Hash 存储机制
2014-07-05 17:22 600集合和引用 就像引 ... -
NIO 入门
2014-07-05 17:15 633在开始之前 关于本教程 新的输入/输出 (NIO) 库 ... -
利用AJax方式提交和Webservice完成页面输入汉字简体字回显繁体字
2014-06-29 18:05 1133最近一直在学习新的 ... -
How To Parse XML File Using XPath In Java
2014-06-29 11:59 1294最近一直在学习XML的Xpath解析方式,据说是一个很简单 ... -
Java排序算法之简单选择排序
2014-06-21 22:31 753在网上搜索了很多的算法,貌似大家说的简单选择排序算法和直接选择 ... -
Java排序算法之冒泡排序
2014-06-21 20:22 981冒泡排序算法的基本思想是:首先将第n-1个记录的关键字和第n个 ... -
Java排序算法之直接插入排序
2014-06-21 19:33 1171直接插入排序算法的基本思想是:把n个待排序的元素看成为 ... -
JAVA之桥接模式
2014-05-26 20:11 0桥模式:将某个问题抽象的不同形式分别与该问题的具体实现 ... -
Java数字小写转换为大写
2014-05-11 11:52 1386闲来无事,在网上搜索了一些面试的题目,开始练习下,下列代码的作 ... -
Oracle SQL developer 报JVM错误解决和更换jdk
2014-05-03 20:35 0今日升级 Oracle SQL developer为2.1。发 ... -
多线程上机题
2014-04-08 23:46 951题目如下: 四个线程1,2,3,4. 线程1,2对变量i加一. ...
相关推荐
JAVA冒泡排序和快速排序算法,符合实验报告要求哦
详细解释了快速排序的java实现.里面有代码,还有注释说明
Java 快速排序,目前来说效率很高的一种排序算法,好理解。
java代码-使用java解决java排序之-快速排序的问题的源代码 ——学习参考资料:仅用于个人学习使用!
实现合并排序,插入排序,希尔排序,快速排序,冒泡排序,桶排序算法的java实现。
JAVA排序算法: 直接插入,希尔排序,选择排序,堆排序,冒泡排序,快速排序,归并排序,包括算法的详细介绍,以及对几种算法的详细测试
编写选择排序,插入排序,自顶向上合并排序,合并排序,快速排序,理解各排序算法的实现原理,加深对排序算法的理解。
一个简单的快速排序算法,用JAVA编写的
详解Java常用排序算法-快速排序
快速排序等经典排序算法C++、Java、python等版本 快速排序等经典排序算法C++、Java、python等版本 快速排序等经典排序算法C++、Java、python等版本 快速排序等经典排序算法C++、Java、python等版本 快速排序等经典...
1.插入排序(直接插入排序、折半插入排序、希尔排序); 2.交换排序(冒泡泡排序、快速排序); 3.选择排序(直接选择排序、堆排序); 4.归并排序; 5.基数排序
java算法,快速排序、冒泡排序、选择排序 快速排序文章:http://blog.csdn.net/yanwenyuan0304/article/details/51822361 冒泡排序文章:http://blog.csdn.net/yanwenyuan0304/article/details/51819045
这是一个用Java语言实现的快速排序算法,快速排序算法是根据分冶思想去实现的。
快速排序算法java代码,内附运行结果,望对大家有帮助,谢谢!
Java排序算法:插入,冒泡,选择,Shell,快速排序,归并排序,堆排序,桶式排序,基数排序
用java语言编写的排序算法,包括选择排序、插入排序、自底向上排序法、快速排序法等四种排序算法
该工具包含有Java一些比较常见的排序算法和查找算法。 排序算法包括:冒泡排序、选择排序 、插入排序、希尔排序、快速排序、归并排序、基数排序(桶排序) 查找算法包括:线性查找、二分查找、插值查询、斐波那契...
快速排序方法...给新手一点指引,内置快速排序方法,有详细解析的链接地址,免费的
java实现的快速排序算法
java 快速排序 折半查找的界面实现 (递归与分治法)