排序算法pascal代码集锦

排序

排序就是将杂乱无章的数据元素，通过一定的方法按关键字顺序排列的过程。

排序的方法很多，下面介绍一些常见的排序方法，要求了解其原理，会编写代码，并会分析不同算法的时间复杂度，了解各个算法的稳定性。

稳定性指在原序列中相同元素的相对位置与排好序的新序列中相同元素的相对位置是否相同。若相同，则该算法是稳定的，否则不稳定。

简单排序

1.选择排序

选择排序的基本思想是：对待排序的记录序列进行n-1遍的处理，第1遍处理是将L[1..n]中最小者与L[1]交换位置，第2遍处理是将L[2..n]中最小者与L[2]交换位置……第i遍处理是将L[i..n]中最小者与L[i]交换位置。这样，经过i遍处理之后，前i个记录的位置就已经按从小到大的顺序排列好了。时间复杂度:O(n2)。选择排序是稳定排序。 【例1】利用选择排序法对L[1..n]排序。 程序如下: program selectionSort; const n=7; var a:array[1..n] of integer; i,j,k,t:integer; begin assign(input,'selectionSort.in');reset(input); assign(output,'selectionSort.out');rewrite(output); for i:=1 to n do read(a[i]); for i:=1 to n-1 do begin k:=i; for j:=i+1 to n do if a[j]i then begin t:=a[i];a[i]:=a[k];a[k]:=t; end; end; write('output data:'); for i:=1 to n do write(a[i]:6); writeln; close(input);close(output); end. 2.插入排序

