asked in 電腦與網際網路軟體 · 1 decade ago

何謂 選擇排序、泡沫排序、循序排序法、二分搜尋法??

因為看到這個單元都很霧煞煞,所以請各位懂VB的大大詳解一下,能越簡單的說就越簡單說。

快速排序法是循序排序法嗎?!?!

1 Answer

Rating
  • 小民
    Lv 6
    1 decade ago
    Favorite Answer

    Selection Sort 選擇排序

    最簡單的排序演算法之一: selection sort (選擇排序): 將 n 張考卷中最低分的那一個調到最前面, 再將剩下 (n-1) 張考卷中最低分的那一個調到第二個位置, 再將剩下 (n-2) 張考卷中最低分的那一個 ...

    Selection sort 外層迴圈的 loop invariant: 第 k 步做完時, 所有考卷當中最低分的 k 張已就定位。

    我們說 "selection sort 這個演算法的 worst case time complexity 屬於 O(n^2)", 意思是如果輸入 n 筆資料, 則最多 (最悲觀的情況下) 花 c n^2 的時間必能用 selection sort 演算法完成排序。 (那個 c 是什麼意思? 就是我們不在意的常數倍.)

    Bubble Sort

    讓大的數往下沉,小的數往上浮,每一次都會讓最大的數沉到最後面。所以排序的序列是從右到左排好的。而大部份的數則慢慢往上浮。

    氣泡排序法

    if (左邊的值 > 右邊的值) then

    此兩個值的位置互換

    else /* 左邊的值 ≦ 右邊的值 */

    此兩個值的位置不變

    右邊的值繼續和下一個值比較

    快速排序法

    假設有n個資料data[0] ~ data[n-1]

    設立指標l = data[0]= k ;指向第1個位置data[0],i = 0

    指標r = data[n-1] ;指向第n個位置data[n],j = n

    Step1:l往右找,直到找到比l值大時停止,假設停止於data[i]

    r往左找,直到找到比r值小時停止,假設停止於data[j]

    可能有兩種狀況:

    if ( i < j ) then

    data[i] 和data[j] 的內容值交換

    if ( i ≧ j ) then

    此陣列的第一個值和data[j]的內容值交換

    Step2:每次被分割的區塊,再分別設立l及r指標,

    l = 區塊第1個值,指向區塊第1個位置

    r = 區塊最後1個值,指向 (最後 + 1)的位置

    Step3:各個區塊再個別進行Step1,直到所有區塊均

    已排序完成。

    二元樹排序法

    1.將欲排序的元素一一以建立二元樹的方式插入,建

    立二元樹需滿足二個條件:

    (1)每一個節點最多只有兩個子節點 (左節點、右節點)

    (2)若一節點有子節點,則該節點的資料要比左節點

    的資料大,且比右節點的資料小 (左節點 < parent

    < 右節點)

    2.使用二元樹中序走訪的方式將二元樹的節點列印出 來,即可得到元素的排序結果。

    循序排序

    就是從第一個數往後比較,小的數就放前面,一直比到最後.

    舉例:

    7, 2, 3,9

    step 1 7 : 2 - 7 >2 so 2,7,3,9

    step 2 7:3 - 7 > 3 so 2,3,7,9

    step 3 7:9 - 9>7 so 2,3,7,9

    參考 網站

    http://www.shinjia.idv.tw/course/knu931/data_struc...

Still have questions? Get your answers by asking now.