package sort;
 
/**
 * @author lei 2011-8-17
 */
public class Sort {
 
    /**
     * 選擇排序: 
     * 首先在數(shù)組中查找最小值， 如果該值不在第一個位置， 那么將其和處在第一個位置的元素交換，然后從第二個位置重復
     * 此過程，將剩下元素中最小值交換到第二個位置 。當?shù)阶詈笠晃?時，數(shù)組排序結(jié)束 
     * 復雜度為：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);
            }
 
        }
    }
 
    /**
     * 冒泡排序法: 
     * 是運用數(shù)據(jù)值比較后，依判斷規(guī)則對數(shù)據(jù)位置進行交換，以達到排序的目的 
     * 復雜度都是O(n^2)
     * 
     * @param array
     */
    public static void bubbleSort(int[] array) {// 冒泡排序算法
        int out, in;
        // 外循環(huán)記錄冒泡次數(shù)
        for (out = array.length - 1; out >= 1; out--) {
            boolean flag = false;
            // 進行冒泡
            for (in = 0; in < out; in++) {
                // 交換數(shù)據(jù)
                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++) {// 外循環(huán)是給每個數(shù)據(jù)循環(huán)
            int temp = array[out]; // 先取出來保存到臨時變量里
            in = out; // in是記錄插入數(shù)據(jù)之前的每個數(shù)據(jù)下標
            // while內(nèi)循環(huán)是找插入數(shù)據(jù)的位置，并且把該位置之后的數(shù)據(jù)（包括該位置）
            // 依次往后順移。
            while (in > 0 && array[in - 1] >= temp) {
                array[in] = array[in - 1]; // 往后順移
                --in; // 繼續(xù)往前搜索
            }
            array[in] = temp; // 該數(shù)據(jù)要插入的位置
        }
    }
 
    /**
     * 交換數(shù)組數(shù)據(jù)
     * 
     * @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);
        }
 
    }
 
}

標簽： swap 搜索

版權(quán)申明：本站文章部分自網(wǎng)絡(luò)，如有侵權(quán)，請聯(lián)系：west999com@outlook.com
特別注意：本站所有轉(zhuǎn)載文章言論不代表本站觀點！
本站所提供的圖片等素材，版權(quán)歸原作者所有，如需使用，請與原作者聯(lián)系。