排序算法篇（选择排序）

1.选择排序

选择排序的基本思想是遍历数组的过程中，以i代表当前需要排序的序号，则需要在剩余的[i…n-1]中找出其中的最小值，然后将找到的最小值与i指向的值进行交换。因为每一趟确定元素的过程中都会有一个选择最大值的子流程，所以人们形象地称之为选择排序。

举个实例来看看：

初始：[38,17,16,16,7,31,39,32,2,11]

i=0:[2,17,16,16,7,31,39,32,38,11](0th[38]<->8th[2])

i=1:[2,7,16,16,17,31,39,32,38,11](1st[38]<->4th[17])

i=2:[2,7,11,16,17,31,39,32,38,16](2nd[11]<->9th[16])

i=3:[2,7,11,16,17,31,39,32,38,16](无需交换)

i=4:[2,7,11,16,16,31,39,32,38,17](4th[17]<->9th[16])

i=5:[2,7,11,16,16,17,39,32,38,31](5th[31]<->9th[17])

i=6:[2,7,11,16,16,17,31,32,38,39](6th[39]<->9th[31])

i=7:[2,7,11,16,16,17,31,32,38,39](无需交换)

i=8:[2,7,11,16,16,17,31,32,38,39](无需交换)

i=9:[2,7,11,16,16,17,31,32,38,39](无需交换)

由例子可以看出，选择排序随着排序的进行（i逐渐增大），比较的次数会越来越少，但是不论数组初始是否有序，选择排序都会从i至数组末尾进行一次选择比较，所以给定长度的数组，选择排序的比较次数是固定的：1+2+3+….+n=n*(n+1)/2，而交换的次数则跟初始数组的顺序有关，如果初始数组顺序为随机，则在最坏情况下，数组元素将会交换n次，最好的情况下则可能0次（数组本身即为有序）。

由此可以推出，选择排序的时间复杂度和空间复杂度分别为O(n2)和O(1)（选择排序只需要一个额外空间用于数组元素交换）。

Java实现代码：

//交换data1和data2

publicvoidDataSwap(intdata1,intdata2)

{

inttemp=data1;

data1=data2;

data2=temp;

}

/********************************************************

*函数名称：SelectionSort

*参数说明：pDataArray无序数组；

*iDataNum为无序数据个数

*说明：选择排序

*********************************************************/

publicvoidSelectionSort(int[]pDataArray,intiDataNum)

{

for(inti=0;i<iDataNum-1;i++)//从第一个位置开始

{

intindex=i;

for(intj=i+1;j<iDataNum;j++)//寻找最小的数据索引

if(pDataArray[j]<pDataArray[index])

index=j;

if(index!=i)//如果最小数位置变化则交换

DataSwap(pDataArray[index],pDataArray[i]);

}

}