C# · 12月 20, 2021

数据结构与算法——排序算法之选择排序

一:选择排序原理:

将要排序的数据元素选出最小(大),将他和数据元素的首位交换位置。再次从剩下的数据元素中 找到最小(大)的元素,然后与数据元素的第二位子交换。。。直到将整个数据元素排序。

总之他在不断选择剩余元素的最小值,然后放在恰当的位置。

二:选择排序的特点:

1.运行时间和输入无关。

为了找出最小的元素,遍历整个数组并不能为下一次遍历提供信息。这样的缺点是:一个有序的数组与一个随机数组所用的排序时间相同。

2.数据移动最少。

每次交换都会改变两个元素的值,因此数组多大,就几次数据移动。

三:代码描述(java实现):

public static void sort(int[] a){

int N=a.length;

for(int i=0;i<N;i++){

int min=i;

for(int j=i+1;j<N;j++){

if(a[j]

min=j;

}

}

int temp=a[i];

a[i]=a[min];

a[min]=temp;

}

}

内循环为找到当前序列的最小元素。然后最小元素与相应的位置的元素交换位置。每次交换能确定一个元素的位置,所以总交换次数为N.所以算法的时间效率取决于比较次数N*(N-1)/2