JAVA排序汇总

1.import java.util.Random;  
2. 
3./** 
4. *  
5. * 排序测试类 
6. *  
7. *  
8. *  
9. * 排序算法的分类如下： 
10. *  
11. * 1.插入排序（直接插入排序、折半插入排序、希尔排序）； 
12. *  
13. * 2.交换排序（冒泡泡排序、快速排序）； 
14. *  
15. * 3.选择排序（直接选择排序、堆排序）； 
16. *  
17. * 4.归并排序； 
18. *  
19. * 5.基数排序。 
20. *  
21. *  
22. *  
23. * 关于排序方法的选择： 
24. *  
25. * (1)若n较小(如n≤50)，可采用直接插入或直接选择排序。 
26. *  
27. * 当记录规模较小时，直接插入排序较好；否则因为直接选择移动的记录数少于直接插人，应选直接选择排序为宜。 
28. *  
29. * (2)若文件初始状态基本有序(指正序)，则应选用直接插人、冒泡或随机的快速排序为宜； 
30. *  
31. * (3)若n较大，则应采用时间复杂度为O(nlgn)的排序方法：快速排序、堆排序或归并排序。 
32. *  
33. *  
34. *  
35. */ 
36. 
37.public class SortTest {  
38. 
39.    /** 
40.     *  
41.     * 初始化测试数组的方法 
42.     *  
43.     * @return 一个初始化好的数组 
44.     *  
45.     */ 
46. 
47.    public int[] createArray() {  
48. 
49.        Random random = new Random();  
50. 
51.        int[] array = new int[10];  
52. 
53.        for (int i = 0; i < 10; i++) {  
54. 
55.            array[i] = random.nextInt(100) - random.nextInt(100);// 生成两个随机数相减，保证生成的数中有负数  
56. 
57.        }  
58. 
59.        System.out.println("==========原始序列==========");  
60. 
61.        printArray(array);  
62. 
63.        return array;  
64. 
65.    }  
66. 
67.    /** 
68.     *  
69.     * 打印数组中的元素到控制台 
70.     *  
71.     * @param source 
72.     *  
73.     */ 
74. 
75.    public void printArray(int[] data) {  
76. 
77.        for (int i : data) {  
78. 
79.            System.out.print(i + " ");  
80. 
81.        }  
82. 
83.        System.out.println();  
84. 
85.    }  
86. 
87.    /** 
88.     *  
89.     * 交换数组中指定的两元素的位置 
90.     *  
91.     * @param data 
92.     *  
93.     * @param x 
94.     *  
95.     * @param y 
96.     *  
97.     */ 
98. 
99.    private void swap(int[] data, int x, int y) {  
100. 
101.        int temp = data[x];  
102. 
103.        data[x] = data[y];  
104. 
105.        data[y] = temp;  
106. 
107.    }  
108. 
109.    /** 
110.     *  
111.     * 冒泡排序----交换排序的一种 
112.     *  
113.     * 方法：相邻两元素进行比较，如有需要则进行交换，每完成一次循环就将最大元素排在最后（如从小到大排序），下一次循环是将其他的数进行类似操作。 
114.     *  
115.     * 性能：比较次数O(n^2),n^2/2；交换次数O(n^2),n^2/4 
116.     *  
117.     *  
118.     *  
119.     * @param data 
120.     *            要排序的数组 
121.     *  
122.     * @param sortType 
123.     *            排序类型 
124.     *  
125.     * @return 
126.     *  
127.     */ 
128. 
129.    public void bubbleSort(int[] data, String sortType) {  
130. 
131.        if (sortType.equals("asc")) { // 正排序，从小排到大  
132. 
133.            // 比较的轮数  
134. 
135.            for (int i = 1; i < data.length; i++) {  
136. 
137.                // 将相邻两个数进行比较，较大的数往后冒泡  
138. 
139.                for (int j = 0; j < data.length - i; j++) {  
140. 
141.                    if (data[j] > data[j + 1]) {  
142. 
143.                        // 交换相邻两个数  
144. 
145.                        swap(data, j, j + 1);  
146. 
147.                    }  
148. 
149.                }  
150. 
151.            }  
152. 
153.        } else if (sortType.equals("desc")) { // 倒排序，从大排到小  
154. 
155.            // 比较的轮数  
156. 
157.            for (int i = 1; i < data.length; i++) {  
158. 
159.                // 将相邻两个数进行比较，较大的数往后冒泡  
160. 
161.                for (int j = 0; j < data.length - i; j++) {  
162. 
163.                    if (data[j] < data[j + 1]) {  
164. 
165.                        // 交换相邻两个数  
166. 
167.                        swap(data, j, j + 1);  
168. 
169.                    }  
170. 
171.                }  
172. 
173.            }  
174. 
175.        } else {  
176. 
177.            System.out.println("您输入的排序类型错误！");  
178. 
179.        }  
180. 
181.        printArray(data);// 输出冒泡排序后的数组值  
182. 
183.    }  
184. 
185.    /** 
186.     *  
187.     * 直接选择排序法----选择排序的一种 
188.     *  
189.     * 方法：每一趟从待排序的数据元素中选出最小（或最大）的一个元素， 顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完。 
190.     *  
191.     * 性能：比较次数O(n^2),n^2/2 
192.     *  
193.     * 交换次数O(n),n 
194.     *  
195.     * 交换次数比冒泡排序少多了，由于交换所需CPU时间比比较所需的CUP时间多，所以选择排序比冒泡排序快。 
196.     *  
197.     * 但是N比较大时，比较所需的CPU时间占主要地位，所以这时的性能和冒泡排序差不太多，但毫无疑问肯定要快些。 
198.     *  
199.     *  
200.     *  
201.     * @param data 
202.     *            要排序的数组 
203.     *  
204.     * @param sortType 
205.     *            排序类型 
206.     *  
207.     * @return 
208.     *  
209.     */ 
210. 
211.    public void selectSort(int[] data, String sortType) {  
212. 
213.        if (sortType.equals("asc")) { // 正排序，从小排到大  
214. 
215.            int index;  
216. 
217.            for (int i = 1; i < data.length; i++) {  
218. 
219.                index = 0;  
220. 
221.                for (int j = 1; j <= data.length - i; j++) {  
222. 
223.                    if (data[j] > data[index]) {  
224. 
225.                        index = j;  
226. 
227.                    }  
228. 
229.                }  
230. 
231.                // 交换在位置data.length-i和index(最大值)两个数  
232. 
233.                swap(data, data.length - i, index);  
234. 
235.            }  
236. 
237.        } else if (sortType.equals("desc")) { // 倒排序，从大排到小  
238. 
239.            int index;  
240. 
241.            for (int i = 1; i < data.length; i++) {  
242. 
243.                index = 0;  
244. 
245.                for (int j = 1; j <= data.length - i; j++) {  
246. 
247.                    if (data[j] < data[index]) {  
248. 
249.                        index = j;  
250. 
251.                    }  
252. 
253.                }  
254. 
255.                // 交换在位置data.length-i和index(最大值)两个数  
256. 
257.                swap(data, data.length - i, index);  
258. 
259.            }  
260. 
261.        } else {  
262. 
263.            System.out.println("您输入的排序类型错误！");  
264. 
265.        }  
266. 
267.        printArray(data);// 输出直接选择排序后的数组值  
268. 
269.    }  
270. 
271.    /** 
272.     *  
273.     * 插入排序 
274.     *  
275.     * 方法：将一个记录插入到已排好序的有序表（有可能是空表）中,从而得到一个新的记录数增1的有序表。 
276.     *  
277.     * 性能：比较次数O(n^2),n^2/4 
278.     *  
279.     * 复制次数O(n),n^2/4 
280.     *  
281.     * 比较次数是前两者的一般，而复制所需的CPU时间较交换少，所以性能上比冒泡排序提高一倍多，而比选择排序也要快。 
282.     *  
283.     *  
284.     *  
285.     * @param data 
286.     *            要排序的数组 
287.     *  
288.     * @param sortType 
289.     *            排序类型 
290.     *  
291.     */ 
292. 
293.    public void insertSort(int[] data, String sortType) {  
294. 
295.        if (sortType.equals("asc")) { // 正排序，从小排到大  
296. 
297.            // 比较的轮数  
298. 
299.            for (int i = 1; i < data.length; i++) {  
300. 
301.                // 保证前i+1个数排好序  
302. 
303.                for (int j = 0; j < i; j++) {  
304. 
305.                    if (data[j] > data[i]) {  
306. 
307.                        // 交换在位置j和i两个数  
308. 
309.                        swap(data, i, j);  
310. 
311.                    }  
312. 
313.                }  
314. 
315.            }  
316. 
317.        } else if (sortType.equals("desc")) { // 倒排序，从大排到小  
318. 
319.            // 比较的轮数  
320. 
321.            for (int i = 1; i < data.length; i++) {  
322. 
323.                // 保证前i+1个数排好序  
324. 
325.                for (int j = 0; j < i; j++) {  
326. 
327.                    if (data[j] < data[i]) {  
328. 
329.                        // 交换在位置j和i两个数  
330. 
331.                        swap(data, i, j);  
332. 
333.                    }  
334. 
335.                }  
336. 
337.            }  
338. 
339.        } else {  
340. 
341.            System.out.println("您输入的排序类型错误！");  
342. 
343.        }  
344. 
345.        printArray(data);// 输出插入排序后的数组值  
346. 
347.    }  
348. 
349.    /** 
350.     *  
351.     * 反转数组的方法 
352.     *  
353.     * @param data 
354.     *            源数组 
355.     *  
356.     */ 
357. 
358.    public void reverse(int[] data) {  
359. 
360.        int length = data.length;  
361. 
362.        int temp = 0;// 临时变量  
363. 
364.        for (int i = 0; i < length / 2; i++) {  
365. 
366.            temp = data[i];  
367. 
368.            data[i] = data[length - 1 - i];  
369. 
370.            data[length - 1 - i] = temp;  
371. 
372.        }  
373. 
374.        printArray(data);// 输出到转后数组的值  
375. 
376.    }  
377. 
378.    /** 
379.     *  
380.     * 快速排序 
381.     *  
382.     * 快速排序使用分治法（Divide and conquer）策略来把一个序列（list）分为两个子序列（sub-lists）。 
383.     *  
384.     * 步骤为： 
385.     *  
386.     * 1. 从数列中挑出一个元素，称为 "基准"（pivot）， 
387.     *  
388.     * 2. 
389.     * 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分割之后，该基准是它的最后位置。这个称为分割（partition）操作。 
390.     *  
391.     * 3. 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。 
392.     *  
393.     * 递回的最底部情形，是数列的大小是零或一，也就是永远都已经被排序好了。虽然一直递回下去，但是这个算法总会结束，因为在每次的迭代（iteration）中，它至少会把一个元素摆到它最后的位置去。 
394.     *  
395.     * @param data 
396.     *            待排序的数组 
397.     *  
398.     * @param low 
399.     *  
400.     * @param high 
401.     *  
402.     * @see SortTest#qsort(int[], int, int) 
403.     *  
404.     * @see SortTest#qsort_desc(int[], int, int) 
405.     *  
406.     */ 
407. 
408.    public void quickSort(int[] data, String sortType) {  
409. 
410.        if (sortType.equals("asc")) { // 正排序，从小排到大  
411. 
412.            qsort_asc(data, 0, data.length - 1);  
413. 
414.        } else if (sortType.equals("desc")) { // 倒排序，从大排到小  
415. 
416.            qsort_desc(data, 0, data.length - 1);  
417. 
418.        } else {  
419. 
420.            System.out.println("您输入的排序类型错误！");  
421. 
422.        }  
423. 
424.    }  
425. 
426.    /** 
427.     *  
428.     * 快速排序的具体实现，排正序 
429.     *  
430.     * @param data 
431.     *  
432.     * @param low 
433.     *  
434.     * @param high 
435.     *  
436.     */ 
437. 
438.    private void qsort_asc(int data[], int low, int high) {  
439. 
440.        int i, j, x;  
441. 
442.        if (low < high) { // 这个条件用来结束递归  
443. 
444.            i = low;  
445. 
446.            j = high;  
447. 
448.            x = data[i];  
449. 
450.            while (i < j) {  
451. 
452.                while (i < j && data[j] > x) {  
453. 
454.                    j--; // 从右向左找第一个小于x的数  
455. 
456.                }  
457. 
458.                if (i < j) {  
459. 
460.                    data[i] = data[j];  
461. 
462.                    i++;  
463. 
464.                }  
465. 
466.                while (i < j && data[i] < x) {  
467. 
468.                    i++; // 从左向右找第一个大于x的数  
469. 
470.                }  
471. 
472.                if (i < j) {  
473. 
474.                    data[j] = data[i];  
475. 
476.                    j--;  
477. 
478.                }  
479. 
480.            }  
481. 
482.            data[i] = x;  
483. 
484.            qsort_asc(data, low, i - 1);  
485. 
486.            qsort_asc(data, i + 1, high);  
487. 
488.        }  
489. 
490.    }  
491. 
492.    /** 
493.     *  
494.     * 快速排序的具体实现，排倒序 
495.     *  
496.     * @param data 
497.     *  
498.     * @param low 
499.     *  
500.     * @param high 
501.     *  
502.     */ 
503. 
504.    private void qsort_desc(int data[], int low, int high) {  
505. 
506.        int i, j, x;  
507. 
508.        if (low < high) { // 这个条件用来结束递归  
509. 
510.            i = low;  
511. 
512.            j = high;  
513. 
514.            x = data[i];  
515. 
516.            while (i < j) {  
517. 
518.                while (i < j && data[j] < x) {  
519. 
520.                    j--; // 从右向左找第一个小于x的数  
521. 
522.                }  
523. 
524.                if (i < j) {  
525. 
526.                    data[i] = data[j];  
527. 
528.                    i++;  
529. 
530.                }  
531. 
532.                while (i < j && data[i] > x) {  
533. 
534.                    i++; // 从左向右找第一个大于x的数  
535. 
536.                }  
537. 
538.                if (i < j) {  
539. 
540.                    data[j] = data[i];  
541. 
542.                    j--;  
543. 
544.                }  
545. 
546.            }  
547. 
548.            data[i] = x;  
549. 
550.            qsort_desc(data, low, i - 1);  
551. 
552.            qsort_desc(data, i + 1, high);  
553. 
554.        }  
555. 
556.    }  
557. 
558.    /** 
559.     *  
560.     * 二分查找特定整数在整型数组中的位置(递归) 
561.     *  
562.     * 查找线性表必须是有序列表 
563.     *  
564.     * @paramdataset 
565.     *  
566.     * @paramdata 
567.     *  
568.     * @parambeginIndex 
569.     *  
570.     * @paramendIndex 
571.     *  
572.     * @returnindex 
573.     *  
574.     */ 
575. 
576.    public int binarySearch(int[] dataset, int data, int beginIndex,  
577. 
578.    int endIndex) {  
579. 
580.        int midIndex = (beginIndex + endIndex) >>> 1; // 相当于mid = (low + high)  
581.                                                        // / 2，但是效率会高些  
582. 
583.        if (data < dataset[beginIndex] || data > dataset[endIndex]  
584. 
585.        || beginIndex > endIndex)  
586. 
587.            return -1;  
588. 
589.        if (data < dataset[midIndex]) {  
590. 
591.            return binarySearch(dataset, data, beginIndex, midIndex - 1);  
592. 
593.        } else if (data > dataset[midIndex]) {  
594. 
595.            return binarySearch(dataset, data, midIndex + 1, endIndex);  
596. 
597.        } else {  
598. 
599.            return midIndex;  
600. 
601.        }  
602. 
603.    }  
604. 
605.    /** 
606.     *  
607.     * 二分查找特定整数在整型数组中的位置(非递归) 
608.     *  
609.     * 查找线性表必须是有序列表 
610.     *  
611.     * @paramdataset 
612.     *  
613.     * @paramdata 
614.     *  
615.     * @returnindex 
616.     *  
617.     */ 
618. 
619.    public int binarySearch(int[] dataset, int data) {  
620. 
621.        int beginIndex = 0;  
622. 
623.        int endIndex = dataset.length - 1;  
624. 
625.        int midIndex = -1;  
626. 
627.        if (data < dataset[beginIndex] || data > dataset[endIndex]  
628. 
629.        || beginIndex > endIndex)  
630. 
631.            return -1;  
632. 
633.        while (beginIndex <= endIndex) {  
634. 
635.            midIndex = (beginIndex + endIndex) >>> 1; // 相当于midIndex =  
636.                                                        // (beginIndex +  
637.                                                        // endIndex) / 2，但是效率会高些  
638. 
639.            if (data < dataset[midIndex]) {  
640. 
641.                endIndex = midIndex - 1;  
642. 
643.            } else if (data > dataset[midIndex]) {  
644. 
645.                beginIndex = midIndex + 1;  
646. 
647.            } else {  
648. 
649.                return midIndex;  
650. 
651.            }  
652. 
653.        }  
654. 
655.        return -1;  
656. 
657.    }  
658. 
659.    public static void main(String[] args) {  
660. 
661.        SortTest sortTest = new SortTest();  
662. 
663.        int[] array = sortTest.createArray();  
664. 
665.        System.out.println("==========冒泡排序后(正序)==========");  
666. 
667.        sortTest.bubbleSort(array, "asc");  
668. 
669.        System.out.println("==========冒泡排序后(倒序)==========");  
670. 
671.        sortTest.bubbleSort(array, "desc");  
672. 
673.        array = sortTest.createArray();  
674. 
675.        System.out.println("==========倒转数组后==========");  
676. 
677.        sortTest.reverse(array);  
678. 
679.        array = sortTest.createArray();  
680. 
681.        System.out.println("==========选择排序后(正序)==========");  
682. 
683.        sortTest.selectSort(array, "asc");  
684. 
685.        System.out.println("==========选择排序后(倒序)==========");  
686. 
687.        sortTest.selectSort(array, "desc");  
688. 
689.        array = sortTest.createArray();  
690. 
691.        System.out.println("==========插入排序后(正序)==========");  
692. 
693.        sortTest.insertSort(array, "asc");  
694. 
695.        System.out.println("==========插入排序后(倒序)==========");  
696. 
697.        sortTest.insertSort(array, "desc");  
698. 
699.        array = sortTest.createArray();  
700. 
701.        System.out.println("==========快速排序后(正序)==========");  
702. 
703.        sortTest.quickSort(array, "asc");  
704. 
705.        sortTest.printArray(array);  
706. 
707.        System.out.println("==========快速排序后(倒序)==========");  
708. 
709.        sortTest.quickSort(array, "desc");  
710. 
711.        sortTest.printArray(array);  
712. 
713.        System.out.println("==========数组二分查找==========");  
714. 
715.        System.out.println("您要找的数在第" + sortTest.binarySearch(array, 74)  
716. 
717.        + "个位子。（下标从0计算）");  
718. 
719.    }  
720. 
721.}


原文：http://keer2345.iteye.com/blog/584914