快速排序的PASCAL程序是什么啊？最好有思想

分类: 电脑/网络 >>程序设计 >>其他编程语言

解析:

procedure sort(l,r:longint)

var i,j,x,y:longint

begin

i:=l

j:=r

x:=b[(i+j) div 2]

repeat

while x>b[i] do inc(i)

while b[j]>x do dec(j)

if not (i>j) then

begin

y:=b[i]

b[i]:=b[j]

b[j]:=y

inc(i)

dec(j)

end

until i>j

if i<r then sort(i,r)

if l<j then sort(l,j)

end

这是我刚编的，这个过程是对于数组b进行快排。在主程序中sort(1,n）就可以排序了。

具体的思想嘛，我在网上找了一下，这个说得是对的：

快速排序是对冒泡排序的一种改进。它的基本思想是：通过一躺排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一不部分的所有数据都要小，然后再按次方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

假设要排序的数组是A[1]……A[N]，首先任意选取一个数据（通常选用第一个数据）作为关键数据，然后将所有比它的数都放到它前面，所有比它大的数都放到它后面，这个过程称为一躺快速排序。一躺快速排序的算法是：

1）、设置两个变量I、J，排序开始的时候I：=1，J：=N；

2）以第一个数组元素作为关键数据，赋值给X，即X：=A[1]；

3）、从J开始向前搜索，即由后开始向前搜索（J：=J-1），找到第一个小于X的值，两者交换；

4）、从I开始向后搜索，即由前开始向后搜索（I：=I+1），找到第一个大于X的值，两者交换；

5）、重复第3、4步，直到I=J；

例如：待排序的数组A的值分别是：（初始关键数据X：=49）

A[1] A[2] A[3] A[4] A[5] A[6] A[7]：

49 38 65 97 76 13 27

进行第一次交换后： 27 38 65 97 76 13 49

( 按照算法的第三步从后面开始找

进行第二次交换后： 27 38 49 97 76 13 65

( 按照算法的第四步从前面开始找>X的值，65>49,两者交换，此时I：=3 )

进行第三次交换后： 27 38 13 97 76 49 65

( 按照算法的第五步将又一次执行算法的第三步从后开始找

进行第四次交换后： 27 38 13 49 76 97 65

( 按照算法的第四步从前面开始找大于X的值，97>49,两者交换，此时J：=4 )

此时再执行第三不的时候就发现I=J，从而结束一躺快速排序，那么经过一躺快速排序之后的结果是：27 38 13 49 76 97 65，即所以大于49的数全部在49的后面，所以小于49的数全部在49的前面。

快速排序就是递归调用此过程——在以49为中点分割这个数据序列，分别对前面一部分和后面一部分进行类似的快速排序，从而完成全部数据序列的快速排序，最后把此数据序列变成一个有序的序列，根据这种思想对于上述数组A的快速排序的全过程如图6所示：

初始状态 {49 38 65 97 76 13 27}

进行一次快速排序之后划分为 {27 38 13} 49 {76 97 65}

分别对前后两部分进行快速排序 {13} 27 {38}

结束 结束 {49 65} 76 {97}

49 {65} 结束

结束

图6 快速排序全过程

1）、设有N（假设N=10）个数，存放在S数组中；

2）、在S[1。。N]中任取一个元素作为比较基准，例如取T=S[1]，起目的就是在定出T应在排序结果中的位置K，这个K的位置在：S[1。。K-1]<=S[K]<=S[K+1..N]，即在S[K]以前的数都小于S[K]，在S[K]以后的数都大于S[K]；

3）、利用分治思想（即大化小的策略）可进一步对S[1。。K-1]和S[K+1。。N]两组数据再进行快速排序直到分组对象只有一个数据为止。

如具体数据如下，那么第一躺快速排序的过程是：

数组下标： 1 2 3 4 5 6 7 8 9 10

45 36 18 53 72 30 48 93 15 36

I J

（1） 36 36 18 53 72 30 48 93 15 45

（2） 36 36 18 45 72 30 48 93 15 53

（3） 36 36 18 15 72 30 48 93 45 53

（4） 36 36 18 15 45 30 48 93 72 53

（5） 36 36 18 15 30 45 48 93 72 53

通过一躺排序将45放到应该放的位置K，这里K=6，那么再对S[1。。5]和S[6。。10]分别进行快速排序。

快速排序又称划分交换排序。 它的基本思想是，通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键宇均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。具体做法是在当前无宽罩序区R[1]到R[h]中任取一个记录作为比较的“基准”(不妨记为temp), 用此基准将当前无序区划分为左右两个较小的无序子区：R[1]到R[i-1]和R[i+1]到R[h]，且左边的无序子区中记录的关键字均小于或等于基准temp的关键字，右边的无序子区中记录的关键字均大于或等于基准temp的关键字，而基准temp则位于最终排序的位置上,即：R[1]到R[i-1]中关键字<=temp.key<=R[i+1]到R[h]的关键字(1<=i<=h)。当R[1]到R[i-1]和R[i+1]到R[h]均非空时，分别对它们进行上述的划分过程,直至所有无序子区中记录均已排好序为止。下面是快速排序的过程。方括号表示无序区，上下划线表示基准temp的关键字，它未参加真正的交换，只是在划分完成时才将它放入正确的位置上。

初始关键字： [49 38 65 97 76 13 27 49’] 一趟排序之后： [27 38 13] 49 [76 97 65 49’] 二趟排序之后： [13] 27 [38] 49 [49’ 65] 76 [97] 三趟排序之后： 13 27 38 49 49’ [65] 76 97 最后的排序结果： 13 27 38 49 49’ 65 76 97 对当前无序区R[1]到R[h]的划分具体做法： 设置两个指针i和j,它们的初值分为i=1和j=h.不妨取基准为无序的第1个记录R[i](即R[1]),并将它保存在变量temp 中。令j自h起向左扫描，直到找到第1个关键字小于 temp.key的记录R[j]，将R[j]移至i所指的位知蔽置上(这相当于交换了R[j]和基准R[i](即temp)的位置，使关键字小于基准关键字的记录移到了基准的左边)；然后，令i自i+1起向右扫描，直至找到第1个关键字大于temp.key的记录R[i],将R[i]移至j指的位置上(这相当于交换了R[i]和基准R[j](即temp)的位置，使关键字大于基准关键字的记录移到了基准的右边)；接着，令j自j-1起向左扫描，如此交替改变扫描方向，从两端各自往中间靠拢，直至i=j时，i便是基准temp的最终位置，将temp放在此位置上就完成了一次划分 。算法可描述如下：Procedure Parttion(Var R : FileTypeL, H : IntegerVar I : Integer)

{对无序区R[L,H]做划分，执行算法之后，求得I（L<=I<=H），I为本次划分后已被定位的基准元素的位置。若L<I，则R[L..I-1]中记录的关键字均不大于R[I]的关键字，若I<H，则R[I+1..H]中记录的关键字均不小于R[I]的关键字， }

Begin

I := LJ := Htemp:= R[I] {初始化，temp为基准元素}

Repeat

While (R[J] >=temp) And (I <J) Do

J := J - 1{从右向左扫描，查找第一个小搭巧州于 temp的元素}

If I <J Then {已找到R[J] 〈temp}

begin

R[I] := R[J]{相当于交换R[I]和R[J]}

I := I + 1

end

While (R[I] <= temp) And (I <J) Do

I := I + 1 {从左向右扫描，查找第一个大于 temp的元素}

If I <J Then {已找到R[I] >temp }

begin R[J] := R[I]{相当于交换R[I]和R[J]}

J := J - 1

end

Until I = J

R[I] := temp {基准temp已被最终定位}

End{Parttion }Procedure QuickSort(Var R :FileTypeS,T: Integer){对R[S..T]快速排序}

Begin

If S <T Then {当R[S..T]为空或只有一个元素是无需排序}

begin

Parttion(R, S, T, I){对R[S..T]做划分}

QuickSort(R, S, I-1){递归处理左区间R[S,I-1]}

QuickSort(R, I+1,T){递归处理右区间R[I+1..T] }

end

End{QuickSort} 这是我的资料，你看看有用么？

---