排序算法 – JAVA編程語言程序開發技術文章

一、排序算法:
1、對文件(File)進行排序有重要的意義。如果文件按key有序,可對其折半查找,使查找效率提高;在數據庫(Data Base)和知識庫(Knowledge Base)等系統中,一般要建立若幹索引文件,就牽涉到排序問題;在一些計算機的應用系統中,要按不同的數據段作出若幹統計,也涉及到排序。排序效率的高低,直接影響到計算機的工作效率。
    另外,研究排序方法和算法,目的不單純是完成排序的功能和提高效率,其中對軟件人員的程序設計能力會有一定的提高。
 
    2、穩定排序和非穩定排序:設文件f=(R1……Ri……Rj……Rn)中記錄Ri、Rj(i≠j,i、j=1……n)的key相等,即Ki=Kj。若在排序前Ri領先於Rj,排序後Ri仍領先於Rj,則稱這種排序是穩定的,其含義是它沒有破壞原本已有序的次序。反之,若排序後Ri與Rj的次序有可能顛倒,則這種排序是非穩定的,即它有可能破壞瞭原本已有序記錄的次序。
 
3、內部排序和外部排序:若待排文件f在計算機的內存儲器中,且排序過程也在內存中進行,稱這種排序為內排序。內排序速度快,但由於內存容量一般很小,文件的長度(記錄個數)n受到一定限制。若排序中的文件存入外存儲器,排序過程借助於內外存數據交換(或歸並)來完成,則稱這種排序為外排序。我們重點討論內排序的一些方法、算法以及時間復雜度的分析。
A、插入排序的工作原理是通過構建有序序列,對於未排序數據,在已排序序列中從後向前掃描,找到相應位置並插入。其具體步驟參見代碼及註釋。

/** 
 * 插入排序<br/> 
 * <ul> 
 * <li>從第一個元素開始,該元素可以認為已經被排序</li> 
 * <li>取出下一個元素,在已經排序的元素序列中從後向前掃描</li> 
 * <li>如果該元素(已排序)大於新元素,將該元素移到下一位置</li> 
 * <li>重復步驟3,直到找到已排序的元素小於或者等於新元素的位置</li> 
 * <li>將新元素插入到該位置中</li> 
 * <li>重復步驟2</li> 
 * </ul> 
 *  
 * @param numbers 
 */ 
publicstaticvoid insertSort(int[] numbers) {  
    int size = numbers.length, temp, j;  
    for(int i=1; i<size; i++) {  
        temp = numbers[i];  
        for(j = i; j > 0 && temp < numbers[j-1]; j–)  
            numbers[j] = numbers[j-1];  
        numbers[j] = temp;  
    }  
}

B、冒泡排序是一種簡單的排序算法。它重復地走訪過要排序的數列,一次比較兩個元素,如果他們的順序錯誤就把他們交換過來。走訪數列的工作是重復地進行直到沒有再需要交換,也就是說該數列已經排序完成。這個算法的名字由來是因為越小的元素會經由交換慢慢“浮”到數列的頂端。
以下程序已經經過驗證,可以運行。
/** 
 * 冒泡法排序<br/> 

 * <li>比較相鄰的元素。如果第一個比第二個大,就交換他們兩個。</li> 
 * <li>對每一對相鄰元素作同樣的工作,從開始第一對到結尾的最後一對。在這一點,最後的元素應該會是最大的數。</li> 
 * <li>針對所有的元素重復以上的步驟,除瞭最後一個。</li> 
 * <li>持續每次對越來越少的元素重復上面的步驟,直到沒有任何一對數字需要比較。</li> 

 *  
 * @param numbers 
 *            需要排序的整型數組 
 */ 
publicstaticvoid bubbleSort(int[] numbers) {  
    int temp; // 記錄臨時中間值  
    int size = numbers.length; // 數組大小  
    for (int i = 0; i < size – 1; i++) {  
        for (int j = i + 1; j < size; j++) {  
            if (numbers[i] < numbers[j]) { // 交換兩數的位置  
                temp = numbers[i];  
                numbers[i] = numbers[j];  
                numbers[j] = temp;  
            }  
        }  
    }  
}

C、快速排序使用分治法策略來把一個序列分為兩個子序列。
 
