C語言中文網 目錄

選擇排序算法,C語言選擇排序算法詳解

選擇排序是一種簡單直觀的排序算法。它與冒泡排序很相似,都是比較 n-1 輪,每輪都是比較 n–1–i 次,每輪找出一個最大值或最小值。

只不過,冒泡排序是將每輪找出的最值放到最右邊,而選擇排序是將每輪找出的最值放到最左邊。并且在算法上,冒泡排序是將相鄰的數進行逐個比較,以從小到大排序為例,只要前面的比后面的大,就互換這兩個數,直到最后將最大的數“浮”到最右邊,如此依次循環。而選擇排序是先保存第一個元素的下標,然后后面所有的數依次與第一個元素相比,如果遇到更小的,則記錄更小的那個數的下標,然后后面所有的數都依次與那個更小的數比較,直到最后將最小的數的下標找出來,然后再將這個數放到最左邊,即與下標為 0 的數互換。如果最小的數的下標就是 0 那么就不用互換。

所以,選擇排序算法是先判斷最小的數的下標是不是 0,如果不是則說明最小的數不是第一個元素,則將這個數與第一個元素互換位置,這樣一輪下來最小的那個數就被找到并放到了最左邊。

在第二輪同樣先保存新序列第二個元素的下標,后面所有的數依次與第二個元素相比較,如果遇到更小的則記錄更小的那個數的下標,然后后面所有的數都依次與那個更小的數比較,直到最后又找到一個最小的,此時這個最小的在整個序列中是“第二小”。然后再判斷這個數的下標是否等于 1,如果不等于 1 說明“第二小”的那個數不是第二個元素,則將這個數與第二個元素互換位置,這樣第二輪下來就找到了“第二小”的那個數,并將它放到了第二個位置。如此循環,直到整個序列實現從小到大排序。

如果是從大到小排序,那么就記錄大的那個數的下標,每一輪找出一個最大的數放到左邊。

從上面的分析可以看出,選擇排序和冒泡排序的另一個不同點是,冒泡排序只要遇到前面比后面大的就互換,而選擇排序是比較一輪才互換一次,而且如果本輪中最小的就是最左邊那個數則不用互換。所以從這個角度看,選擇排序比冒泡排序的效率要高。而且通過上面對選擇排序的分析發現,從邏輯上講,與冒泡排序相比,選擇排序更符合人的思維。

下面來寫一個程序,用選擇排序實現一個序列的從小到大排序:
# include <stdio.h>
int main(void)
{
    int i, j;  //循環變量
    int MinIndex;  //保存最小的值的下標
    int buf;  //互換數據時的臨時變量
    int a[] = {5, 5, 3, 7, 4, 2, 5, 4, 9, 1, 8, 6};
    int n = sizeof(a) / sizeof(a[0]);  //存放數組a中元素的個數
    for (i=0; i<n-1; ++i)  //n個數比較n-1輪
    {
        MinIndex = i;
        for (j=i+1; j<n; ++j)  //每輪比較n-1-i次, 找本輪最小數的下標
        {
            if (a[MinIndex] > a[j])
            {
                MinIndex = j;  //保存小的數的下標
            }
        }
        if (MinIndex != i)  /*找到最小數之后如果它的下標不是i則說明它不在最左邊, 則互換位置*/
        {
            buf = a[MinIndex];
            a[MinIndex] = a[i];
            a[i] = buf;
        }
    }
    printf("最終排序結果為:\n");
    for (i=0; i<12; ++i)
    {
        printf("%d ", a[i]);
    }
    printf("\n");
    return 0;
}
輸出結果是:
最終排序結果為:
1 2 3 4 4 5 5 5 6 7 8 9

通過程序可以看出,雖然選擇排序比冒泡排序的效率高,邏輯上也更符合人的思維,但是程序相對更復雜,冒泡排序比選擇排序在邏輯上要清晰一點,也稍微簡單一點。

精美而實用的網站,提供C語言、C++、STL、Linux、Shell、Java、Go語言等教程,以及socket、GCC、vi、Swing、設計模式、JSP等專題。

Copyright ?2011-2018 biancheng.net, 陜ICP備15000209號

底部Logo
极速pk10开户