Java 算法，

Java 算法，

一、冒泡排序法：
最简单的排序方法是冒泡排序方法。这种方法的基本思想是，将待排序的元素看作是竖着排列的“气泡”，较小的元素比较轻，从而要往上浮。
在冒泡排序算法中我们要对这个“气泡”序列处理若干遍。所谓一遍处理，就是自底向上检查一遍这个序列，并时刻注意两个相邻的元素的顺序是否正确。
如果发现两个相邻元素的顺序不对，即“轻”的元素在下面，就交换它们的位置。
显然，处理一遍之后，“最轻”的元素就浮到了最高位置；处理二遍之后，“次轻”的元素就浮到了次高位置。
在作第二遍处理时，由于最高位置上的元素已是“最轻”元素，所以不必检查。
一般地，第i遍处理时，不必检查第i高位置以上的元素，因为经过前面i-1遍的处理，它们已正确地排好序。这个算法可实现如下。

 

Java代码  

1. public class BubbleSort {   
2.  static void bubbleSort(int[] nums){  
3.   for(int i = 0;i<nums.length;i++){  
4.    int temp = 0;  
5.    for (int j = i+1; j < nums.length; j++) {  
6.     if(nums[i]>nums[j]){  
7.      temp = nums[i];  
8.      nums[i]=nums[j];  
9.      nums[j]=temp;  
10.     }  
11.    }   
12.   }   
13.   }   
14.   public static void main(String[] args){  
15.         int []  nums = {2,5,47,8,6,2,1,4,6,3,5,9};  
16.         long l1 = System.nanoTime();  
17.         bubbleSort(nums);  
18.         for(int i=0;i<nums.length;i++){  
19.            System.out.print(nums[i]+" ");  
20.         }  
21.         long l2 = System.nanoTime();  
22.         System.out.println("bubbleSort spends ("+(l2-l1)+")");  
23.   }   
24. }  

 

优点：稳定，比较次数已知；
缺点：慢，每次只能移动相邻两个数据，移动数据的次数多。

二、选择排序法（冒泡排序的改进版）：
每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完。
　选择排序是稳定的排序方法(很多教科书都说选择排序是不稳定的，但是，完全可以将其实现成稳定的排序方法)。 　　
n个记录的文件的直接选择排序可经过n-1趟直接选择排序得到有序结果： 　　
①初始状态：无序区为R[1..n]，有序区为空。 　　
②第1趟排序 　　在无序区R[1..n]中选出关键字最小的记录R[k]，将它与无序区的第1个记录R[1]交换，使R[1..1]和R[2..n]分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区。
③第i趟排序 　　第i趟排序开始时，当前有序区和无序区分别为R[1..i-1]和R(1≤i≤n-1)。
该趟排序从当前无序区中选出关键字最小的记录 R[k]，将它与无序区的第1个记录R交换，使R[1..i]和R分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区。 　　
这样，n个记录的文件的直接选择排序可经过n-1趟直接选择排序得到有序结果。 　　

优点：移动数据的次数已知（n-1次）； 　　缺点：比较次数多。

Java代码  

1. public class SelectionSort {   
2.  public static void main(String[] args) {  
3.   int[] data = {1,9,5,6,0,2,6,8,9};  
4.   SelectionSort sort = new SelectionSort();  
5.   sort.sort(data);  
6.   for (int i = 0; i < data.length; i++) {  
7.    System.out.print(data[i]+"  ");  
8.   }   
9.  }   
10.     public  void sort(int[] data) {   
11.         for (int i = 0; i < data.length; i++) {  
12.             int lowIndex = i;   
13.             for (int j = data.length - 1; j > i; j--) {  
14.                 if (data[j] < data[lowIndex]) {  
15.                     lowIndex = j;  
16.                 }  
17.             }    
18.             int temp = data[i];  
19.             data[i] = data[lowIndex];  
20.             data[lowIndex] = temp;  
21.         }  
22.     }   
23. }  

 

优点：稳定，比较次数与冒泡排序一样；
缺点：相对之下还是慢。

三、插入排序
插入排序：已知一组升序排列数据a[1]、a[2]、……a[n]，一组无序数据b[1]、b[2]、……b[m]，
需将二者合并成一个升序数列。首先比较b[1]与a[1]的值，若b[1]大于a[1]，则跳过，比较b[1]与a[2]的值，若b[1]仍然大于a[2]，则继续跳过，
直到b[1]小于a数组中某一数据a[x]，则将a[x]~a[n]分别向后移动一位，将b[1]插入到原来a[x]的位置这就完成了b[1]的插入。b[2]~b[m]用相同方法插入。
（若无数组a，可将b[1]当作n=1的数组a） 　　

Java代码  

1. public class InsertSort {   
2.      public void sort(int[] data) {  
3.           for(int i=1;i<data.length;i++){  
4.              for(int j=i;(j>0)&&(data[j]<data[j-1]);j--){  
5.               int temp = data[j];  
6.         data[j]= data[j-1];  
7.         data[j-1] = temp;  
8.              }  
9.          }          
10.      }   
11.      public static void main(String[] args) {  
12.    int[] data = {1,9,5,6,0,2,6,8,9};  
13.    InsertSort sort = new InsertSort();  
14.    sort.sort(data);  
15.    for (int i = 0; i < data.length; i++) {  
16.     System.out.print(data[i]+"  ");  
17.    }   
18.   }    
19. }  

  

优点：稳定，快； 　　
缺点：比较次数不一定，比较次数越少，插入点后的数据移动越多，特别是当数据总量庞大的时候，但用链表可以解决这个问题。

四、快速排序法： ----暂时没看懂，暂无代码
快速排序是冒泡排序的改进版，是目前已知的最快的排序方法。
已知一组无序数据a[1]、a[2]、……a[n]，需将其按升序排列。
首先任取数据a[x]作为基准。
比较a[x]与其它数据并排序，使a[x]排在数据的第k位，并且使a[1]~a[k-1]中的每一个数据<a[x]，a[k+1]~a[n]中的每一个数据>a[x]，
然后采用分治的策略分别对a[1]~a[k-1]和a[k+1]~a[n]两组数据进行快速排序。

 

优点：极快，数据移动少；
缺点：不稳定。