浅谈自由帕斯卡的排序方法
(1)直接插入-稳定排序
(2)拆卸和半插入稳定排序
(3)双向插入排序-稳定排序
(4)表格插入排序-稳定排序
(5)希尔排序——不稳定排序。
二、快速(交换)排序:(平均时间复杂度:O(nlogn)，最坏情况:O(N2))-不稳定排序。
(1)冒泡排序-稳定排序
(2)快速排序
三、选择排序:(平均时间复杂度:O(nlogn)，最坏情况:O(NLOGN))-不稳定排序。
(1)简单选择排序
(2)树选择排序
(3)堆排序((2)排序的改进)
四、归并排序:(平均时间复杂度:O(nlogn)，最坏情况:O(nlogn))
(1)双向合并排序
5.基数排序:(平均时间复杂度:O(d(n+rd))、最坏情况:O(d(n+rd))-稳定排序。
稳定排序:排序过程中元素的相对位置没有发生变化的排序称为稳定排序。
不稳定排序:排序过程中元素相对位置发生变化的排序称为不稳定排序。
首先，插入排序:
(1)直接插入:
示例:初始状态:(49) 38 65 97 76 13 27 *49
i=2 (38) (38 49)
i=3 (65) (38 49 65)
i=4 (97) (38 49 65 97)
i=5 (76) (38 49 65 76 97)
I = 6(13)(13 38 49 65 76 97)
i=7 (27) (13 27 38 49 65 76 97)
I = 8(49)(13 27 38 49 * 49 65 76 97)
(2)拆除和插入:
示例:初始状态:49 38 65 97 76 13 27 *49
proc bin pass(var r:listtype；)
(3) 2路插入排序:设置两个指针:first——头总是指向最小的元素，final——尾总是指向最大的元素。
示例:初始状态:49 38 65 97 76 13 27 *49
i=1 (49)
i=2 (49) (38)
i=3 (49 65) (38)
i=4 (49 65 97) (38)
i=5 (49 65 76 97) (38)
i=6 (49 65 76 97) (13 38)
i=7 (49 65 76 97) (13 27 38)
i=8 (49 *49 65 76 97) (13 27 38)
(4)希尔排名:(O(logn)最好，O (n 2)最差)
示例:初始状态:49 38 65 97 76 13 27 *49 55 04
| |
| |
| |
| |
| |
一次性排序结果:13 27 *49 55 04 49 38 65 97 76
| | | |
| | |
| | |
两遍排序的结果:13 04 *49 38 27 49 55 65 97 76
三遍排序的结果:04 13 27 38 *49 49 55 65 76 97
增量公式:...9,5,3,2,1
...40,13,4,1
(5)简单排序:49 38 65 97 76 13 27 *49
38 65 13 27
38 13
排序一次的结果是13。
(6)堆排序:
堆的定义:n个元素的序列{K1，K2，...，KN}称为堆当且仅当满足以下关系时:
k(I)& lt；=k(2i)或k(i)>=k(2i)
k(I)& lt；=k(2i+1) k(i)>=k(2i+1)
(7)合并排序:
示例:初始状态:49 38 65 97 76 13 27 *49 50
一次行程排序:(38 49)(65 97)(65 438+03 76)(27 * 49)(50)
两遍排序:(38 49 65 97) (13 27 *49 76) (50)
三遍排序:(13 27 38 49 *49 50 65 76 97)
Pascal实现排序方法
过程交换(var x，y:integer)；
定义变量
temp:整数；
开始
temp:= x；
x:= y；
y:= temp；
结束；
//冒泡排序
过程BubbleSort(变量A:整数数组)；
定义变量
I，J，T:整数；
开始
从高到低做
对于J :=低(A)到高(A) - 1 do
如果A[J]& gt；A[J + 1]然后
开始
swap(A[J]，A[J+1])；
t:= A[J]；
A[J]:= A[J+1]；
a[J+1]:= T；
结束；
结束；
//选择排序
procedure SelectionSort(var A:整数数组)；
定义变量
I，J，T:整数；
开始
对于I :=低(A)到高(A) - 1 do
对于J := High(A) downto I + 1 do
如果A[I]& gt；那么
开始
Swap(A[I]，A[J])；
t:= A[I]；
A[I]:= A[J]；
a[J]:= T；
如果终止，则退出；
结束；
结束；
//快速排序
过程快速排序(变量A:整数数组)；
过程QuickSortSub(var A:整数数组；iLo、iHi:整数)；
定义变量
Lo，Hi，Mid，T:整数；
开始
lo:= iLo；
hi:= iHi；
mid:= A[(Lo+Hi)div 2]；
重复
而A[Lo]& lt；Mid do公司(Lo)；
而A[Hi]>十二月中旬(喜)；
如果Lo & lt你好
开始
Swap(A[Lo]，A[Hi])；
t:= A[Lo]；
A[Lo]:= A[Hi]；
a[Hi]:= T；
Inc(Lo)；
Dec(喜)；
结束；
直到Lo & gt嗨；
如果嗨& gtiLo then QuickSortSub(A，iLo，Hi)；
如果Lo & ltiHi then QuickSortSub(A，Lo，iHi)；
结束；
开始
QuickSortSub(A，低(A)，高(A))；
结束；
Pascal 2007-04-18 16:16程序Inssort
const max = 100；
类型arr=array[0..max]的整数；
var a:arr；
I，n:整数；
fin:文本；
过程in sort(var r:arr；rn:整数)；{直接插入排序算法}
var i，j:整数；
开始
对于i:=2到rn do
开始
r[0]:= r[I]；{存储要插入到监视栏r[0]中的记录}
j:= I-1；
while(r[0]& lt；r[j])do {找到插入位置}
开始
r[j+1]:= r[j]；{记录向后移动}
第十届会议；
结束；
r[j+1]:= r[0]；{插入要插入排序序列的记录}
结束；
结束；
开始
assign(fin，' input . txt ')；
复位(鳍)；
readln(fin，n)；
for i:=1到n do read(fin，a[I])；
write('排序前:')；
对于i:=1到n做写(a[I]:5)；writeln
in sort(a，n)；
write('排序后:')；
对于i:=1到n做写(a[I]:5)；writeln
关闭(鳍)；
readln
结束。
合并排序[Pascal]
类型元素=数组[0..10001]的整数；
var arrhead，arrend:longint；
n，I:longint；
a:元素；
过程合并(var a:element；x，y，z:longint)；
var temp1，temp 2:element；
lengthA，lengthB，I，j，count:longint；
开始
对于i:=x到y do temp 1[I-x+1]:= a[I]；
对于j:=y+1到z do temp 2[j-y]:= a[j]；
length a:= y-x+1；
length b:= z-y；
I:= 1；j:= 1；计数:= x-1；
while(我& lt=lengthA)和(j & lt=长度B) do
开始
inc(计数)；
if temp 1[I]& gt；temp2[j]然后开始一个[计数]:= temp 2[j]；Inc(j)；结束
否则开始一个[count]:= temp 1[I]；inc(一)；结束；
结束；
如果我& gtlengthA然后for i:=j to lengthB做a[count+i-j+1]:=temp2[i]
else for j:=i to lengthA做a[count+j-I+1]:= temp 1[j]；
结束；
过程排序(变量a:元素；x，y:longint)；
var mid:longint；
开始
mid:=(x+y)div 2；
如果mid & lt& gtx然后排序(a，x，mid)；
如果mid+1 & lt；& gty然后排序(a，mid+1，y)；
merge(a，x，mid，y)；
结束；
开始
读作(n)；
对于i:=1到n做read(a[I])；
arr head:= 1；
arrend:= n；
sort(a，arrhead，arrend)；
对于i:=1到n do begin write(a[i]，' ')；如果i mod 5=0，那么writeln结束；
结束。
气泡分类
过程冒泡排序(变量R:文件类型)
开始
对于i:=1到n-1 do // Do N-1次排序。
no swap:= true；//交换符号
对于j:=n-1 downto i do //从后向前扫描。
如果R[j+1]。key & ltR[j]。那就按键
temp:= R[j+1]；
R[j+1]:= R[j]；
r[j]:= temp；
noswap:=false
endif
endfor
如果没有交换，则//如果没有交换发生，则停止算法。
返回；
endif
结束
结束；
直接选择排序
过程select sort(var R:filetype)；
开始
对于i:=1到n-1 do
k:= I；
对于j:=i+1到n do
如果R[j]。key & ltR[k]。那就按键
k:=j
endif
endfor
如果k不等于I那么//靠，不能用那个符号，屏蔽够了。
temp:R[I]；
R[I]:= R[k]；
r[k]:=温度
endif
结束
结束；
堆排序的Pascal实现
//这个程序实现了一个小根堆(满足父比子小的天性)
//程序实现的功能有:堆排序，取最小元素。
//数组最终将按降序排序。
const maxn = 1000；
var a:array[1..maxn]of longint；
尺寸:longint
I，n:longint；
过程交换(var a，b:longint)；
var t:longint；
开始
t:= a；
a:= b；
b:= t；
结束；
过程插入(x:longint)；
var p:longint；
开始
inc(大小)；
p:=大小；
while (a[p div 2]>x)和(p & gt1)开始吧
a[p]:= a[p div 2]；
p:= p div 2；
结束；
a[p]:= x；
结束；
过程堆(idx:longint)；
var l，r，low:longint；
开始
l:= 2 * idx；
r:= 2 * idx+1；
if(a[l]& lt；a[idx])和(l & lt=size)然后低:=l
else低:= idx
if(a[r]& lt；a[低])和(r & lt=size)那么低:= r；
如果idx & lt& gt●然后开始
swap(a[idx]，a[low])；
heapfy(低)；
结束；
结束；
函数getmin:longint；
开始
退出(a[1])；
结束；
函数pop:longint；
开始
pop:= a[1]；
a[1]:= a[size]；
dec(大小)；
heap fy(1)；
结束；
开始
readln(n)；
大小:= 0；
对于i:=1到n do
插入(随机(1000))；
对于i:=1到n do
a[n-I+1]:= pop；
对于i:=1到n做写(a[i]，' ')；
writeln
结束。