实作范例

C语言

voidselection_sort(intarr[],intlen){inti,j,min,temp;for(i=0;i<len-1;i++){min=i;for(j=i+1;jarr[j])min=j;temp=arr[min];arr[min]=arr[i];arr[i]=temp;}}

C++

template//整數或浮點數皆可使用，若要使用物件（class）時必須設定大於（>）的運算子功能voidselection_sort(std::vector&arr){for(inti=0;i<arr.size()-1;i++){intmin=i;for(intj=i+1;j<arr.size();j++)if(arr[j]<arr[min])min=j;std::swap(arr[i],arr[min]);}}

C#

staticvoidselection_sort(T[]arr)whereT:System.IComparable{//整數或浮點數皆可使用inti,j,min,len=arr.Length;Ttemp;for(i=0;i<len-1;i++){min=i;for(j=i+1;j0)min=j;temp=arr[min];arr[min]=arr[i];arr[i]=temp;}}

VB.net

Python

defselection_sort(L):N=len(L)exchanges_count=0foriinrange(N-1):min_index=iforjinrange(i+1,N):ifL[min_index]>L[j]:min_index=jifmin_index!=i:L[min_index],L[i]=L[i],L[min_index]exchanges_count+=1print("iteration #{}: {}".format(i,L))print("Total {} swappings".format(exchanges_count))returnLtestlist=[17,23,20,14,12,25,1,20,81,14,11,12]print("Before selection sort: {}".format(testlist))print("After selection sort: {}".format(selection_sort(testlist)))

Java

publicstaticvoidselection_sort(int[]arr){inti,j,min,temp,len=arr.length;for(i=0;i<len-1;i++){min=i;//未排序序列中最小数据数组下标for(j=i+1;jarr[j]){min=j;}temp=arr[min];//将最小元素放到已排序序列的末尾arr[min]=arr[i];arr[i]=temp;}}

JavaScript

Array.prototype.selection_sort=function(){vari,j,min;vartemp;for(i=0;i<this.length-1;i++){min=i;for(j=i+1;jthis[j])min=j;temp=this[min];this[min]=this[i];this[i]=temp;}};

PHP

functionswap(&$x,&$y){$t=$x;$x=$y;$y=$t;}functionselection_sort(&$arr){//php的陣列視為基本型別，所以必須用傳參考才能修改原陣列for($i=0;$i<count($arr)-1;$i++){$min=$i;for($j=$i+1;$j$arr[$j])$min=$j;swap($arr[$min],$arr[$i]);}}

GO

// SelectSort 选择排序, data必须实现sort包中的Interface接口funcSelectSort(datasort.Interface){fori:=0;i<data.Len()-1;i++{// 假定首元素为最小元素min:=iforj:=min+1;j<data.Len();j++{ifdata.Less(j,min){min=j}}// 将此次筛选出的最小元素放入最左边data.Swap(min,i)}}

复杂度分析

选择排序的 交换操作 介于 0 {\displaystyle 0} 和 ( n − − --> 1 ) {\displaystyle (n-1)} 次之间。选择排序的 比较操作 为 n ( n − − --> 1 ) / 2 {\displaystyle n(n-1)/2} 次之间。选择排序的 赋值操作 介于 0 {\displaystyle 0} 和 3 ( n − − --> 1 ) {\displaystyle 3(n-1)} 次之间。

比较次数 O ( n 2 ) {\displaystyle O(n^{2})} ，比较次数与关键字的初始状态无关，总的比较次数 N = ( n − − --> 1 ) + ( n − − --> 2 ) + . . . + 1 = n × × --> ( n − − --> 1 ) / 2 {\displaystyle N=(n-1)+(n-2)+...+1=n\times (n-1)/2} 。交换次数 O ( n ) {\displaystyle O(n)} ，最好情况是，已经有序，交换0次；最坏情况是，逆序，交换 n − − --> 1 {\displaystyle n-1} 次。交换次数比冒泡排序较少，由于交换所需CPU时间比比较所需的CPU时间多， n {\displaystyle n} 值较小时，选择排序比冒泡排序快。

原地操作几乎是选择排序的唯一优点，当空间复杂度要求较高时，可以考虑选择排序；实际适用的场合非常罕见。

免责声明：以上内容版权归原作者所有，如有侵犯您的原创版权请告知，我们将尽快删除相关内容。感谢每一位辛勤著写的作者，感谢每一位的分享。