`
ivanisme
  • 浏览: 78621 次
  • 性别: Icon_minigender_1
  • 来自: Shang Hai
最近访客 更多访客>>
daoger
社区版块
存档分类
最新评论

用Java实现几种常见的排序算法

    博客分类：
  • Java
算法JavaJ# 
阅读更多
用Java语言实现的各种排序，包括插入排序、冒泡排序、选择排序、Shell排序、快速排序、归并排序、堆排序、SortUtil等。


  1.  插入排序：
  2. package org.rut.util.algorithm.support;  
  3. 　import org.rut.util.algorithm.SortUtil;  
  4. 　/** 
  5. 　* @author treeroot 
  6. 　* @since 2006-2-2 
  7. 　* @version 1.0 
  8. 　*/  
  9. 　public class InsertSort implements SortUtil.Sort  
  10. 　{  
  11. 　　/* (non-Javadoc) 
  12. 　　* @see org.rut.util.algorithm.SortUtil.Sort#sort(int[]) 
  13. 　　*/  
  14. 　　public void sort(int[] data)   
  15. 　　{  
  16. 　　　int temp;  
  17. 　　　for(int i=1;i for(int j=i;(j>0)&&(data[j] SortUtil.swap(data,j,j-1);  
  18. 　　}  
  19. 　}   
  20.   
  21. 　冒泡排序：  
  22.   
  23. 　package org.rut.util.algorithm.support;  
  24. 　import org.rut.util.algorithm.SortUtil;  
  25. 　/** 
  26. 　* @author treeroot 
  27. 　* @since 2006-2-2 
  28. 　* @version 1.0 
  29. 　*/  
  30. 　public class BubbleSort implements SortUtil.Sort  
  31. 　{  
  32. 　　/* (non-Javadoc) 
  33. 　　* @see org.rut.util.algorithm.SortUtil.Sort#sort(int[]) 
  34. 　　*/  
  35. 　　public void sort(int[] data)   
  36. 　　{  
  37. 　　　int temp;  
  38. 　　　for(int i=0;i for(int j=data.length-1;j>i;j--)  
  39. 　　　{  
  40. 　　　　if(data[j] SortUtil.swap(data,j,j-1);  
  41. 　　　}  
  42. 　　}  
  43. 　}  
  44.   
  45. 　选择排序：  
  46.   
  47. 　package org.rut.util.algorithm.support;  
  48. 　import org.rut.util.algorithm.SortUtil;  
  49. 　/** 
  50. 　* @author treeroot 
  51. 　* @since 2006-2-2 
  52. 　* @version 1.0 
  53. 　*/  
  54. 　public class SelectionSort implements SortUtil.Sort   
  55. 　{  
  56. 　　/* 
  57. 　　* (non-Javadoc) 
  58. 　　*  
  59. 　　* @see org.rut.util.algorithm.SortUtil.Sort#sort(int[]) 
  60. 　　*/  
  61. 　　public void sort(int[] data)   
  62. 　　{  
  63. 　　　int temp;  
  64. 　　　for (int i = 0; i < data.length; i++)   
  65. 　　　{  
  66. 　　　　int lowIndex = i;  
  67. 　　　　for (int j = data.length - 1; j >i; j--)   
  68. 　　　　{  
  69. 　　　　　if (data[j] < data[lowIndex])   
  70. 　　　　　{  
  71. 　　　　　　lowIndex = j;  
  72. 　　　　　}  
  73. 　　　　}  
  74. 　　　　SortUtil.swap(data,i,lowIndex);  
  75. 　　　}  
  76. 　　}  
  77. 　}  
  78. 　Shell排序：  
  79.   
  80. 　package org.rut.util.algorithm.support;  
  81. 　import org.rut.util.algorithm.SortUtil;  
  82. 　/** 
  83. 　* @author treeroot 
  84. 　* @since 2006-2-2 
  85. 　* @version 1.0 
  86. 　*/  
  87. 　public class ShellSort implements SortUtil.Sort  
  88. 　{  
  89. 　　/* (non-Javadoc) 
  90. 　　* @see org.rut.util.algorithm.SortUtil.Sort#sort(int[]) 
  91. 　　*/  
  92. 　　public void sort(int[] data)   
  93. 　　{  
  94. 　　　for(int i=data.length/2;i>2;i/=2)  
  95. 　　　{  
  96. 　　　　for(int j=0;j insertSort(data,j,i);  
  97. 　　　}  
  98. 　　}  
  99. 　　insertSort(data,0,1);  
  100. 　}  
  101.   
  102. 　/** 
  103. 　* @param data 
  104. 　* @param j 
  105. 　* @param i 
  106. 　*/  
  107. 　private void insertSort(int[] data, int start, int inc)   
  108. 　{  
  109. 　　int temp;  
  110. 　　for(int i=start+inc;i for(int j=i;(j>=inc)&&(data[j] SortUtil.swap(data,j,j-inc);  
  111. 　}  
  112.   
  113. 　快速排序：  
  114.   
  115. 　package org.rut.util.algorithm.support;  
  116. 　import org.rut.util.algorithm.SortUtil;  
  117. 　/** 
  118. 　* @author treeroot 
  119. 　* @since 2006-2-2 
  120. 　* @version 1.0 
  121. 　*/  
  122. 　public class QuickSort implements SortUtil.Sort  
  123. 　{  
  124. 　　/* (non-Javadoc) 
  125. 　　* @see org.rut.util.algorithm.SortUtil.Sort#sort(int[]) 
  126. 　　*/  
  127. 　　public void sort(int[] data)   
  128. 　　{  
  129. 　　　quickSort(data,0,data.length-1);   
  130. 　　}  
  131. 　　private void quickSort(int[] data,int i,int j)  
  132. 　　{  
  133. 　　　int pivotIndex=(i+j)/2;  
  134. 　　　//swap  
  135. 　　　SortUtil.swap(data,pivotIndex,j);  
  136. 　　　int k=partition(data,i-1,j,data[j]);  
  137. 　　　SortUtil.swap(data,k,j);  
  138. 　　　if((k-i)>1) quickSort(data,i,k-1);  
  139. 　　　if((j-k)>1) quickSort(data,k+1,j);  
  140. 　　}  
  141. 　　/** 
  142. 　　* @param data 
  143. 　　* @param i 
  144. 　　* @param j 
  145. 　　* @return 
  146. 　　*/  
  147. 　　private int partition(int[] data, int l, int r,int pivot)   
  148. 　　{  
  149. 　　　do  
  150. 　　　{  
  151. 　　　　while(data[++l] while((r!=0)&&data[--r]>pivot);  
  152. 　　　　SortUtil.swap(data,l,r);  
  153. 　　　}  
  154. 　　　while(l SortUtil.swap(data,l,r);   
  155. 　　　return l;  
  156. 　　}  
  157. 　}  
  158.   
  159. 　改进后的快速排序：  
  160.   
  161. 　package org.rut.util.algorithm.support;  
  162. 　import org.rut.util.algorithm.SortUtil;  
  163. 　/** 
  164. 　* @author treeroot 
  165. 　* @since 2006-2-2 
  166. 　* @version 1.0 
  167. 　*/  
  168. 　public class ImprovedQuickSort implements SortUtil.Sort   
  169. 　{  
  170. 　　private static int MAX_STACK_SIZE=4096;  
  171. 　　private static int THRESHOLD=10;  
  172. 　　/* (non-Javadoc) 
  173. 　　* @see org.rut.util.algorithm.SortUtil.Sort#sort(int[]) 
  174. 　　*/  
  175. 　　public void sort(int[] data)   
  176. 　　{  
  177. 　　　int[] stack=new int[MAX_STACK_SIZE];  
  178. 　　　int top=-1;  
  179. 　　　int pivot;  
  180. 　　　int pivotIndex,l,r;  
  181. 　　　stack[++top]=0;  
  182. 　　　stack[++top]=data.length-1;  
  183. 　　　while(top>0)  
  184. 　　　{  
  185. 　　　　int j=stack[top--];  
  186. 　　　　int i=stack[top--];  
  187. 　　　　pivotIndex=(i+j)/2;  
  188. 　　　　pivot=data[pivotIndex];  
  189. 　　　　SortUtil.swap(data,pivotIndex,j);  
  190. 　　　　//partition  
  191. 　　　　l=i-1;  
  192. 　　　　r=j;  
  193. 　　　　do  
  194. 　　　　{  
  195. 　　　　　while(data[++l] while((r!=0)&&(data[--r]>pivot));  
  196. 　　　　　SortUtil.swap(data,l,r);  
  197. 　　　　}  
  198. 　　　　while(l SortUtil.swap(data,l,r);  
  199. 　　　　SortUtil.swap(data,l,j);  
  200. 　　　　if((l-i)>THRESHOLD)  
  201. 　　　　{  
  202. 　　　　　stack[++top]=i;  
  203. 　　　　　stack[++top]=l-1;  
  204. 　　　　}  
  205. 　　　　if((j-l)>THRESHOLD)  
  206. 　　　　{  
  207. 　　　　　stack[++top]=l+1;  
  208. 　　　　　stack[++top]=j;  
  209. 　　　　}  
  210. 　　　}  
  211. 　　　//new InsertSort().sort(data);  
  212. 　　　insertSort(data);  
  213. 　　}  
  214. 　　/** 
  215. 　　* @param data 
  216. 　　*/  
  217. 　　private void insertSort(int[] data)   
  218. 　　{  
  219. 　　　int temp;  
  220. 　　　for(int i=1;i for(int j=i;(j>0)&&(data[j] SortUtil.swap(data,j,j-1);  
  221. 　　}  
  222. 　}   
  223. 　归并排序：  
  224.   
  225. 　package org.rut.util.algorithm.support;  
  226. 　import org.rut.util.algorithm.SortUtil;  
  227. 　/** 
  228. 　* @author treeroot 
  229. 　* @since 2006-2-2 
  230. 　* @version 1.0 
  231. 　*/  
  232. 　public class MergeSort implements SortUtil.Sort  
  233. 　{  
  234. 　　/* (non-Javadoc) 
  235. 　　* @see org.rut.util.algorithm.SortUtil.Sort#sort(int[]) 
  236. 　　*/  
  237. 　　public void sort(int[] data)   
  238. 　　{  
  239. 　　　int[] temp=new int[data.length];  
  240. 　　　mergeSort(data,temp,0,data.length-1);  
  241. 　　}  
  242. 　　private void mergeSort(int[] data,int[] temp,int l,int r)  
  243. 　　{  
  244. 　　　int mid=(l+r)/2;  
  245. 　　　if(l==r) return ;  
  246. 　　　mergeSort(data,temp,l,mid);  
  247. 　　　mergeSort(data,temp,mid+1,r);  
  248. 　　　for(int i=l;i<=r;i++){  
  249. 　　　temp[i]=data[i];  
  250. 　　}  
  251. 　　int i1=l;  
  252. 　　int i2=mid+1;  
  253. 　　for(int cur=l;cur<=r;cur++)  
  254. 　　{  
  255. 　　　if(i1==mid+1)  
  256. 　　　data[cur]=temp[i2++];  
  257. 　　　else if(i2>r)  
  258. 　　　data[cur]=temp[i1++];  
  259. 　　　else if(temp[i1] data[cur]=temp[i1++];  
  260. 　　　else  
  261. 　　　data[cur]=temp[i2++];   
  262. 　　}  
  263. 　}  
  264.   
  265. 　改进后的归并排序:  
  266.   
  267. 　package org.rut.util.algorithm.support;  
  268. 　import org.rut.util.algorithm.SortUtil;  
  269. 　/** 
  270. 　* @author treeroot 
  271. 　* @since 2006-2-2 
  272. 　* @version 1.0 
  273. 　*/  
  274. 　public class ImprovedMergeSort implements SortUtil.Sort   
  275. 　{  
  276. 　　private static final int THRESHOLD = 10;  
  277. 　　/* 
  278. 　　* (non-Javadoc) 
  279. 　　*  
  280. 　　* @see org.rut.util.algorithm.SortUtil.Sort#sort(int[]) 
  281. 　　*/  
  282. 　　public void sort(int[] data)   
  283. 　　{  
  284. 　　　int[] temp=new int[data.length];  
  285. 　　　mergeSort(data,temp,0,data.length-1);  
  286. 　　}  
  287. 　　private void mergeSort(int[] data, int[] temp, int l, int r)   
  288. 　　{  
  289. 　　　int i, j, k;  
  290. 　　　int mid = (l + r) / 2;  
  291. 　　　if (l == r)  
  292. 　　　return;  
  293. 　　　if ((mid - l) >= THRESHOLD)  
  294. 　　　mergeSort(data, temp, l, mid);  
  295. 　　　else  
  296. 　　　insertSort(data, l, mid - l + 1);  
  297. 　　　if ((r - mid) >THRESHOLD)  
  298. 　　　mergeSort(data, temp, mid + 1, r);  
  299. 　　　else  
  300. 　　　insertSort(data, mid + 1, r - mid);  
  301. 　　　for (i = l; i <= mid; i++)   
  302. 　　　{  
  303. 　　　　temp[i] = data[i];  
  304. 　　　}  
  305. 　　　for (j = 1; j <= r - mid; j++)   
  306. 　　　{  
  307. 　　　　temp[r - j + 1] = data[j + mid];  
  308. 　　　}  
  309. 　　　int a = temp[l];  
  310. 　　　int b = temp[r];  
  311. 　　　for (i = l, j = r, k = l; k <= r; k++)   
  312. 　　　{  
  313. 　　　　if (a < b)   
  314. 　　　　{  
  315. 　　　　　data[k] = temp[i++];  
  316. 　　　　　a = temp[i];  
  317. 　　　　}   
  318. 　　　　else   
  319. 　　　　{  
  320. 　　　　　data[k] = temp[j--];  
  321. 　　　　　b = temp[j];  
  322. 　　　　}  
  323. 　　　}  
  324. 　　}  
  325.   
  326. 　　/** 
  327. 　　* @param data 
  328. 　　* @param l 
  329. 　　* @param i 
  330. 　　*/  
  331. 　　private void insertSort(int[] data, int start, int len)   
  332. 　　{  
  333. 　　　for(int i=start+1;i for(int j=i;(j>start) && data[j] SortUtil.swap(data,j,j-1);  
  334. 　　}  
  335. 　}  
  336. 　堆排序：  
  337.   
  338. 　package org.rut.util.algorithm.support;  
  339. 　import org.rut.util.algorithm.SortUtil;  
  340. 　/** 
  341. 　* @author treeroot 
  342. 　* @since 2006-2-2 
  343. 　* @version 1.0 
  344. 　*/  
  345. 　public class HeapSort implements SortUtil.Sort  
  346. 　{  
  347. 　　/* (non-Javadoc) 
  348. 　　* @see org.rut.util.algorithm.SortUtil.Sort#sort(int[]) 
  349. 　　*/  
  350. 　　public void sort(int[] data)   
  351. 　　{  
  352. 　　　MaxHeap h=new MaxHeap();  
  353. 　　　h.init(data);  
  354. 　　　for(int i=0;i h.remove();  
  355. 　　　System.arraycopy(h.queue,1,data,0,data.length);  
  356. 　　}  
  357. 　　private static class MaxHeap  
  358. 　　{   
  359. 　　　void init(int[] data)  
  360. 　　　{  
  361. 　　　　this.queue=new int[data.length+1];  
  362. 　　　　for(int i=0;i queue[++size]=data[i];  
  363. 　　　　fixUp(size);  
  364. 　　　}  
  365. 　　}  
  366. 　　private int size=0;  
  367. 　　private int[] queue;  
  368. 　　public int get()   
  369. 　　{  
  370. 　　　return queue[1];  
  371. 　　}  
  372. 　　public void remove()   
  373. 　　{  
  374. 　　　SortUtil.swap(queue,1,size--);  
  375. 　　　fixDown(1);  
  376. 　　}  
  377. 　　//fixdown  
  378. 　　private void fixDown(int k)   
  379. 　　{  
  380. 　　　int j;  
  381. 　　　while ((j = k << 1) <= size)   
  382. 　　　{  
  383. 　　　　if (j < size && queue[j] j++;   
  384. 　　　　if (queue[k]>queue[j]) //不用交换  
  385. 　　　　break;  
  386. 　　　　SortUtil.swap(queue,j,k);  
  387. 　　　　k = j;  
  388. 　　　}  
  389. 　　}  
  390. 　　private void fixUp(int k)   
  391. 　　{  
  392. 　　　while (k >1)   
  393. 　　　{  
  394. 　　　　int j = k >>1;  
  395. 　　　　if (queue[j]>queue[k])  
  396. 　　　　break;  
  397. 　　　　SortUtil.swap(queue,j,k);  
  398. 　　　　k = j;  
  399. 　　　}  
  400. 　　}  
  401. 　}  
  402.   
  403. 　SortUtil：  
  404.   
  405. 　package org.rut.util.algorithm;  
  406. 　import org.rut.util.algorithm.support.BubbleSort;  
  407. 　import org.rut.util.algorithm.support.HeapSort;  
  408. 　import org.rut.util.algorithm.support.ImprovedMergeSort;  
  409. 　import org.rut.util.algorithm.support.ImprovedQuickSort;  
  410. 　import org.rut.util.algorithm.support.InsertSort;  
  411. 　import org.rut.util.algorithm.support.MergeSort;  
  412. 　import org.rut.util.algorithm.support.QuickSort;  
  413. 　import org.rut.util.algorithm.support.SelectionSort;  
  414. 　import org.rut.util.algorithm.support.ShellSort;  
  415.   
  416. 　/** 
  417. 　* @author treeroot 
  418. 　* @since 2006-2-2 
  419. 　* @version 1.0 
  420. 　*/  
  421. 　public class SortUtil   
  422. 　{  
  423. 　　public final static int INSERT = 1;  
  424. 　　public final static int BUBBLE = 2;  
  425. 　　public final static int SELECTION = 3;  
  426. 　　public final static int SHELL = 4;  
  427. 　　public final static int QUICK = 5;  
  428. 　　public final static int IMPROVED_QUICK = 6;  
  429. 　　public final static int MERGE = 7;  
  430. 　　public final static int IMPROVED_MERGE = 8;  
  431. 　　public final static int HEAP = 9;  
  432. 　　public static void sort(int[] data)   
  433. 　　{  
  434. 　　　sort(data, IMPROVED_QUICK);  
  435. 　　}  
  436. 　　private static String[] name=  
  437. 　　{  
  438. 　　　"insert", "bubble", "selection", "shell", "quick", "improved_quick", "merge", "improved_merge", "heap"  
  439. 　　};  
  440. 　　private static Sort[] impl=new Sort[]  
  441. 　　{  
  442. 　　　new InsertSort(),  
  443. 　　　new BubbleSort(),  
  444. 　　　new SelectionSort(),  
  445. 　　　new ShellSort(),  
  446. 　　　new QuickSort(),  
  447. 　　　new ImprovedQuickSort(),  
  448. 　　　new MergeSort(),  
  449. 　　　new ImprovedMergeSort(),  
  450. 　　　new HeapSort()  
  451. 　　};  
  452. 　　public static String toString(int algorithm)  
  453. 　　{  
  454. 　　　return name[algorithm-1];  
  455. 　　}  
  456. 　　public static void sort(int[] data, int algorithm)   
  457. 　　{  
  458. 　　　impl[algorithm-1].sort(data);  
  459. 　　}  
  460. 　　public static interface Sort   
  461. 　　{  
  462. 　　　public void sort(int[] data);  
  463. 　　}  
  464. 　　public static void swap(int[] data, int i, int j)   
  465. 　　{  
  466. 　　　int temp = data[i];  
  467. 　　　data[i] = data[j];  
  468. 　　　data[j] = temp;  
  469. 　　}  
  470. 　}  
分享到：
| Spring中映射X.hbm.xml文件的小技巧
评论
发表评论

您还没有登录,请您登录后再发表评论

相关推荐

    用Java实现几种常见的排序算法.txt

    根据提供的文件信息，我们可以总结出该文档主要涉及了五种基于...以上就是关于这五种排序算法的介绍及其基于Java的实现方式。这些排序算法各有优缺点，适用于不同的场景，了解并掌握它们能够帮助开发者更好地解决问题。

    java实现数据结构常见排序算法及详解

    ### Java 实现数据结构常见排序算法及详解 #### 排序算法概述 排序算法是计算机科学中的基础概念之一，主要用于将一系列数据按照特定规则进行排列。根据数据处理方式的不同，排序算法大致分为两大类：比较排序与非...

    各种排序算法比较（java实现）

    本文将详细探讨标题所提及的几种排序算法：合并排序、插入排序、希尔排序、快速排序、冒泡排序以及桶排序，并结合Java语言的实现进行解析。 1. **合并排序(Merge Sort)**： 合并排序是一种基于分治策略的排序算法...

    Java几种常见的排序算法

    Java几种常见的排序算法

    常用排序算法java演示

    7. **计数排序（Counting Sort）、桶排序（Bucket Sort）和基数排序（Radix Sort）**：这三种排序算法属于非比较型排序，不依赖于元素间的比较，而是基于特定的特性，如元素的范围、分布等。Java中实现这类排序通常...

    Java实现几种常见的排序算法

    本文将详细探讨Java中实现几种常见的排序算法，包括它们的工作原理、时间复杂度以及如何在实际代码中应用。 一、冒泡排序（Bubble Sort） 冒泡排序是一种简单的排序算法，它重复地遍历待排序的数列，一次比较两个...

    Java实现几种常见排序方法

    ### Java 实现几种常见排序方法 #### 泡泡排序（Bubble Sort） ...以上是几种常见的排序算法在 Java 中的具体实现，每种算法都有其特点和适用场景。在实际应用中可以根据具体需求选择最合适的排序算法。

    java编写的几种排序算法

    本文将深入探讨在Java中实现的几种常见排序算法：冒泡排序、快速排序以及堆排序。 1. **冒泡排序（Bubble Sort）** 冒泡排序是最简单的排序算法之一，通过重复遍历数组，比较相邻元素并交换位置，直到没有任何一对...

    JAVA几种常用的排序算法

    JAVA几种常用的经典的排序算法 冒泡 选择 快速 shell 堆排序

    几种常见排序算法JAVA实现.pdf

    几种常见排序算法JAVA实现.pdf

    java排序算法

    本文将深入探讨Java中常见的几种基本排序算法，包括插入排序、交换排序、选择排序以及归并排序，并分析它们的基本思想、时间复杂度以及应用场景。 #### 插入排序 插入排序是一种简单的排序方法，它的工作原理类似...

    Java几种常见的排序算法(经典收藏)

    根据给定的文件信息，我们可以深入探讨几种在Java中实现的经典排序算法，这些算法是数据结构与算法领域的重要组成部分，广泛应用于各种计算机科学场景。以下是对插入排序（Insertion Sort）、冒泡排序（Bubble Sort...

    java 几种常用的排序算法

    ### Java几种常用的排序算法 在Java编程语言中，排序算法是数据处理中不可或缺的一部分，它不仅可以帮助我们组织数据，还能提高程序效率。本篇文章将详细介绍几种常用的Java排序算法：选择排序、冒泡排序以及插入...

Magicbox
Global site tag (gtag.js) - Google Analytics