java冒泡，插入，选择排序

转载于
http://www.talentdigger.cn/home/space-3615-do-blog-id-16914.html

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

public class TestSort{
       public static void bubbleSort(int[] a) {
      for (int j = a.length - 1; j > 0; j--)
     for (int i = 0; i < j; i++)
           if (a[i] > a[i+1])
           {     a[i] = a[i] + a[i+1];
                 a[i+1] = a[i] - a[i+1];
                 a[i] = a[i] - a[i+1];
      }
 }
      public static void main(String[] args) {
             int[] a = new int[]{28,17,54,48,36,25,11,60,71};
             System.out.print("排序前: ");   
            for (int i = 0; i < a.length; i++)   
                       System.out.printf("%3s", a[i]);   
                        System.out.println();
             bubbleSort(a);
             System.out.print("排序后: ");  
            for (int i = 0; i < a.length; i++)   
                       System.out.printf("%3s", a[i]);   
                        System.out.println();   
                    }
      }
=====================================================
public class TestSort{   
    public static void main(String[] args) {   
           int[] a = new int[]{28,17,54,48,36,25,11,60,71};
             System.out.print("排序前: ");   
            for (int i = 0; i < a.length; i++)   
                       System.out.printf("%3s", a[i]);   
                        System.out.println();
      bubbleSort(a);
      System.out.print("排序后: ");  
            for (int i = 0; i < a.length; i++)   
                       System.out.printf("%3s", a[i]);   
                        System.out.println(); 
   }   
public static void bubbleSort(int[] a) {   
           int len = a.length;      
           System.out.println("数组大小是:" + len);      
           boolean change = false;   
           int temp;   
           int count = 0;     
           for (int i = len; i > 1; i--) {   
          for (int j = 0; j < i - 1; j++) {   
          if (a[j + 1] < a[j]) {   
             temp = a[j + 1];   
             a[j + 1] = a[j];   
             a[j] = temp;   
             change = true;   
             count++;   
         }       
       }   
      if (change) {   
         System.out.print("第" + count + "趟交换:   ");   
               for (int k = 0; k < len; k++)   
             System.out.print(a[k] + " ");      
               System.out.println();   
       }   
     }   
   }   
}

2、选择排序 Selection Sort
选择排序的基本思想是：对待排序的记录序列进行n-1遍的处理，第1遍处理是将L[1..n]中最小者与L[1]交换位置，第2遍处理是将L[2..n]中最小者与L[2]交换位置，......，第i遍处理是将L[i..n]中最小者与L[i]交换位置。这样，经过i遍处理之后，前i个记录的位置就已经按从小到大的顺序排列好了。
　　当然，实际操作时，也可以根据需要，通过从待排序的记录中选择最大者与其首记录交换位置，按从大到小的顺序进行排序处理。
算法如下：

 public class SelectSort {  
      public static void main(String[] args) {
      int[] a = new int[]{28,17,54,48,36,25,11,60,71};
             System.out.print("排序前: ");   
            for (int i = 0; i < a.length; i++)   
                       System.out.printf("%3s", a[i]);   
                        System.out.println();
             selectSort(a);
             System.out.print("排序后: ");   
            for (int i = 0; i < a.length; i++)   
                       System.out.printf("%3s", a[i]);   
                        System.out.println();   
                    }
 public static  void selectSort(int[] a){  
        int temp = 0;  
        for(int i=0;i<a.length;i++){  
            int k = 0;  
            for(int j=0;j<a.length-i;j++){  
                if(a[j]>a[k]){  
                    k = j;  
                }  
            }  
            temp = a[a.length-i-1];  
            a[a.length-i-1] = a[k];  
            a[k] = temp;  
        }  
        for(int i=0;i<a.length;i++){  
           }
      }  
}

3、插入排序 Insertion Sort
插入排序的基本思想是，经过i-1遍处理后,L[1..i-1]己排好序。第i遍处理仅将L[i]插入L[1..i-1]的适当位置，使得L[1..i]又是排好序的序列。要达到这个目的，我们可以用顺序比较的方法。首先比较L[i]和L[i-1]，如果L[i-1]≤ L[i]?则L[1..i]已排好序，第i遍处理就结束了；否则交换L[i]与L[i-1]的位置，继续比较L[i-1]和L[i-2]，直到找到某一个位置j(1≤j≤i-1)，使得L[j] ≤L[j+1]时为止。
　　简言之,插入排序就是每一步都将一个待排数据按其大小插入到已经排序的数据中的适当位置，直到全部插入完毕。插入排序方法分直接插入排序和折半插入排序两种，这里只介绍直接插入排序，折半插入排序留到“查找”内容中进行。
在下面的插入排序算法中，为了写程序方便我们可以引入一个哨兵元素L[0]，它小于L[1..n]中任一记录。所以，我们设元素的类型ElementType中有一个常量-∞，它比可能出现的任何记录都小。如果常量-∞不好事先确定，就必须在决定L[i]是否向前移动之前检查当前位置是否为1，若当前位置已经为1时就应结束第i遍的处理。另一个办法是在第i遍处理开始时，就将L[i]放入L[0]中，这样也可以保证在适当的时候结束第i遍处理。下面的算法中将对当前位置进行判断。
算法如下：(FOR循环实现)
   

 public class InsertSort{   
 public static int[] a = { 10, 32, 1, 9, 5, 7, 12, 0, 4, 3 }; // 预设数据数组  
 public static void main(String args[]) {   
           int i; // 循环计数变量   
           int Index = a.length;// 数据索引变量  
                 System.out.print("排序前: ");   
                  for (i = 0; i < Index - 1; i++)   
                System.out.print(" " + a[i] + " ");   
                 System.out.println("");      
          InsertSort(Index - 1); // 选择排序   
           System.out.print("排序后: ");   // 排序后结果    
           for (i = 0; i < Index - 1; i++)   
         System.out.print(" " + a[i] + " ");   
          System.out.println("");   
   }  
  public static void InsertSort(int Index) {   
           int i, j, k; // 循环计数变量   
           int InsertNode; // 欲插入数据变量  
           for (i = 1; i < Index; i++) // 依序插入数值   
     {  InsertNode = a[i]; // 设定欲插入的数值   
             j = i - 1; // 欲插入数组的开始位置   
                // 找适当的插入位置   
             while (j >= 0 && InsertNode < a[j]) {   
              a[j + 1] = a[j];   
              j--;   
                }   
         a[j + 1] = InsertNode; // 将数值插入   
                // 打印目前排序结果   
         System.out.print("排序中: ");    
                for (k = 0; k < Index; k++)   
              System.out.print(" " + a[k] + " ");   
                System.out.println("");   
          }   
     }   
}