/** 
 * 快速排序<br/> 
 * <ul> 
 * <li>從數列中挑出一個元素,稱為“基準”</li> 
 * <li>重新排序數列,所有元素比基準值小的擺放在基準前面,所有元素比基準值大的擺在基準的後面(相同的數可以到任一邊)。在這個分割之後, 
 * 該基準是它的最後位置。這個稱為分割(partition)操作。</li> 
 * <li>遞歸地把小於基準值元素的子數列和大於基準值元素的子數列排序。</li> 
 * </ul> 
 *  
 * @param numbers 
 * @param start 
 * @param end 
 */ 
publicstaticvoid quickSort(int[] numbers, int start, int end) {  
    if (start < end) {  
        int base = numbers[start]; // 選定的基準值(第一個數值作為基準值)  
        int temp; // 記錄臨時中間值  
        int i = start, j = end;  
        do {  
            while ((numbers[i] < base) && (i < end))  
                i++;  
            while ((numbers[j] > base) && (j > start))  
                j–;  
            if (i <= j) {  
                temp = numbers[i];  
                numbers[i] = numbers[j];  
                numbers[j] = temp;  
                i++;  
                j–;  
            }  
        } while (i <= j);  
        if (start < j)  
            quickSort(numbers, start, j);  
        if (end > i)  
            quickSort(numbers, i, end);  
    }  

D、選擇排序是一種簡單直觀的排序方法,每次尋找序列中的最小值,然後放在最末尾的位置。
 
/** 
 * 選擇排序<br/> 
 * <li>在未排序序列中找到最小元素,存放到排序序列的起始位置</li> 
 * <li>再從剩餘未排序元素中繼續尋找最小元素,然後放到排序序列末尾。</li> 
 * <li>以此類推,直到所有元素均排序完畢。</li> 

 *  
 * @param numbers 
 */ 
publicstaticvoid selectSort(int[] numbers) {  
    int size = numbers.length, temp;  
    for (int i = 0; i < size; i++) {  
        int k = i;  
        for (int j = size – 1; j >i; j–)  {  
            if (numbers[j] < numbers[k])  k = j;  
        }  
        temp = numbers[i];  
        numbers[i] = numbers[k];  
        numbers[k] = temp;  
    }  

E、歸並排序是建立在歸並操作上的一種有效的排序算法,歸並是指將兩個已經排序的序列合並成一個序列的操作。參考代碼如下:
 /** 
 * 歸並排序<br/> 
 * <ul> 
 * <li>申請空間,使其大小為兩個已經排序序列之和,該空間用來存放合並後的序列</li> 
 * <li>設定兩個指針,最初位置分別為兩個已經排序序列的起始位置</li> 
 * <li>比較兩個指針所指向的元素,選擇相對小的元素放入到合並空間,並移動指針到下一位置</li> 
 * <li>重復步驟3直到某一指針達到序列尾</li> 
 * <li>將另一序列剩下的所有元素直接復制到合並序列尾</li> 
 * </ul> 
 *  
 * @param numbers 
 */ 
publicstaticvoid mergeSort(int[] numbers, int left, int right) {  
    int t = 1;// 每組元素個數  
    int size = right – left + 1;  
    while (t < size) {  
        int s = t;// 本次循環每組元素個數  
        t = 2 * s;  
        int i = left;  
        while (i + (t – 1) < size) {  
            merge(numbers, i, i + (s – 1), i + (t – 1));  
            i += t;  
        }  
        if (i + (s – 1) < right)  
            merge(numbers, i, i + (s – 1), right);  
    }  
}  
/** 
 * 歸並算法實現 
 *  
 * @param data 
 * @param p 
 * @param q 
 * @param r 
 */ 
privatestaticvoid merge(int[] data, int p, int q, int r) {  
    int[] B = newint[data.length];  
    int s = p;  
    int t = q + 1;  
    int k = p;  
    while (s <= q && t <= r) {  
        if (data[s] <= data[t]) {  
            B[k] = data[s];  
            s++;  
        } else {  
            B[k] = data[t];  
            t++;  
        }  
        k++;   www.aiwalls.com
    }  
    if (s == q + 1)  
        B[k++] = data[t++];  
    else 
        B[k++] = data[s++];  
    for (int i = p; i <= r; i++)  
        data[i] = B[i];  

作者:lhfight

發佈留言

發佈留言必須填寫的電子郵件地址不會公開。 必填欄位標示為 *