选择排序

在选择排序中，在每次传递中选择数组的未排序元素中的最小值，并将其插入到数组中的适当位置。

首先，找到数组的最小元素并将其放在第一个位置。 然后，找到数组的第二个最小元素并将其放在第二个位置。 这个过程一直持续到得到排序的数组。

具有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