排序（ 冒泡 选择 插入 ）

排序

-----------学习笔记

冒泡排序：

基本思想：两两比较相邻的关键字，若反序则交换，直到无反序。 [java]  view plain  copy

1. <pre name="code" class="java">    boolean  flag = true;   //标记变量flag  
2.     int len = num.length;  
3.     for (int i=0; i<len-1 && flag; i++){  
4.         flag = false;  
5.         for (int j=len-1; j>i; j--){  
6.             if (num[j] < num[j-1]){  
7.                 swap(num[j+1], num[j]);// 交换两个数的位置  
8.                 flag = true;  
9.             }  
10.         }  
11.     }  

flag为标记， 如：{2，1，3，4，5，6，7，8，9}经过一次排序已经完成，无需再次排序，则完成排序； 时间复杂度：最后情况运行n-1次，最坏情况（逆序）运行1+2+3+…+(n-1) = n(n-1)/2,总的时间那复杂度为O(n^2);

简单选择排序：

基本思想：通过n-1次的比较，从n-i-1的关键字中找到最小（或最大）值，将它与第i个关键字交换。 [java]  view plain  copy

1. int len = num.length;  
2. for (int i=0; i<len-1; i++){  
3.     for (int j=i+1;j<len-1; j++){  
4.         if (num[i] > num[j]){  
5.             swap(num[i], num[j]);  
6.         }  
7.     }  
8. }  

时间复杂度：无论最好或者最坏的情况，都是需要比较(n-1) + (n-2）+（n-1) + …+1 = n(n-1)/2。时间复杂度为O(n^2)，

但是其交换次数较少，总的来说，性能优于冒泡排序。

直接插入排序：

基本思想：将记录插入一个已经排序好的序列中。 [java]  view plain  copy

1. int len = num.length;  
2. int temp;  
3. int j;  
4. for (int i=0; i<len-1; i++){  
5.     if (num[i+1] < num[i]){  
6.         temp = num[i+1];  
7.         for (j=i+1; num[j-1] > temp && j>=0; j--){  
8.             num[j] = num[j-1];  
9.         }  
10.         num[j] = temp;  
11.     }  
12. }  

时间复杂度：当最好情况，即顺序，需要比较n-1次；  当最坏情况，需要比较（n+2）(n-1)/2 , 需要交换（n+4）(n-1)/ 2 然而当排序记录是随机的，根据概率相同的原则，平均比较和移动次数为n^2/4， 比选择和冒泡的性能高一些