HkEndless
- 浏览: 93056 次
- 性别:
- 来自: 上海
-
文章分类
- 全部博客 (133)
- jQuery (11)
- XML (3)
- 组件 (1)
- JAVA (20)
- WEB (3)
- SPRING (6)
- HIBERNATE (5)
- AJAX (2)
- JS (1)
- JAVA webservice (1)
- Ditu (1)
- WEBSITE (1)
- HIBERNATE ANNOTATION (1)
- 排序 (1)
- TCP_NODELAY (1)
- ConvertUtils (1)
- Logistics (1)
- SQL SERVER 中identity (4)
- sql server (35)
- MYSQL (1)
- Eclipse (6)
- ORACLE (6)
- FLEX (4)
- notepad++ (0)
- UNION ALL (1)
- JUnit (3)
- SQL 异常处理 (1)
- @@trancount (1)
- IOS (1)
- ORA-02266 (1)
- REMOTE DESKTOP (0)
- HTML 优化 (1)
- CRLF (1)
- SQL Server Sequence (1)
最新评论
-
zjuttsw：
看的舒服
重要的hashcode equals转载
http://java.chinaitlab.com/advance/910025_2.html
Java代码
1.插入排序:
2.
3.1.package org.rut.util.algorithm.support;
4.2.import org.rut.util.algorithm.SortUtil;
5.3.4.public class InsertSort implements SortUtil.Sort{
6.5. /* (non-Javadoc)
7.6. * @see org.rut.util.algorithm.SortUtil.Sort#sort(int[])
8.7. */
9.8. public void sort(int[] data) {
10.9. int temp;
11.10. for(int i=1;i<data.length;i++){
12.11. for(int j=i;(j>0)&&(data[j]<data[j-1]);j--){
13.12. SortUtil.swap(data,j,j-1);
14.13. }
15.14. }
16.15. }
17.16.}
18.17.冒泡排序:
19.
20.1.package org.rut.util.algorithm.support;
21.2.import org.rut.util.algorithm.SortUtil;
22.3.4.public class BubbleSort implements SortUtil.Sort{
23.5. /* (non-Javadoc)
24.6. * @see org.rut.util.algorithm.SortUtil.Sort#sort(int[])
25.7. */
26.8. public void sort(int[] data) {
27.9. int temp;
28.10. for(int i=0;i<data.length;i++){
29.11. for(int j=data.length-1;j>i;j--){
30.12. if(data[j]<data[j-1]){
31.13. SortUtil.swap(data,j,j-1);
32.14. }
33.15. }
34.16. }
35.17. }
36.18.}
37.19.选择排序:
38.1.package org.rut.util.algorithm.support;
39.2.import org.rut.util.algorithm.SortUtil;
40.3.4.public class SelectionSort implements SortUtil.Sort {
41.5. /*
42.6. * (non-Javadoc)
43.7. *
44.8. * @see org.rut.util.algorithm.SortUtil.Sort#sort(int[])
45.9. */
46.10. public void sort(int[] data) {
47.11. int temp;
48.12. for (int i = 0; i < data.length; i++) {
49.13. int lowIndex = i;
50.14. for (int j = data.length - 1; j > i; j--) {
51.15. if (data[j] < data[lowIndex]) {
52.16. lowIndex = j;
53.17. }
54.18. }
55.19. SortUtil.swap(data,i,lowIndex);
56.20. }
57.21. }
58.22.}
59.23.Shell排序:
60.1.package org.rut.util.algorithm.support;
61.2.import org.rut.util.algorithm.SortUtil;
62.3.4.public class ShellSort implements SortUtil.Sort{
63.5. /* (non-Javadoc)
64.6. * @see org.rut.util.algorithm.SortUtil.Sort#sort(int[])
65.7. */
66.8. public void sort(int[] data) {
67.9. for(int i=data.length/2;i>2;i/=2){
68.10. for(int j=0;j<i;j++){
69.11. insertSort(data,j,i);
70.12. }
71.13. }
72.14. insertSort(data,0,1);
73.15. }
74.16. /**
75.17. * @param data
76.18. * @param j
77.19. * @param i
78.20. */
79.21. private void insertSort(int[] data, int start, int inc) {
80.22. int temp;
81.23. for(int i=start+inc;i<data.length;i+=inc){
82.24. for(int j=i;(j>=inc)&&(data[j]<data[j-inc]);j-=inc){
83.25. SortUtil.swap(data,j,j-inc);
84.26. }
85.27. }
86.28. }
87.29.}
88.30.快速排序:
89.1.package org.rut.util.algorithm.support;
90.2.import org.rut.util.algorithm.SortUtil;
91.3.4.public class QuickSort implements SortUtil.Sort{
92.5. /* (non-Javadoc)
93.6. * @see org.rut.util.algorithm.SortUtil.Sort#sort(int[])
94.7. */
95.8. public void sort(int[] data) {
96.9. quickSort(data,0,data.length-1);
97.10. }
98.11. private void quickSort(int[] data,int i,int j){
99.12. int pivotIndex=(i+j)/2;
100.13. //swap 14. SortUtil.swap(data,pivotIndex,j);
101.15.
102.16. int k=partition(data,i-1,j,data[j]);
103.17. SortUtil.swap(data,k,j);
104.18. if((k-i)>1) quickSort(data,i,k-1);
105.19. if((j-k)>1) quickSort(data,k+1,j);
106.20.
107.21. }
108.22. /**
109.23. * @param data
110.24. * @param i
111.25. * @param j
112.26. * @return
113.27. */
114.28. private int partition(int[] data, int l, int r,int pivot) {
115.29. do{
116.30. while(data[++l]<pivot);
117.31. while((r!=0)&&data[--r]>pivot);
118.32. SortUtil.swap(data,l,r);
119.33. }
120.34. while(l<r);
121.35. SortUtil.swap(data,l,r);
122.36. return l;
123.37. }
124.38.}
125.39.改进后的快速排序:
126.1.package org.rut.util.algorithm.support;
127.2.import org.rut.util.algorithm.SortUtil;
128.3.4.public class ImprovedQuickSort implements SortUtil.Sort {
129.5. private static int MAX_STACK_SIZE=4096;
130.6. private static int THRESHOLD=10;
131.7. /* (non-Javadoc)
132.8. * @see org.rut.util.algorithm.SortUtil.Sort#sort(int[])
133.9. */
134.10. public void sort(int[] data) {
135.11. int[] stack=new int[MAX_STACK_SIZE];
136.12.
137.13. int top=-1;
138.14. int pivot;
139.15. int pivotIndex,l,r;
140.16.
141.17. stack[++top]=0;
142.18. stack[++top]=data.length-1;
143.19.
144.20. while(top>0){
145.21. int j=stack[top--];
146.22. int i=stack[top--];
147.23.
148.24. pivotIndex=(i+j)/2;
149.25. pivot=data[pivotIndex];
150.26.
151.27. SortUtil.swap(data,pivotIndex,j);
152.28.
153.29. //partition 30. l=i-1;
154.31. r=j;
155.32. do{
156.33. while(data[++l]<pivot);
157.34. while((r!=0)&&(data[--r]>pivot));
158.35. SortUtil.swap(data,l,r);
159.36. }
160.37. while(l<r);
161.38. SortUtil.swap(data,l,r);
162.39. SortUtil.swap(data,l,j);
163.40.
164.41. if((l-i)>THRESHOLD){
165.42. stack[++top]=i;
166.43. stack[++top]=l-1;
167.44. }
168.45. if((j-l)>THRESHOLD){
169.46. stack[++top]=l+1;
170.47. stack[++top]=j;
171.48. }
172.49.
173.50. }
174.51. //new InsertSort().sort(data); 52. insertSort(data);
175.53. }
176.54. /**
177.55. * @param data
178.56. */
179.57. private void insertSort(int[] data) {
180.58. int temp;
181.59. for(int i=1;i<data.length;i++){
182.60. for(int j=i;(j>0)&&(data[j]<data[j-1]);j--){
183.61. SortUtil.swap(data,j,j-1);
184.62. }
185.63. }
186.64. }
187.65.}
188.66.归并排序:
189.1.package org.rut.util.algorithm.support;
190.2.import org.rut.util.algorithm.SortUtil;
191.3.4.public class MergeSort implements SortUtil.Sort{
192.5. /* (non-Javadoc)
193.6. * @see org.rut.util.algorithm.SortUtil.Sort#sort(int[])
194.7. */
195.8. public void sort(int[] data) {
196.9. int[] temp=new int[data.length];
197.10. mergeSort(data,temp,0,data.length-1);
198.11. }
199.12.
200.13. private void mergeSort(int[] data,int[] temp,int l,int r){
201.14. int mid=(l+r)/2;
202.15. if(l==r) return ;
203.16. mergeSort(data,temp,l,mid);
204.17. mergeSort(data,temp,mid+1,r);
205.18. for(int i=l;i<=r;i++){
206.19. temp[i]=data[i];
207.20. }
208.21. int i1=l;
209.22. int i2=mid+1;
210.23. for(int cur=l;cur<=r;cur++){
211.24. if(i1==mid+1)
212.25. data[cur]=temp[i2++];
213.26. else if(i2>r)
214.27. data[cur]=temp[i1++];
215.28. else if(temp[i1]<temp[i2])
216.29. data[cur]=temp[i1++];
217.30. else
218.31. data[cur]=temp[i2++];
219.32. }
220.33. }
221.34.}
222.35.改进后的归并排序:
223.
224.1.package org.rut.util.algorithm.support;
225.2.import org.rut.util.algorithm.SortUtil;
226.3.4.public class ImprovedMergeSort implements SortUtil.Sort {
227.5. private static final int THRESHOLD = 10;
228.6. /*
229.7. * (non-Javadoc)
230.8. *
231.9. * @see org.rut.util.algorithm.SortUtil.Sort#sort(int[])
232.10. */
233.11. public void sort(int[] data) {
234.12. int[] temp=new int[data.length];
235.13. mergeSort(data,temp,0,data.length-1);
236.14. }
237.15. private void mergeSort(int[] data, int[] temp, int l, int r) {
238.16. int i, j, k;
239.17. int mid = (l + r) / 2;
240.18. if (l == r)
241.19. return;
242.20. if ((mid - l) >= THRESHOLD)
243.21. mergeSort(data, temp, l, mid);
244.22. else
245.23. insertSort(data, l, mid - l + 1);
246.24. if ((r - mid) > THRESHOLD)
247.25. mergeSort(data, temp, mid + 1, r);
248.26. else
249.27. insertSort(data, mid + 1, r - mid);
250.28. for (i = l; i <= mid; i++) {
251.29. temp[i] = data[i];
252.30. }
253.31. for (j = 1; j <= r - mid; j++) {
254.32. temp[r - j + 1] = data[j + mid];
255.33. }
256.34. int a = temp[l];
257.35. int b = temp[r];
258.36. for (i = l, j = r, k = l; k <= r; k++) {
259.37. if (a < b) {
260.38. data[k] = temp[i++];
261.39. a = temp[i];
262.40. } else {
263.41. data[k] = temp[j--];
264.42. b = temp[j];
265.43. }
266.44. }
267.45. }
268.46. /**
269.47. * @param data
270.48. * @param l
271.49. * @param i
272.50. */
273.51. private void insertSort(int[] data, int start, int len) {
274.52. for(int i=start+1;i<start+len;i++){
275.53. for(int j=i;(j>start) && data[j]<data[j-1];j--){
276.54. SortUtil.swap(data,j,j-1);
277.55. }
278.56. }
279.57. }
280.58.}
281.59.堆排序:
282.1.package org.rut.util.algorithm.support;
283.2.import org.rut.util.algorithm.SortUtil;
284.3.4.public class HeapSort implements SortUtil.Sort{
285.5. /* (non-Javadoc)
286.6. * @see org.rut.util.algorithm.SortUtil.Sort#sort(int[])
287.7. */
288.8. public void sort(int[] data) {
289.9. MaxHeap h=new MaxHeap();
290.10. h.init(data);
291.11. for(int i=0;i<data.length;i++)
292.12. h.remove();
293.13. System.arraycopy(h.queue,1,data,0,data.length);
294.14. }
295.15.16. private static class MaxHeap{
296.17.
297.18.
298.19. void init(int[] data){
299.20. this.queue=new int[data.length+1];
300.21. for(int i=0;i<data.length;i++){
301.22. queue[++size]=data[i];
302.23. fixUp(size);
303.24. }
304.25. }
305.26.
306.27. private int size=0;
307.28. private int[] queue;
308.29.
309.30. public int get() {
310.31. return queue[1];
311.32. }
312.33. public void remove() {
313.34. SortUtil.swap(queue,1,size--);
314.35. fixDown(1);
315.36. }
316.37. //fixdown 38. private void fixDown(int k) {
317.39. int j;
318.40. while ((j = k << 1) <= size) {
319.41. if (j < size && queue[j]<queue[j+1])
320.42. j++;
321.43. if (queue[k]>queue[j]) //不用交换 44. break;
322.45. SortUtil.swap(queue,j,k);
323.46. k = j;
324.47. }
325.48. }
326.49. private void fixUp(int k) {
327.50. while (k > 1) {
328.51. int j = k >> 1;
329.52. if (queue[j]>queue[k])
330.53. break;
331.54. SortUtil.swap(queue,j,k);
332.55. k = j;
333.56. }
334.57. }
335.58. }
336.59.}
337.60.SortUtil:
338.1.package org.rut.util.algorithm;
339.2.import org.rut.util.algorithm.support.BubbleSort;
340.3.import org.rut.util.algorithm.support.HeapSort;
341.4.import org.rut.util.algorithm.support.ImprovedMergeSort;
342.5.import org.rut.util.algorithm.support.ImprovedQuickSort;
343.6.import org.rut.util.algorithm.support.InsertSort;
344.7.import org.rut.util.algorithm.support.MergeSort;
345.8.import org.rut.util.algorithm.support.QuickSort;
346.9.import org.rut.util.algorithm.support.SelectionSort;
347.10.import org.rut.util.algorithm.support.ShellSort;
348.11.12.public class SortUtil {
349.13. public final static int INSERT = 1;
350.14. public final static int BUBBLE = 2;
351.15. public final static int SELECTION = 3;
352.16. public final static int SHELL = 4;
353.17. public final static int QUICK = 5;
354.18. public final static int IMPROVED_QUICK = 6;
355.19. public final static int MERGE = 7;
356.20. public final static int IMPROVED_MERGE = 8;
357.21. public final static int HEAP = 9;
358.22. public static void sort(int[] data) {
359.23. sort(data, IMPROVED_QUICK);
360.24. }
361.25. private static String[] name={
362.26. “insert”,“bubble”,“selection”,“shell”,“quick”,“improved_quick”,“merge”,“improved_merge”,“heap”
363.27. };
364.28.
365.29. private static Sort[] impl=new Sort[]{
366.30. new InsertSort(),
367.31. new BubbleSort(),
368.32. new SelectionSort(),
369.33. new ShellSort(),
370.34. new QuickSort(),
371.35. new ImprovedQuickSort(),
372.36. new MergeSort(),
373.37. new ImprovedMergeSort(),
374.38. new HeapSort()
375.39. };
376.40. public static String toString(int algorithm){
377.41. return name[algorithm-1];
378.42. }
379.43.
380.44. public static void sort(int[] data, int algorithm) {
381.45. impl[algorithm-1].sort(data);
382.46. }
383.47. public static interface Sort {
384.48. public void sort(int[] data);
385.49. }
386.50. public static void swap(int[] data, int i, int j) {
387.51. int temp = data[i];
388.52. data[i] = data[j];
389.53. data[j] = temp;
390.54. }
391.55.}
分享到：
发表评论
-
JAVA 的checked异常和unchecked异常
2015-03-03 17:23 610JAVA 的checked异常和unchecked异常 (20 ... -
good upload
2013-08-01 12:48 330http://spring-geli.iteye.com/bl ... -
文件上传
2013-08-01 12:01 245http://zhangjunhd.blog.51cto.co ... -
错序死锁（Locking-ordering deadlock）
2013-07-31 15:15 652错序死锁（Locking-ordering deadlock） ... -
collection排序
2013-06-17 16:52 487http://www.cnblogs.com/huangfox ... -
ServerSocket 与 Socket的区别
2013-04-03 08:08 648http://www.cnblogs.com/mareymar ... -
java基础：关于java流与文件操作
2013-04-03 00:36 631http://www.blogjava.net/haizhig ... -
NumberFormatException异常
2013-03-17 21:48 9851. 对应String类型的对象 ... -
Heep and Stack
2013-02-20 16:52 561java中堆（heap)和堆栈（s ... -
Java中HashMap的工作机制
2013-01-12 19:50 0http://java.chinaitlab.com/adva ... -
java中去掉字符串中间的空格
2013-01-12 19:23 8981.JAVA中去掉空格 2. 3.1. S ... -
Java中的克隆(Clone)机制
2013-01-12 19:19 596http://java.chinaitlab.com/adva ... -
java设计模式示例
2013-01-12 19:13 739http://blog.csdn.net/chmask/art ... -
Thread
2013-01-12 18:20 665Java:使用wait()与notify()实现线程间协作 2 ... -
hashCode equal避免的几个误区
2012-12-28 11:45 1809对于hashcode方法和equals ... -
重要的hashcode equals转载
2012-12-28 10:26 732http://www.iteye.com/topic/2571 ... -
JAVA HashCode
2012-12-28 10:14 622http://www.cnblogs.com/batys/ar ... -
java bingfa
2012-12-27 14:29 690http://www.iteye.com/topic/3665 ... -
Good book about java
2012-12-27 14:05 555http://extjs2.iteye.com/blog/79 ... -
内部类
2012-12-04 18:51 755Java代码 内部类的分类：成员内部类，静态内部类，局部内 ...
相关推荐
完整版 Java高级教程 Java语言程序设计 第1章 输入输出流（共42页）.ppt 完整版 Java高级教程 Java语言程序设计 第2章 Java多线程（共24页）.ppt 完整版 Java高级教程 Java语言程序设计 第2章 哲学家的故事（共7页）...
JAVA高级特性JAVA高级特性JAVA高级特性JAVA高级特性
完整版 Java高级教程 Java语言程序设计 第1章 输入输出流（共42页）.ppt 完整版 Java高级教程 Java语言程序设计 第2章 Java多线程（共24页）.ppt 完整版 Java高级教程 Java语言程序设计 第2章 哲学家的故事（共7页）...
java高级实用教程 java高级实用教程
Java高级实用教程，好得很，学习java的好帮手，值得一看。
2018最新最全java高级工程师面试题，2018最新最全java高级工程师面试题2018最新最全java高级工程师面试题，2018最新最全java高级工程师面试题 十几个文档
上海-拼多多-Java高级.pdf 上海-携程-Java高级.pdf 北京-京东-Java中级.pdf 北京-百度-Java中级.pdf 南京-软通动力-Java中级.pdf 厦门-中软国际-Java中级.pdf 广州-唯品会-Java大数据开发工程师.pdf 杭州-蚂蚁金服-...
包括Java高级编程部分： 图形界面编程的知识 多线程 （支持多人操作）例如qq IO流 输入输出流 异常 网络编程 API的使用、集合等有笔记，源代码，示例程序
JAVA高级教程 JAVA高级教程 JAVA高级教程
高级java工程师面试考纲，java高级工程师进阶知识地图
java高级工程师面试总结
给大家分享一套课程，Java高级面试突围课 ,一次搞定Java中高级面试的必考点视频教程，希望对大家面试有帮助。
| 345个Java高级编程_源码大全打包 | | 内含： | | 345个Java高级编程_源码大全打包 | +--- 100个Java经典编程实例源代码 | | +--- 45款 Java 游戏源代码 | | +--- 50个 JAVA游戏开发编程基础源码 ...
工信部考试复习题库（Java高级证书）把模拟题分享给需要的人，希望能帮助到你们，我们的程序题改成了选择，不知道你们的一样不一样，自己看看空就行了
java高级工程师-笔试题及答案.docx
java高级工程师-面试题及答案.docx
Java 高级工程师的一些常见笔试面试题目，比较经典，值得看看
知名企业java高级工程师面试题附答案
java 高级架构师教程，java 高级架构师教程，java 高级架构师教程，java 高级架构师教程，java 高级架构师教程，java 高级架构师教程，java 高级架构师教程，java 高级架构师教程，java 高级架构师教程，java 高级...