排序算法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

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