C++與演算法

選擇排序法 (Selection Sort)

生活中經常要用到排序、分類，例如：

  • 將成績由高到低排序
  • 將喜好程度由高到低排序
  • 將可回收的垃圾分類
  • 將筆電的價錢排序
  • ...

對電腦來說，我們可以將排序問題轉化成以下形式


題目 - 排序

輸入說明

第1列: 1個整數N，代表接下來有幾個數字。 ( 1 <= N <= 100 )

第2列: N個待排序的整數

輸出說明

將輸出由小到大排序

input

12
50 25 76 38 19 58 29 88 44 22 11 34

output

11 19 22 25 29 34 38 44 50 58 76 88





處理排序問題有很多方法，以下介紹其中一種適合入門的選擇排序法

概念

將數字們分成2類，未排序 和 已排序

一開始所有數字都是未排序

重複 N 次：

  • 從未排序的數字中挑出最小的數字，放入已排序的最尾端。


依照上述

第1次可以挑到所有數字中第1小的數字 (最小的數字)

第2次可以挑到所有數字中第2小的數字

...

第N次可以挑到所有數字中第N小的數字 (最大的數字)

最後就由小到大排完了


實際操作

已排序 未排序
空 50 25 76 38 19 58 29 88 44 22 11 34
11 50 25 76 38 19 58 29 88 44 22 34
11 19 50 25 76 38 58 29 88 44 22 34
11 19 22 50 25 76 38 58 29 88 44 34
11 19 22 25 50 76 38 58 29 88 44 34
11 19 22 25 29 50 76 38 58 88 44 34
11 19 22 25 29 34 50 76 38 58 88 44
11 19 22 25 29 34 38 50 76 58 88 44
11 19 22 25 29 34 38 44 50 76 58 88
11 19 22 25 29 34 38 44 50 76 58 88
11 19 22 25 29 34 38 44 50 58 76 88
11 19 22 25 29 34 38 44 50 58 76 88
11 19 22 25 29 34 38 44 50 58 76 88 空



code

  • 想像在sort裡的 for( i=0 ; i<N ; i++ )中

    • num[0] ~ num[i-1] 是已排序

    • num[i+1] ~ num[N-1] 是未排序

    • num[i]是現在正要增加的 已排序的最尾端

    • 用變數交換，把num[i]換成未排序裡最小的數字

#include<iostream>
using namespace std;

int main()
{
    int num[100];
    int N;
    int i, j, tmp;

    //[input]
    cin >> N;
    for( i=0 ; i<N ; i=i+1 )
    {
        cin >> num[i];
    }

    //[sort]
    for( i=0 ; i<N ; i=i+1 )
    {
        for( j=i+1 ; j<N ; j=j+1 )
        {
            if( num[i] > num[j] )
            {
                //變數交換
                tmp = num[i];
                num[i] = num[j];
                num[j] = tmp;
            }
        }
    }

    //[output]
    for( i=0 ; i<N ; i=i+1 )
    {
        cout << num[i] << " ";
    }
    cout << endl;

    return 0;
}



題目練習



延伸閱讀