在选择排序中，在每次传递中选择数组的未排序元素中的最小值，并将其插入到数组中的适当位置。
首先，找到数组的最小元素并将其放在第一个位置。 然后，找到数组的第二个最小元素并将其放在第二个位置。 这个过程一直持续到得到排序的数组。
具有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};
执行排序和交换位置过程如下所示 -
| 遍次 | pos | A[0] | A[1] | A[2] | A[3] | A[4] | A[5] |
|---|---|---|---|---|---|---|---|
| 1 | 1 | 2 | 10 | 3 | 90 | 43 | 56 |
| 2 | 2 | 2 | 3 | 10 | 90 | 43 | 56 |
| 3 | 2 | 2 | 3 | 10 | 90 | 43 | 56 |
| 4 | 4 | 2 | 3 | 10 | 43 | 90 | 56 |
| 5 | 5 | 2 | 3 | 10 | 43 | 56 | 90 |
执行上面排序后，数组中的数据值如下 -
A = {2, 3, 10, 43, 56, 90}
复杂性
| 复杂性 | 最好情况 | 平均情况 | 最坏情况 |
|---|---|---|---|
| 时间复杂性 | Ω(n) | θ(n^2) | o(n^2) |
| 空间复杂性 | - | - | o(1) |
算法
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
