java實現排序算法:插入排序、選擇排序、冒泡排序

package sort;

/**

@author lei 2011-8-17
*/
public class Sort {
/**

選擇排序: 
首先在數組中查找最小值， 如果該值不在第一個位置， 那么將其和處在第一個位置的元素交換，然后從第二個位置重復
此過程，將剩下元素中最小值交換到第二個位置 。當到最后一位 時，數組排序結束 
復雜度為：O(n^2)

@param array
*/
static void selectionSort(int[] array) {
 for (int i = 0; i < array.length - 1; i++) {

 int min_idx = i;

 for (int j = i + 1; j < array.length; j++) {
     if (array[j] < array[min_idx]) {
         min_idx = j;
     }
 }

 if (min_idx != i) {
     swap(array, min_idx, i);
 }


}
}
/**

冒泡排序法: 
是運用數據值比較后，依判斷規則對數據位置進行交換，以達到排序的目的 
復雜度都是O(n^2)

@param array
*/
public static void bubbleSort(int[] array) {// 冒泡排序算法
 int out, in;
 // 外循環記錄冒泡次數
 for (out = array.length - 1; out >= 1; out--) {

 boolean flag = false;
 // 進行冒泡
 for (in = 0; in < out; in++) {
     // 交換數據
     if (array[in] > array[in + 1]) {
         swap(array, in, in + 1);
         flag = true;
     }
 }
 if (!flag) {
     break;
 }


}
}
/**

插入排序 
是對于欲排序的元素以插入的方式尋找該元素的適當位置，以達到排序的目的。 
插入排序的最差和平均情況的性能是O(n^2)

@param array
*/
public static void insertSort(int[] array) {// 插入排序算法
 int in, out;
 for (out = 1; out < array.length; out++) {// 外循環是給每個數據循環

 int temp = array[out]; // 先取出來保存到臨時變量里
 in = out; // in是記錄插入數據之前的每個數據下標
 // while內循環是找插入數據的位置，并且把該位置之后的數據（包括該位置）
 // 依次往后順移。
 while (in > 0 && array[in - 1] >= temp) {
     array[in] = array[in - 1]; // 往后順移
     --in; // 繼續往前搜索
 }
 array[in] = temp; // 該數據要插入的位置

}
}
/**

交換數組數據

@param array
@param min_idx
@param i
*/
private static void swap(int[] array, int min_idx, int i) {
 int temp = array[min_idx];
 array[min_idx] = array[i];
 array[i] = temp;
}
public static void main(String[] args) {
int[] array = new int[] { 1, 2, 6, 5, 7, 9, 0, 121, 4545 };
 bubbleSort(array);
 for (int i : array) {

 System.out.println(i);

}
}




}</pre>