java實現插入、冒泡、選擇、快速排序、二分查找

jopen 10年前發布 | 20K 次閱讀 Java開發 Java
一. 直接插入排序
void insertSort( int[] a){
       for( int i=1;i             if (a[i]                temp = a[i];   //1 
               a[i] = a[i-1];  //2

                // 繼續和前面的進行比較
                for( int j=i-2; j>=0; j--){
                     if(temp < a[j])
                         a[j+1] =a[j]; //3
               }
               a[j+1] = temp; //4
           }
      }
}

算法(簡要描述):
1. temp保存被比較的數值
2. 前一位數值移動到被比較的數值的位置
3. 前面的繼續往后移動
4. 把被比較的數值放到適當的位置
java實現插入、冒泡、選擇、快速排序、二分查找


二.冒泡排序
  冒泡排序，就是從最底那個開始往上比較，遇到比它小的就交換，相當于過五關看六將，不斷地向前沖。接著循環第二個...
+-----+     void bubbleSort( int[] a){ 
| a[6] |             //每個都進行冒泡(一個一個來) 
+-----+             for ( int i=0; i | a[5] |    
+-----+                     //和后面的每個都進行比較(過五關看六將) 
| a[4] |                     for ( int j=i; j +-----+                             if (a[j]>a[j+1]){ 
| a[3] |                                    temp = a[j]; 
+-----+                                    a[j] = a[j+1]; 
| a[2] |                                    a[j+1] = temp; 
+-----+                            } 
| a[1] |                    } 
+-----+            } 
| a[0] |    } 
+-----+

三.選擇排序
  選擇排序，就是選擇最小的，然后置換，循環再找到最小的，再置換...
void selectSort( int[] a){ 
         for ( int i=0; i                 small = i; 

                 //找出最小的 
                  for ( int j=i+1; j                          if (a[small]>a[j]){ 
                                small = j; 
                        } 
                } 

                 //置換位置 
                  if (i != small){ 
                        temp = a[small]; 
                        a[small] = a[i]; 
                        a]i] = temp; 
                } 
        } 
}

四.快速排序
  快速排序的基本過程:
  得到樞軸索引：compare首先從high位置向前搜索找到第一個小于compare值的索引，并置換(這時high索引位置上的值為compare 值)；然后從low位置往后搜索找到第一個大于compare值的索引，并與high索引上的值置換(這時low索引位置上的值為compare值)；重 復這兩步直到low=high為止。
  得到樞軸索引后，則遞歸進行樞軸兩邊的隊列的排序....
void quickSort( int[] a,  int low,  int high) { 
        p = get(a, low, high); 
        quickSort(a, low, p-1); 
        quickSort(a, p+1, high); 
} 

int get( int[] a,  int low,  int high){ 
     compare = a[low]; 

      while(low < high){  //無論如何置換, 被置換的都包含compare的值
          while(low=compare)    
              high--; 

          //在 low
         temp = a[low];
         a[low] = a[high];
         a[high] = temp;

          while(low               low++; 

          //在 lowcompare并置換 
          temp = a[low]; 
          a[low] = a[high]; 
          a[high] = temp; 
     } 
      return low;  //while(low==hight)停止循環, 并返回樞軸位置 
}

五.二分查找
  二分查找原理很容易懂，想象為二叉查找樹就明白了。
int binarySearch( int[] a,  int value){ 
         int low = 0; 
         int high = a.length-1; 
         
         while(low <= high){ 
                mid = (low+high)/2;  //**
                 if (a[mid] == value) 
                         return mid; 
                 else  if (a[mid] > value) 
                        high = mid-1; 
                 else 
                        low = mid +1; 
        } 
         return -1; 
}
     ** mid = (low + high) / 2; 有問題，當low + high大于int范圍時就會溢出的。Sun的jdk里面的二分查找源碼原先也有同樣的問題。
    解決的方法是mid = low/2 + high/2。這樣用2先除一下，就不會溢出了。

原文地址：http://android.blog.51cto.com/268543/130450
 本文由用戶 jopen 自行上傳分享，僅供網友學習交流。所有權歸原作者，若您的權利被侵害，請聯系管理員。
 轉載本站原創文章，請注明出處，并保留原始鏈接、圖片水印。
 本站是一個以用戶分享為主的開源技術平臺，歡迎各類分享！