java排序2（选择排序）

so_brave

java排序2（选择排序）

Java代码

1. 1.package hello;   
   
2. 2.  
   
3. 3.import java.util.Random;   
   
4. 4.  
   
5. 5./**  
   
6. 6. * 书接上回--冒泡排序  
   
7. 7. *   
   
8. 8. * 选择排序: 它改进了冒泡排序,将必要的交换次数O(N*N)减少到了O(N). 但,比较次数仍然保持为O(N*N).  
   
9. 9. * 然而,选择排序仍然为大记录量的排序提出了一个比较重要的改进, 因为,这些大量的记录需要在内存中移动,这就使交换时间和比较时间 相比起来,交换时间更为重要.  
   
10. 10. * (一般来说,在java语言中不是这种情况,java中只是改变了引用位置, 而实际对象的位置并没有发生改变.)  
    
11. 11. */  
    
12. 12.public class ChooseSortApp {   
    
13. 13.    public static void main(String[] args) {   
    
14. 14.        long ls = System.currentTimeMillis();   
    
15. 15.        int maxSize = 100;   
    
16. 16.        SelectionSort arr;   
    
17. 17.        arr = new SelectionSort(maxSize);   
    
18. 18.        Random r = new Random();   
    
19. 19.        // insert 10 items   
    
20. 20.        for (int i = 0; i < 10; i++) {   
    
21. 21.            arr.insert(r.nextInt(100));   
    
22. 22.        }   
    
23. 23.        arr.display();   
    
24. 24.        arr.selectionSort();   
    
25. 25.        arr.display();   
    
26. 26.           
    
27. 27.        System.out.println(System.currentTimeMillis()-ls);   
    
28. 28.    }   
    
29. 29.}   
    
30. 30.  
    
31. 31.class SelectionSort extends BubbleSort {   
    
32. 32.    public SelectionSort(int max) {   
    
33. 33.        super(max);   
    
34. 34.    }   
    
35. 35.  
    
36. 36.    /*  
    
37. 37.     * 外层循环用循环变量out,从数组开头开始(数组下标为0)向高位增长. 内层循环用循环变量in,从out所指位置开始,同样是向右移位.  
    
38. 38.     * 在每一个in的新位置,数据项a[in]和a[min]进行比较. 如果a[in]更小,则min被赋值为in的值.  
    
39. 39.     * 在内层循环的最后,min指向最小的数据项,然后交换out和min指向的数组数据项  
    
40. 40.     */  
    
41. 41.    public void selectionSort() {   
    
42. 42.        int out, in, min;   
    
43. 43.        for (out = 0; out < nElems - 1; out++) {   
    
44. 44.            min = out;   
    
45. 45.            for (in = out + 1; in < nElems; in++) {   
    
46. 46.                if (a[in] < a[min])   
    
47. 47.                    min = in;   
    
48. 48.            }   
    
49. 49.            swap(out, min);   
    
50. 50.        }   
    
51. 51.    }   
    
52. 52.}  

复制代码

阳光的扣子

谢谢分享