over 1 year ago
  • 選擇排序法的原理
  • 插入排序法的執行效能
  • javascript演算法實作

選擇排序法的原理

選擇排序法,它基本的觀念為將資料分成已排序與未排序,然後在未排序的資料中尋找最小(大)值,並將它移置已排序資料的右邊,我們以下圖來簡單的進行說明。

注意,下列的A[0]代表陣列的第一個位置。

  • 第一行 : 已排序資料為空,然後尋找未排序資料中最小值8,並將它移至已排序資料的右邊,也就是A[0],結果如第二行。
  • 第二行 : 已排序資料為8,尋找未排序資料中最小值23,並將它移至已排序資料的尾端A[1],結果如第三行。
  • 以此類推,最後可得到從小到大的排序資料。


圖片來源

插入排序法的執行效能

那這個排序演算法效能如何 ? 我們會分成最好與最壞與平均來看。

最好、最壞、平均狀況

O(n^2)

對都是一樣的,就算是排序好的,也是O(n^2)的時間複雜度,我們來看個例子。

[1,2,3,4,5]

我們有上面的陣列,它需要進行排序,我們知道它排序好了,但演算法不知,所以還是要跑。

  • 第一行 : 已排序資料為空,然後尋找未排序資料最小值,因為演算法不知道最小值是啥,所以還是要從頭找到尾,然後找出1,並將它放到A[0]位置。
  • 然後接下來,每一行還是要從未排序資料中,從頭掃到尾來尋找資料,不管你有沒有排序好。

建議使用情況

根據Wiki的說法,嗯……。

原地操作幾乎是選擇排序的唯一優點,當空間複雜度要求較高時,可以考慮選擇排序;實際適用的場合非常罕見。

javascript演算法實作

我們來看看它的演算法,我們採用javascript來進行撰寫。

/**
 * selectionSort
 * Selection Sort Algorithmic
 * @param arr
 * @returns {Array} , Thie return's array has been Sorted.   
 */
function selectionSort(arr){
    var len = arr.length,
            min = 0;
    for (var i=0;i<len;i++){
        min = i;    
        for (var j=i+1;j<len;j++){
            if(arr[min] >= arr[j] ){
                min = j;
            }
        }
        swap(arr,min,i);
        console.log(arr);
    }
    return arr;
}


/**
 * swap
 * Swap the min element and now element location.
 * @param arr , array
 * @param min , the min element's postion 
 * @param pos , now postion
 * @returns {undefined}
 */
function swap(arr,min,pos){
    var temp = arr[min];
    arr[min] = arr[pos];
    arr[pos] = temp;
}


簡單的測試一下。

selectionSort([3,54,24,33,22,58,95,1,2,31])

參考資料

← 排序之插入排序法(Insertion Sort) 排序之堆積排序法(Heap Sort) →
 
comments powered by Disqus