筆記國度

在這裡放著一些我自己的筆記

排序法(未完,待續)

| Comments

資料來源:http://spaces.isu.edu.tw/upload/18833/3/web/sorting.htm

排序(sorting),將一組資料一使用者需求,予以重新排列其順序。一般會依資料之大小順序排序(由大至小、或由小至大)。排序後之資料,優點為容易閱讀、統計分析、與快速搜尋所要之資料。


排序法的分類

  1. 內部與外部排序
    • 內部排序(Internal sort):又稱「陣列排序」
      • 排序之工作,主要在主記憶體(RAM)完成。適用於資料量較少時。
    • 外部排序(External sort):又稱「檔案排序」
      • 排序之工作,主要是在輔助記憶體(Disk, File)完成。適用於資料量較大時。
  2. 穩定與不穩定排序法
    • 穩定排序法(stable sorting)
      • 如果鍵值相同之資料,在排序後相對位置與排序前相同時,稱穩定排序。
        排序前:3,5,19,1,3',10
        排序後:1,3,3',5,10,19  (因為兩個 3, 3' 的相對位置在排序前與後皆相同。)
        
    • 不穩定排序法(unstable sorting)
      • 如果鍵值相同之資料,在排序後相對位置與排序前不相同時,稱不穩定排序。
        排序前:3,5,19,1,3',10
        排序後:1,3',3,5,10,19  (因為兩個3, 3'的相對位置在排序前與後不相同。)
        
  3. 簡單與高等排序法
    • 簡單排序法
      • 排序演算法簡單,但執行時間較長。
    • 高等排序法
      • 排序演算法複雜,執行時間較短。

常見之排序演算法

排序方法 最壞時間 平均時間 穩定 額外空間 備註說明
氣泡排序 (Bubble) 穩定 小比較好。
選擇排序 (Selection) 不穩定 小比較好,部份排序好更好。
插入排序 (Insertion) 穩定 大部份排序好比較好。
快速排序 (Quick) 不穩定 ~ 在資料已排序好時會產生最差狀況。
堆積排序 (Heap) 不穩定
薛爾排序 (shell) 穩定 小比較好。
合併排序 (Merge) 穩定 常用於外部排序。

氣泡排序 (Bubble)

template<typename T> void swap(T *a,T *b)
{
    T tmp = *a;
    *a = *b;
    *b = tmp;
}

template<typename T> void bubble_sort(T *arr,int n)
{
    for(int i=0;i<n;i++)
        for(int j=0;j<n-i-1;j++)
            if(arr[j]>arr[j+1])
                swap(arr[j],arr[j+1]);
}

選擇排序

template<typename T> void swap(T *a,T *b)
{
    T tmp = *a;
    *a = *b;
    *b = tmp;
}

template<typename T> void select_sort(T *arr,int n)
{
    for(int i=0;i<n;i++)
        for(int j=i+1;j<n;j++)
            if(arr[i]>arr[j])
                swap(arr[i],arr[j]);
}

插入排序

template<typename T> void insert_sort(T *arr,int n)
{
    T tmp;
    int j;
    for(int i=1;i<n;i++)
    {
        tmp = arr[i];
        for(j=i-1; j>-1 && arr[j]>tmp ;j--)
            arr[j+1] = arr[j];
        arr[j+1] = tmp;
    }
}

Comments

comments powered by Disqus