黑马程序员技术交流社区

标题: Java实现快排算法 [打印本页]

---

作者: yxz    时间: 2013-9-8 21:58
标题: Java实现快排算法
快速排序的效率很高，算法也比较经典。

1. public class Test3 {
   
2.         public static void main(String args[]) {
   
3.                 int[] lst = getReandArray(20, 100);
   
4.                 quickSort(lst, 0, lst.length - 1);
   
5.                 prtArray(lst);
   
6.         }
   
7. 
   
8.         // 获取指定长度的数组，内部填充int型随机数
   
9.         public static int[] getReandArray(int lenght, int max) {
   
10.                 int[] lst = new int[lenght];
    
11.                 for (int i = 0; i < lenght; i++)
    
12.                         lst[i] = (int) (Math.random() * max);
    
13.                 return lst;
    
14.         }
    
15. 
    
16.         // 自动输出数组
    
17.         public static void prtArray(int[] list) {
    
18.                 int i = 0;
    
19.                 while (i < list.length) {
    
20.                         System.out.print(list[i++] + "\t");
    
21.                 }
    
22.         }
    
23. 
    
24.         // 针对array类型的swap
    
25.         public static void swap(int[] lst, int x, int y) {
    
26.                 int temp = lst[x];
    
27.                 lst[x] = lst[y];
    
28.                 lst[y] = temp;
    
29.         }
    
30. 
    
31.         // 实现快排算法
    
32.         public static void quickSort(int[] list, int l, int r) {
    
33.                 int i = l + 1, j = r;
    
34.                 int key = list[l];
    
35. 
    
36.                 if (l >= r)
    
37.                         return;
    
38.                 while (true) {
    
39.                         while (list[j] > key)
    
40.                                 j--;
    
41.                         while (list[i] < key && i < j)
    
42.                                 i++;
    
43.                         if (i >= j)
    
44.                                 break;
    
45.                         swap(list, i, j);
    
46.                         if (list[i] == key)
    
47.                                 j--;
    
48.                         else
    
49.                                 i++;
    
50.                 }
    
51.                 swap(list, l, j);
    
52. 
    
53.                 if (l < i - 1)
    
54.                         quickSort(list, l, i - 1);
    
55.                 if (j + 1 < r)
    
56.                         quickSort(list, j + 1, r);
    
57.         }
    
58. }
    

复制代码

---

欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2