排序算法pascal代码集锦

排序算法pascal代码集锦 ; 排序排序就是将杂乱无章的数据元素，通过一定的办法按关键字顺序排列的过程。排序的办法很多，下面介绍一些常见的排序办法，要求了解其原理，会编写代码，并会分析不同算法的时间复杂度，了解各个算法的稳定性。稳定性指在原序列中相同元素的相对位置与排好序的新序列中相同元素的相对位置是否相同。假设相同，那么该算法是稳定的，否那么不稳定。简单排序1.选择排序选择排序的根本思想是：对待排序的记录序列进行n-1遍的处理，第1遍处理是将L1.n中最小者与L1交换位置，第2遍处理是将L2.n中最小者与L2交换位置第i遍处理是将Li.n中最小者与Li交换位置。这样，经过i遍处理之后，前i个记录的位置就已经按从小到大的顺序排列好了。时间复杂度:O(n2)。选择排序是稳定排序。 【例1】利用选择排序法对L1.n排序。 程序如下: program selectionSort; const n=7; var a:array1.n of integer; i,j,k,t:integer; beginassign(input,selectionSort.in);reset(input);assign(output,selectionSort.out);rewrite(output);for i:=1 to n do read(ai);for i:=1 to n-1 do begink:=i;for j:=i+1 to n do if aji thenbegin t:=ai;ai:=ak;ak:=t; end; end;write(output data:);for i:=1 to n do write(ai:6);writeln;close(input);close(output); end. 2.插入排序插入排序的根本思想:经过i-1遍处理后，L1.i-1已排好序。第i遍处理仅将Li插入L1. i-1的适当位置p，原来P后的元素一一向右移动一个位置，使得L1.i又是排好序的序列。时间复杂度为O(n2)，插入排序是稳定排序。 【例2】利用插入排序法对L1.n递减排序。 program insertionSort; const n=7; var a:array1.n of integer; i,j,k,t:integer; beginassign(input,insertionSort.in);reset(input);assign(output,insertionSort.out);rewrite(output);for i:=1 to n do read(ai);for i:=2 to n do begink:=ai;j:=i-1;while (j0) and (k冒泡排序又称交换排序，其根本思想是:对待排序的记录的关键字进行两两比拟，如发现两个记录是反序的，那么进行交换，直到无反序的记录为止。时间复杂度为O(n2)，冒泡排序是一个稳定的排序。【例3】利用冒泡排序法对L1.n递减排序。 程序如下:program bubbleSort; const n=7; var a:array1.n of integer; i,j,k,t:integer; beginassign(input,bubbleSort.in);reset(input);assign(output,bubbleSort.out);rewrite(output);for i:=1 to n do read(ai);for i:=1 to n-1 do for j:=n downto i+1 doif aj-1aj thenbegin t:=aj-1;aj-1:=aj;aj:=t; end;for i:=1 to n do write(ai:6);writeln;close(input);close(output); end. 快速排序快速排序的思想是：先从数据序列当选一个元素，并将序列中所有比该元素小的元素都放到它的右边或左边，再对左右两边分别用同样的办法处理直到每一个待处理的序列的长度为1，处理结束。时间复杂度下限O(nlog2n)，上限O(n2)。快速排序不稳定。 【例4】利用快速排序法对n个数字排序。 程序一 (先从数据序列当选取中间元素)： Program quickSort; var a:array0.1000 of longint; n,i:longint; procedure qsort(l,r:longint);var i,j,mid,temp:longint;begin if lr then exit; i:=l;j:=r; mid:=a(l+r) div 2; repeatwhile (aimid) do dec(j);if not (ij) then begin temp:=ai;ai:=aj;aj:=temp;inc(i);dec(j); end; until ij; if i程序二 (先从数据序列当选取首位元素)： program kspx; const n=7; type arr=array1.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:=bi; repeatwhile(bj=x) and (ji) do j:=j-1;if ji then begin bi:=bj;i:=i+1; end;while (bi希尔排序根本思想：将整个无序序列分割成假设干小的子序列分别进行插入排序或冒泡排序。序列分割办法：将相隔某个增量x的元素构成一个子序列。在排序过程中，逐次减小这个增量，最后当h减到1时，进行一次插入排序或冒泡排序，排序就完成。增量序列一般采用:d1=ndiv 2 ,di=di-1 div 2 ；i=2,3,4,其中n为待排序序列的长度。 【例5】利用希尔排序法对L1.n进行稳定排序。 程序1(子序列是插入排序): program shellSort_insert; const n=7; type arr=array1.n of integer; var a:arr; i,j,t,d:integer; bool:boolean; beginassign(input,shellSort_insert.in);reset(input);assign(output,shellSort_insert.out);rewrite(output);for i:=1 to n do read(ai);d:=n;while d1 do begind:=d div 2;for j:=d+1 to n do begint:=aj;i:=j-d;while (i0) and (ait) dobegin ai+d:=ai;i:=i-d; end;ai+d:=t; end; end;for i:=1 to n do write(ai:6);writeln;close(input);close(output); end. 程序2(子序列是冒泡排序): program shellSort_bubble; const n=7; type arr=array1.n of integer; var a:arr;i,temp,d:integer;bool:boolean; beginassign(input,shellSort_bubble.in);reset(input);assign(output,shellSort_bubble.out);rewrite(output);for i:=1 to n do read(ai);d:=n;