插入排序的基本思想:经过i-1遍处理后，L[1..i-1]已排好序。第i遍处理仅将L[i]插入L[1.. i-1]的适当位置p，原来P后的元素一一向右移动一个位置，使得L[1..i]又是排好序的序列。时间复杂度为O(n2)，插入排序是稳定排序。 【例2】利用插入排序法对L[1..n]递减排序。 program insertionSort; const n=7; var a:array[1..n] of integer; i,j,k,t:integer; begin assign(input,'insertionSort.in');reset(input); assign(output,'insertionSort.out');rewrite(output); for i:=1 to n do read(a[i]); for i:=2 to n do begin k:=a[i];j:=i-1; while (j>0) and (k

冒泡排序又称交换排序，其基本思想是:对待排序的记录的关键字进行两两比较，如发现两个记录是反序的，则进行交换，直到无反序的记录为止。时间复杂度为O(n2)，冒泡排序是一个稳定的排序。

【例3】利用冒泡排序法对L[1..n]递减排序。 程序如下:

program bubbleSort; const n=7; var a:array[1..n] of integer; i,j,k,t:integer; begin assign(input,'bubbleSort.in');reset(input); assign(output,'bubbleSort.out');rewrite(output); for i:=1 to n do read(a[i]); for i:=1 to n-1 do for j:=n downto i+1 do if a[j-1]>a[j] then begin t:=a[j-1];a[j-1]:=a[j];a[j]:=t; end; for i:=1 to n do write(a[i]:6); writeln; close(input);close(output); end. 快速排序

快速排序的思想是：先从数据序列中选一个元素，并将序列中所有比该元素小的元素都放到它的右边或左边，再对左右两边分别用同样的方法处理直到每一个待处理的序列的长度为1，处理结束。时间复杂度下限O(nlog2n)，上限O(n2)。快速排序不稳定。 【例4】利用快速排序法对n个数字排序。 程序一 (先从数据序列中选取中间元素)： Program quickSort; var a:array[0..1000] of longint; n,i:longint; procedure qsort(l,r:longint); var i,j,mid,temp:longint; begin if l>r then exit; i:=l;j:=r; mid:=a[(l+r) div 2]; repeat while (a[i]mid) do dec(j); if not (i>j) then begin temp:=a[i];a[i]:=a[j];a[j]:=temp; inc(i);dec(j); end; until i>j; if i

程序二 (先从数据序列中选取首位元素)： program kspx; const n=7; type arr=array[1..n] of integer; var a:arr; i:integer; procedure quicksort(var b:arr;s,t:integer); var i,j,x:integer; begin i:=s;j:=t;x:=b[i]; repeat while(b[j]>=x) and (j>i) do j:=j-1; if j>i then begin b[i]:=b[j];i:=i+1; end; while (b[i]<=x) and (i

希尔排序

基本思想：将整个无序序列分割成若干小的子序列分别进行插入排序或冒泡排序。

序列分割方法：将相隔某个增量x的元素构成一个子序列。在排序过程中，逐次减小这个增量，最后当h减到1时，进行一次插入排序或冒泡排序，排序就完成。增量序列一般采用:d1=n

div 2 ,di=di-1 div 2 ；i=2,3,4,…其中n为待排序序列的长度。 【例5】利用希尔排序法对L[1..n]进行稳定排序。 程序1(子序列是插入排序): program shellSort_insert; const n=7; type arr=array[1..n] of integer; var a:arr; i,j,t,d:integer; bool:boolean; begin assign(input,'shellSort_insert.in');reset(input); assign(output,'shellSort_insert.out');rewrite(output); for i:=1 to n do read(a[i]); d:=n; while d>1 do begin d:=d div 2; for j:=d+1 to n do begin t:=a[j];i:=j-d; while (i>0) and (a[i]>t) do begin a[i+d]:=a[i];i:=i-d; end; a[i+d]:=t; end; end; for i:=1 to n do write(a[i]:6); writeln; close(input);close(output); end. 程序2(子序列是冒泡排序): program shellSort_bubble; const n=7; type arr=array[1..n] of integer; var a:arr; i,temp,d:integer; bool:boolean; begin assign(input,'shellSort_bubble.in');reset(input); assign(output,'shellSort_bubble.out');rewrite(output); for i:=1 to n do read(a[i]); d:=n;

while d>1 do begin d:=d div 2; repeat bool:=true; for i:=1 to n-d do if a[i]>a[i+d] then begin temp:=a[i];a[i]:=a[i+d];a[i+d]:=temp; bool:=false end; until bool; end; for i:=1 to n do write(a[i]:6); writeln; close(input);close(output); end. 堆排序与二叉树排序

1.堆排序

堆结构一定是一颗完全二叉树，并且满足节点T的值大于(小于)它两个儿子的值。当堆顶(树根)的值是整个堆里面最小的数时，这个堆称为小根堆，如果是最大的树则称之为大根堆。

上图中（a），就是一个堆，它可以被视为一棵完全二叉树。每个堆对应于一个数组（b），假设一个堆的数组A，

我们用length[A]表述数组中的元素个数，树的根为A[1]，i表示某一结点的下标，其父结点为PARENT(i)，左儿子LEFT[i]，右儿子RIGHT[i]，它们之间的关系如下： PARENT(i)=i div 2 LEFT(i)=2*i RIGHT(i)=2i + 1

堆可以在log2n的时间内完成插入节点的功能，当然能维护好堆的性质。至于如何维护堆的

性质，只需要在取出堆顶和插入节点这两个时候进行维护。下面的讨论基于大根堆。 在取出堆顶的时候，只需要把堆最后的元素放到堆顶，然后把这个放到堆顶的元素向下移动。如果这个元素小于他两个儿子中小的那个，就与其交换，如果他小于他下面儿子中大的那个，也与其交换，否则就程序结束。在加入新节点的时候，只需要把元素放到堆尾，然后判断这个节点的值是不是大于他的父节点，如果大于就进行交换，直到这个条件不成立为止，程序结束。

堆排序的思想是:

(1)建初始堆(将节点[n/2],[n/2]-1,...,3,2,1 )分别调入堆)；

(2)当未排序完时输出堆顶元素，删除堆顶元素，将剩余的元素重新建堆。 堆排序的时间复杂度为:O(nlog2n)，是一种不稳定的排序。

堆排序算法步骤（1）

堆排序算法步骤（2）

【例6】利用堆排序方法对n个数字进行排序。 程序如下: program heapsort; var n,i,temp:longint; a:array[1..100000] of longint; procedure heap(sta,en:longint); var i,j,x:longint; begin x:=a[sta]; i:=sta; j:=i*2; while (j<=en) do begin if (j二叉树排序：每一个参加排列的数据对应二叉树的一个节点，且任一节点如果有左(右)子树，则左(右)子树各节点的数据必须小(大)于该节点的数据。中序遍历排序二叉树即得排序结果。二叉树排序时间复杂度最坏情况下为O(n2)，是稳定排序。 【例7】利用二叉树排序法对n个互不相同的数字进行排序。 程序如下: program pxtree; const a:array[1..8] of integer=(10,18,3,8,12,2,7,3); type pointer=^node; node=record w:integer; right,left:pointer; end; var root,first:pointer; k:boolean; i:integer; procedure addnode(d:integer;var p:pointer); begin if p=nil then begin new(p); with p^ do begin w:=d;right:=nil;left:=nil end; if k then begin root:=p;k:=false end; end else with p^ do if d>=w then addnode(d,right) else addnode(d,left); end; procedure traveltree(p:pointer); begin with p^ do begin if left<>nil then traveltree(left); write(w:4); if right<>nil then traveltree(right); end; end; begin first:=nil;k:=true; for i:=1 to 8 do addnode(a[i],first); traveltree(root);writeln; end. 归并排序

归并就是将多个有序的数列合成一个有序的数列。将两个有序序列合并为一个有序序列叫二路归并。归并排序就是n个长度为1的子序列，两两归并最后变为有序的序列。 【例8】利用归并排序将n个有序数列合并成一个有序数列。 程序代码如下： program gbpx; const maxn=7; type arr=array[1..maxn] of integer; var a,b,c:arr; i:integer; procedure merge(r:arr;l,m,n:integer;var r2:arr); //合并r[l..m]、r[m+1..n] var i,j,k,p:integer; begin i:=l;j:=m+1;k:=l-1; while(i<=m) and (j<=n) do

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较大时，关键字元素可能出现本身是有序的，对稳定性没有要求时宜用堆排序。

本文来源：https://www.bwwdw.com/article/ndh.html