黑马程序员技术交流社区

标题: 快速排序与堆排序的代码小示例 [打印本页]

---

作者: firwood    时间: 2015-7-2 21:20
标题: 快速排序与堆排序的代码小示例
学习排序，写了快速排序和堆排序的函数。

Sort.java

1. package sort;
   
2. import java.lang.*;
   
3. /**
   
4. *
   
5. * @author Firwood
   
6. */
   
7. public class Sort {
   
8. 
   
9.     /**
   
10.      * @param args the command line arguments
    
11.      */
    
12.     public static void main(String[] args) {
    
13.         // TODO code application logic here
    
14.         System.out.println("This is Test");
    
15. 
    
16.         Quicks h = new Quicks(10);
    
17.         for(int i=0;i<h.length;i++) {
    
18.                 h.a[i] = (int)(Math.random()*100);               
    
19.         }
    
20.         h.Output();
    
21.         System.out.println("------------------------------------------------------");
    
22.         //h.Build();
    
23.         h.sort();
    
24.         h.Output();
    
25.     }
    
26. }
    

复制代码

Quicks.java

1. package sort;
   
2. public class Quicks {
   
3.         //
   
4.         int[] a;
   
5.         int length;
   
6.         Quicks() {//默认生成20个元素的数组来存储数字
   
7.             a = new int[20];
   
8.             length = 20;
   
9.         }
   
10.         Quicks(int x) {
    
11.             a = new int[x];
    
12.             length = x;
    
13.         }
    
14.         int Part(int p, int r) {
    
15.             int x = a[r];
    
16.             int i = p - 1;
    
17.             for( int j = p; j <= r-1; j++) {
    
18.                 if( a[j] <= x ) {
    
19.                     i++;
    
20.                     int temp = a[i];
    
21.                     a[i] = a[j];
    
22.                     a[j] = temp;
    
23.                 }
    
24.             }
    
25.             int tem = a[i+1];
    
26.             a[i+1] = a[r];
    
27.             a[r] = tem;
    
28.             return i+1;
    
29.         }
    
30.         int Quicksort(int p, int r) {
    
31.             if( p < r ) {
    
32.                 int q = Part(p,r);
    
33.                 Quicksort(p,q-1);//排序前一部分
    
34.                 Quicksort(q+1,r);//排序后一部分
    
35.             }
    
36.             return 0;
    
37.         }
    
38.         int sort() {
    
39.             Quicksort(0,length-1);
    
40.             return 0;
    
41.         }
    
42.         int Output() {//输出数组的内容
    
43.                 for(int i=0;i<length;i++) {
    
44.                         System.out.printf("%d ",a[i]);
    
45.                 }
    
46.                 System.out.printf("\n");
    
47.                 return 0;
    
48.         }
    
49. }
    

复制代码

Heapt.java

1. package sort;
   
2. import java.lang.*;
   
3. 
   
4. public class Heapt {
   
5.         int[] a;
   
6.         int length;
   
7.         Heapt() {
   
8.                 a = new int[20];
   
9.                 length = 20;
   
10.         }
    
11.         Heapt(int n) {
    
12.                 a = new int[n];
    
13.                 length = n;
    
14.         }
    
15.        
    
16.         int left(int i) {
    
17.                 return 2*i+1;
    
18.         }
    
19.         int right(int i) {
    
20.                 return 2*i+2;
    
21.         }
    
22.         int parent(int i) {
    
23.                 return ((i+1)/2-1);
    
24.         }
    
25.         int exchange(int x,int y) {
    
26.                 int temp = a[x];
    
27.                 a[x] = a[y];
    
28.                 a[y] = temp;
    
29.                 return 0;
    
30.         }
    
31.         int Max_Heap(int i,int len) {
    
32.                 int r = right(i);
    
33.                 int l = left(i);
    
34.                 int p = parent(i);
    
35.                
    
36.                 int largest = i;
    
37.                 if(l < len && a[l] > a[largest]) largest = l;
    
38.                 else largest = i;
    
39.                
    
40.                 if(r < len && a[r] > a[largest]) largest = r;
    
41.                
    
42.                 if(largest != i) {
    
43.                         exchange(i,largest);
    
44.                         Max_Heap(largest,len);
    
45.                 }
    
46.                
    
47.                 return 0;
    
48.         }
    
49.         int Build() {
    
50.                 for(int i=(length)/2; i>=0;i--) {
    
51.                         Max_Heap(i,length);
    
52.                 }
    
53.                 return 0;
    
54.         }
    
55.         int sort() {
    
56.                 Build();
    
57.                 int tt = length;
    
58.                 while(tt > 1) {
    
59.                         tt--;
    
60.                         exchange(0,tt);
    
61.                         Max_Heap(0,tt);
    
62.                 }
    
63.                 return 0;
    
64.         }
    
65.         int Output() {
    
66.                 for(int i=0;i<length;i++) {
    
67.                         System.out.printf("%d ",a[i]);
    
68.                 }
    
69.                 System.out.printf("\n");
    
70.                 return 0;
    
71.         }
    
72.        
    
73. }
    

复制代码

---

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

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