排序算法pascal代码集锦(3)

begin k:=k+1; if r[i]

线性排序

上面我们所讨论的算法均是基于比较的排序算法，在排序算法中有基于数字本身的算法：计数、桶、基数排序。

1.计数排序

计数排序的基本思想是对于序列中的每一元素x，确定序列中小于x的元素的个数。 【例9】n个整数序列且每个值在[1,m]中，排序之。

程序如下：

program jspx; const m=6;n=8; var i,j:integer; a,b:array[1..n] of integer; c:array[1..m] of integer; begin assign(input,'jspx.in');reset(input); assign(output,'jspx.out');rewrite(output); for i:=1 to n do read(a[i]); for i:=1 to m do c[i]:=0; for i:=1 to n do c[a[i]]:=c[a[i]]+1; for i:=2 to m do c[i]:=c[i]+c[i-1]; for i:=1 to n do begin b[c[a[i]]]:=a[i]; c[a[i]]:=c[a[i]]-1; end; writeln('Sorted data:'); for i:=1 to n do write(b[i]:6); close(input);close(output); end.

2.桶排序

桶排序的思想是若待排序的记录的关键字在一个明显有限范围内(整型)时，可设计有限个有序桶，每个桶装入一个值，顺序输出各桶的值，将得到有序的序列。 【例10】输入n个0～100之间的整数，由小到大排序输出。 程序如下： program tpx; const n=7; var b:array[0..100] of integer; k:0..100; i:integer; begin assign(input,'tpx.in');reset(input); assign(output,'tpx.out');rewrite(output); for i:=0 to 100 do b[i]:=0; for i:=1 to n do begin read(k); b[k]:=b[k]+1; end; for i:=0 to 100 do while b[i]>0 do begin write(i:6);b[i]:=b[i]-1 end; writeln; close(input);close(output); end.

3.基数排序

基本思想是对n个元素依次按k，k-1，…，1位上的数字进行桶排序。 【例11】对n个位数不超过5的数字进行排序。 program basesort; const n=8; type link=^node; node=record data:integer; next:link; end; var i,j,l,m,k:integer; a:array[1..n] of integer; s:string; q,head:array[0..9] of link; p,p1:link; begin assign(input,'basesort.in');reset(input); assign(output,'basesort.out');rewrite(output); for i:=1 to n do read(a[i]); for i:=5 downto 1 do begin for j:=0 to 9 do begin new(head[j]); head[j]^.next:=nil; q[j]:=head[j]; end; for j:=1 to n do begin str(a[j],s); for k:=1 to 5-length(s) do s:='0'+s; m:=ord(s[i])-48; new(p); p^.data:=a[j]; p^.next:=nil; q[m]^.next:=p; q[m]:=p; end; l:=0; for j:=0 to 9 do begin p:=head[j]; while p^.next<>nil do begin l:=l+1;p1:=p;p:=p^.next; dispose(p1);a[l]:=p^.data; end; end; end; for i:=1 to n do write(a[i]:6); close(input);close(output); end. 各种排序算法的比较

1．稳定性比较

插入排序、冒泡排序、二叉树排序、归并排序及其他线形排序是稳定的。 选择排序、希尔排序、快速排序、堆排序是不稳定的。 2．时间复杂性比较

插入排序、冒泡排序、选择排序的时间复杂性为O(n2)。 其他非线形排序的时间复杂性为O(nlog2n)。 线形排序的时间复杂性为O(n)。 3．辅助空间的比较

线形排序、归并排序的辅助空间为O(n)，其他排序的辅助空间为O(1)。 4．其他比较

(1)插入、冒泡排序的速度较慢，但参加排序的序列局部或整体有序时，这种排序能达到较快的速度。在这种情况下，快速排序反而慢了，时间复杂度会达到其上限。当数据为随机数据时，快速排序远远快于插入、冒泡、选择排序，时间复杂度接近其下限。

(2)当n较小时，对稳定性不作要求时宜用选择排序，对稳定性有要求时宜用插入或冒泡排序。

(3)若待排序的记录的关键字在一个明显有限范围内且空间允许时，适用桶排序。 (4)当n较大时，关键字元素比较随机，对稳定性没要求宜用快速排序。

(5)当n较大时，关键字元素可能出现本身是有序的，对稳定性有要求、空间允许的情况下，

宜用归并排序。

(6)当n较大时，关键字元素可能出现本身是有序的，对稳定性没有要求时宜用堆排序。

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说教育文库排序算法pascal代码集锦(3)在线全文阅读。