選擇排序

在選擇排序中，在每次傳遞中選擇陣列的未排序元素中的最小值，並將其插入到陣列中的適當位置。

首先，找到陣列的最小元素並將其放在第一個位置。 然後，找到陣列的第二個最小元素並將其放在第二個位置。 這個過程一直持續到得到排序的陣列。

具有n個元素的陣列通過使用n-1遍選擇排序演算法進行排序。

• 在第1遍中，將找到陣列的最小元素及其索引pos。 然後，交換A[0]和A[pos]。 因此A [0]被排序，現在還有n -1個要排序的元素。

• 在第2遍中，找到子陣列A[n-1]中存在的最小元素的位置pos。 然後，交換，A[1]和A[pos]。 因此A[0]和A[1]被排序，現在留下n-2個未排序的元素。

• 在第n-1遍中，找到A[n-1]和A[n-2]之間的較小元素的位置pos。 然後，交換A[pos]和A[n-1]。

因此，通過遵循上述過程，對元素A[0]，A[1]，A[2]，...，A[n-1]進行排序。
執行過程可參考下圖 -

範例
考慮以下具有6個元素的陣列，使用選擇排序對陣列的元素進行排序。

A = {10, 2, 3, 90, 43, 56};

執行排序和交換位置過程如下所示 -

執行上面排序後，陣列中的資料值如下 -

A = {2, 3, 10, 43, 56, 90}

複雜性

演算法

SELECTION SORT(ARR, N)

第1步 : 迴圈第2步和第3步，從 K = 1 到 N-1
第2步 : CALL SMALLEST(ARR, K, N, POS)
第3步 : 將 A[K] 與 ARR[POS] 交換
        [結束回圈]
第4步 : 退出

SMALLEST (ARR, K, N, POS)

第1步 : [INITIALIZE] SET SMALL = ARR[K]
第2步 : [INITIALIZE] SET POS = K
第3步 : 迴圈 J = K+1 至 N -1
            IF SMALL > ARR[J]
                SET SMALL = ARR[J]
                SET POS = J
            [結束IF]
        [結束回圈]
第4步 : 返回POS

使用C語言實現選擇排序演算法，程式碼如下所示 -

#include<stdio.h>  
int smallest(int[],int,int);  
void main ()  
{  
    int a[10] = {10, 9, 7, 101, 23, 44, 12, 78, 34, 23};  
    int i,j,k,pos,temp;  
    for(i=0;i<10;i++)  
    {  
        pos = smallest(a,10,i);  
        temp = a[i];  
        a[i]=a[pos];  
        a[pos] = temp;  
    }  
    printf("printing sorted elements...\n");  
    for(i=0;i<10;i++)  
    {  
        printf("%d\n",a[i]);  
    }  
}  
int smallest(int a[], int n, int i)  
{  
    int small,pos,j;  
    small = a[i];  
    pos = i;  
    for(j=i+1;j<10;j++)  
    {  
        if(a[j]<small)  
        {  
            small = a[j];  
            pos=j;  
        }  
    }  
    return pos;  
}

執行上面範例程式碼，得到以下結果：

printing sorted elements...
7
9
10
12
23
23
34
44
78
101

使用C++語言實現選擇排序演算法，程式碼如下所示 -

#include<iostream>  
using namespace std;  
int smallest(int[],int,int);  
int main ()  
{  
    int a[10] = {10, 9, 7, 101, 23, 44, 12, 78, 34, 23};  
    int i,j,k,pos,temp;  
    for(i=0;i<10;i++)  
    {  
        pos = smallest(a,10,i);  
        temp = a[i];  
        a[i]=a[pos];  
        a[pos] = temp;  
    }  
    cout<<"printing sorted elements...\n";  
    for(i=0;i<10;i++)  
    {  
        cout<<a[i]<<"\n";  
    }  
    return 0;  
}  
int smallest(int a[], int n, int i)  
{  
    int small,pos,j;  
    small = a[i];  
    pos = i;  
    for(j=i+1;j<10;j++)  
    {  
        if(a[j]<small)  
        {  
            small = a[j];  
            pos=j;  
        }  
    }  
    return pos;  
}

執行上面範例程式碼，得到以下結果：

printing sorted elements...
7
9
10
12
23
23
34
44
78
101

使用Java語言實現選擇排序演算法，程式碼如下所示 -

public class SelectionSort {  
    public static void main(String[] args) {  
        int[] a = {10, 9, 7, 101, 23, 44, 12, 78, 34, 23};  
        int i,j,k,pos,temp;  
        for(i=0;i<10;i++)  
        {  
            pos = smallest(a,10,i);  
            temp = a[i];  
            a[i]=a[pos];  
            a[pos] = temp;  
        }  
        System.out.println("printing sorted elements...\n");  
        for(i=0;i<10;i++)  
        {  
            System.out.println(a[i]);  
        }  
    }  
    public static int smallest(int a[], int n, int i)  
    {  
        int small,pos,j;  
        small = a[i];  
        pos = i;  
        for(j=i+1;j<10;j++)  
        {  
            if(a[j]<small)  
            {  
                small = a[j];  
                pos=j;  
            }  
        }  
        return pos;  
    }  
}

執行上面範例程式碼，得到以下結果：

printing sorted elements...
7
9
10
12
23
23
34
44
78
101

使用C#語言實現選擇排序演算法，程式碼如下所示 -

using System;                 
public class Program  
{  


public void Main() {  
    int[] a = {10, 9, 7, 101, 23, 44, 12, 78, 34, 23};  
    int i,pos,temp;  
    for(i=0;i<10;i++)  
    {  
        pos = smallest(a,10,i);  
        temp = a[i];  
        a[i]=a[pos];  
        a[pos] = temp;  
    }  
    Console.WriteLine("\nprinting sorted elements...\n");  
    for(i=0;i<10;i++)  
    {  
        Console.WriteLine(a[i]);  
    }  
}  
public static int smallest(int[] a, int n, int i)  
{  
    int small,pos,j;  
    small = a[i];  
    pos = i;  
    for(j=i+1;j<10;j++)  
    {  
        if(a[j]<small)  
        {  
            small = a[j];  
            pos=j;  
        }  
    }  
    return pos;  
}  
}

執行上面範例程式碼，得到以下結果：

printing sorted elements...
7
9
10
12
23
23
34
44
78
101