• 冒泡排序
• 選擇排序
• 插入排序
• 希爾排序

冒泡排序

思想:

1. 比較相鄰的元素。如果第一個比第二個大，就交換他們兩個。
2. 對每一對相鄰元素作同樣的工作，從開始第一對到結(jié)尾的最后一對。在這一點，最后的元素應(yīng)該會是最大的數(shù)。
3. 針對所有的元素重復(fù)以上的步驟，除了最后一個。
4. 持續(xù)每次對越來越少的元素重復(fù)上面的步驟，直到?jīng)]有任何一對數(shù)字需要比較

效率:

比較:N - 1 + N - 2 + ...+ 3 + 2 + 1 ~O(N²/2)
交換:最少 0次 最多比較一次交換一次

即:N - 1 + N - 2 + ...+ 3 + 2 + 1 ~O(N²/2)

說明:

冒泡排序手繪

Code

    int a[10] = {4, 2, 5, 7, 8, 9, 10, 1, 6, 3};
    
    for (int i = 0; i < 10 - 1; i++) {
        
        for (int j = 0; j < 10 - i - 1; j++) {
            if (a[j] > a[j + 1]) {
                exchange(&a[j], &a[j + 1]);
            }
        }
        
    }

選擇排序

思想:

1. 找出數(shù)組中最小的那個元素，與數(shù)組中的第一個元素交換(如果第一個元素就是最小的元素那么它就和自己交換)。
2. 找出剩下元素中最小的元素，與數(shù)組中的第一個元素交換。如此往復(fù)， 直到將整個數(shù)組排序。

效率:對于長度為N的數(shù)組,選擇排序需要大約N²/2次比較和N次交換

說明:

• 對于思想的第1步,找出數(shù)組中最小的那個元素需要次數(shù):
  2 1 3 4 5五個數(shù)找出最小, 假設(shè)第一個最小,后邊依次比較如果更小就交換,所以5個數(shù)字找出最小的那個數(shù)需要4次比較。

所以比較次數(shù):

N-1 + N-2 + ...+ 3 + 2 + 1 = na₁ + n(n-1)d/2 = N(N-1)/2

選擇排序

Code

     int a[] = {2, 8, 7, 1, 3, 5, 6, 4};
    
    for (int i = 0; i < N; i++) {
        int index = i;
        
        for (int j = i + 1; j < N; j++) {
            
            if (a[j] < a[index]) {
                index = j;
            }
            exchange(&a[index], &a[i]);
        }
        
    }

插入排序

思想:

1. 比如把4 插入 1 2 5 6 中
2. 4 < 6 前繼續(xù)找合適位置插入, 4 < 5繼續(xù) 但是2 < 4 故 4 插入2 5之間。

效率:對于長度為N的數(shù)組且主鍵不重復(fù)的數(shù)組， 平均插入需要_{N^2/4次比較以及}N^{2/4交換。最壞需要~N}2/2次比較和~N^2/2次交換, 最好需要N-1次比較和0次交換

說明:

插入排序

可見紅色箭頭移動一次累加比較次數(shù)：1 + 2 + 3 因為a[j] 都比a[j - 1]小 所以比較次數(shù)很多。交換 1 + 2 + 3次。

但是 如果是 【1 2 3 4】 比較 3次 交換0次。

Code

     int a[10] = {4, 2, 5, 7, 8, 9, 10, 1, 6, 3};
    
    for (int i = 1; i < N; i++) {
        
        for (int j = i; j > 0 && a[j] < a[j - 1]; j--) {
            exchange(&a[j], &a[j -1]);
        }
    }

其中N是宏定義的個數(shù)， exchange是定義的一個交換函數(shù)。j交換以后紅色箭頭元素會移動， 但是j--。移動一次j--一次， 所以箭頭的任然是a[j]初始那個元素。插入排序?qū)Σ糠钟行虻臄?shù)組十分高效，也很是很小規(guī)模的數(shù)組。所以可以讓數(shù)組先部分有序， 這就減少了比較次數(shù)， 提高了效率。所以這就很好理解希爾排序了。

希爾排序

思想:

1. 先部分有序化(任然是小范圍插入排序思想)
2. 增量為1時 為 插入排序

效率:希爾排序的時間復(fù)雜度會比o(n²)好一些。由于多次插入排序，我們知道一次插入排序是穩(wěn)定的，不會改變相同元素的相對順序，但在不同的插入排序過程中，相同的元素可能在各自的插入排序中移動，最后其穩(wěn)定性就會被打亂，所以shell排序是不穩(wěn)定的。

說明:
遞增序列給出一種:1 4 13 40 ...(3 * h + 1)

增量為4時對以下元素進(jìn)行部分有序化。

希爾排序增量為4的排序

code

    
     int a[10] = {4, 2, 5, 7, 8, 9, 10, 1, 6, 3};
    
    int h = 1;
    while (h < N/3) h = 3 * h + 1;
    
    while (h >= 1) {
        for (int i = h; i < N; i++) {
            for (int j = i; j >= h && a[j] < a[j - h]; j-=h) {
                exchange(&a[j], &a[j - h]);
            }
        }
        
        h = (h - 1)/3;
        
    }