直接选择排序.doc

《直接选择排序.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、直接选择排序算法1．输入n个元素2．从第2个元素开始，依次与第一个元素作比较，如果比第一个元素小，则交换，否则找下一个元素与第一个元素比较；3．从第3个元素开始，重复第2步，直到比较完4．输出n个元素对一组数：46    58    15    45    90    18    10    62排序过程如下：第一遍：46    58    15    45    90    18    10    6215    58    46    45    90    18    10    6210    [58    46    45    90    18    15    62]

2、第二遍：10    46    58    45    90    18    15    6210    45    58    46    90    18    15    6210    18    58    46    90    45    15    6210    15    [58    46    90    45    18    62]第三遍：10    15    46    58    90    45    18    6210    15    45    58    90    46    18    6210    15    18    [5

3、8    90    46    45    62]Program ex;typearr=array [1..100] of integer;vara:arr;i,n:integer;Procedure  select(var  a1:arr;k:integer);varI,j,t:integer;BeginFor i:=1 to k-1 doFor j:=i+1 to k doIf a1[i]>a1[j] thenbegint:=a1[i];a1[i]:=a1[j];a1[j]:=t;end;end;beginreadln(n);for i:=1 to n doread(a[i]

4、);select(a,n);for i:=1 to n dowrite(a[i],’ ’);end.改进算法：第k遍，不需要后面比前面小就交换，只要找最小的，最后再与a[k]交换就可以了。排序过程如下：[46    58    15    45    90    18    10    62]10    [58    15    45    90    18    46    62]10    15    [58    45    90    18    46    62]10    15    18    [45    90    58    46    62]10    15 

5、   18    45    [90    58    46    62]10    15    18    45    46    [58    90    62]10    15    18    45    46    58    [90    62]10    15    18    45    46    58    62    90Procedure  select(var  a1:arr;k:integer);varI,j,s,t:integer;BeginFor i:=1 to k-1 doBegins:=I;For j:=i+1 to k doIf a[s]>a[

6、j] then s:=j;If s<>I thenBeginT:=a[i];a[i]:=a[s];a[s]:=t;End;end;end;该算法不适宜于n较大的情况。直接选择排序是不稳定的。时间复杂度为O（n2）