算法导论Java实现-冒泡排序（思考题2-2）

1. package lhz.algorithm.chapter.two; 
2. /** 
3.  * “冒泡排序”,《算法导论》思考题2-2 
4.  * 伪代码： 
5.  * BUBBLESORT(A) 
6.  * 1 for i ← 1 to length[A] 
7.  * 2 do for j ← length[A] downto i + 1 
8.  * 3 do if A[j] < A[j - 1] 
9.  * 4 then exchange A[j] ↔ A[j - 1]  
10.  * @author lihzh(苦逼coder) 
11. * 本文地址：http://mushiqianmeng.blog.51cto.com/3970029/733277  
12. */ 
13. public class BubbleSort { 
14.      
15.     private static int[] input = new int[] { 2, 1, 5, 4, 9, 8, 6, 7, 10, 3 }; 
16.  
17.     public static void main(String[] args) { 
18.         int endIndex = input.length - 1; 
19.         for (int i = 0; i < endIndex; i++) {//复杂度：n 
20.             for (int j = endIndex; j > i; j--) {//复杂度：1+2+...+(n-1)=Θ(n^2) 
21.                 if (input[j] < input[j-1]) { 
22.                     int temp = input[j]; 
23.                     input[j] = input[j-1]; 
24.                     input[j-1] = temp; 
25.                 } 
26.             } 
27.         } 
28.         /* 
29.          * 复杂度分析： 
30.          * 由上可见冒泡排序的复杂度为：Θ(n^2)。在最佳情况下，虽无需交换，但比较的次数仍为：Θ(n^2)。 
31.          * 在最佳情况下，复杂度也为Θ(n^2)，此时不如插入排序。 
32.          * 冒泡排序的交换次数也大于插入排序。 
33.          * 冒泡排序对n个项目需要O(n2)的比较次数，且可以原地排序。 
34.          * 尽管这个算法是最简单了解和实作的排序算法之一，但它对于少数元素之外的数列排序是很没有效率的。 
35.          * 冒泡排序是稳定的。 
36.          */ 
37.         //打印数组 
38.         printArray(); 
39.     } 
40.      
41.     private static void printArray() { 
42.         for (int i : input) { 
43.             System.out.print(i + " "); 
44.         } 
45.     } 
46. } 

     本文转自mushiqianmeng 51CTO博客，原文链接：http://blog.51cto.com/mushiqianmeng/733277，如需转载请自行联系原作者