快排么。网上一搜就一堆了。算法只是一种思想或说成一种方法而已，并非就C语言。其它语言也一样
快排也有点像二路归并：从一个无序的序列中随机取出一个值q做为支点,然后把大于q的放到一边，小于q的放到q的另一边,然后再以q为分界点，分别对q的两边
进行排序（快排时直接再对q两边重新取支点，整理，再取支点，...直到支点两旁都有序。也就是支点两旁只有一个数时）
*/
#include <stdio.h>
#include <stdlib.h>
int Qsort(int p[],int beg,int end)
{
if(beg+1>=end)return 0//退出递归
int low,hight,q
low=beg
hight=end
q=p[low]//q为支点，其实q可以为随机数。但相应以下程序就要改了
while(1){
while(low<hight &&p[hight]>q)hight--
if(low>=hight)break
p[low++]=p[hight]
while(low<hight &&p[low]<q)low++
p[hight++]=p[low]
}
p[low]=q
Qsort(p,beg,low-1)
Qsort(p,low+1,end)
}
int main()
{
int i,a[]={1,32,6,4,54,654,6,6,2,76,76,7,66,5,544,334,34,78}
Qsort(a,0,sizeof(a)/4-1)
for(i=0i<sizeof(a)/4i++)printf(" %d ",a[i])
system("pause")
return 0
}
快速排序的优势和支点元素的选择有关系。
所选支点元素每次递归后都在最前面或最后面。这样情况就会最差了。
我们知道一般的排序。（如冒泡。。）在一个数组p[m,n]中排序。都是确定最大或最小，而确定最大值（最小值）要经过n-m-1次比较。
而整个过程就差不多是(n-m-1)!次比较。
快排中：一次比较可以确定支点元素的位置。若p[m,q,n](q为支点元素）。当然确定第一个元素也是要比较（n-m-1)次。但第二个，第三个（第二层）就是(q-m-1)和(n-q-1)次比较。
明显q的值若为m或n，快排就没有什么优势了
看了LS的回答，还是我水平最高嘛……喔厚厚厚……希望采纳！鞠躬……
我写的是根比叶子大的堆，siftup 是顶堆（就是新来的数据向上，直到它的父亲比自己大，或自己是
堆的根）
程序是对输入数据边读边排的：
program duipai
var
a:array[1..100000]of longint
n:longint
procedure siftup(i:longint)
var
j,b:longint
begin
b:=a[i]
while i>1 do
begin
j:=i shr 1
if a[j]<b then
begin
a[i]:=a[j]
i:=j
end
else break
end
a[i]:=b
end
procedure init
begin
assign(input,'a.in')reset(input)
n:=1
while not seekeof do
begin
read(a[n])
siftup(n)
inc(n)
end
dec(n)
close(input)
end
procedure ansit
var
i:longint
begin
for i:=1 to n do write(a[i],' ')writeln
end
begin
init
ansit
end.
下面的是把最下面的叶子放到堆根上再向下压的程序：
procedure siftdown
var
b,i,j:longint
begin
b:=a[1]i:=1
while i<=n do
begin
j:=i*2
if j>n then break
if (j<n)and(a[j+1]>a[j])then inc(j)
if a[j]>b then
begin
a[i]:=a[j]i:=j
end
else break
end
a[i]:=b
end
如果要改变堆中数据大小顺序，只要改变a[]与b 的比较符号即可
这是快排：
procedure sort(l,r:longint)
var
i,j,t,temp:longint
begin
i:=lj:=rtemp:=a[(i+j)shr 1]
while i<=j do
begin
while a[j]>temp do dec(j)
while a[i]<temp do inc(i)
if i<=j then
begin
t:=a[i]a[i]:=a[j]a[j]:=t
inc(i)dec(j)
end
end
if l<j then sort(l,j)
if i<r then sort(i,r)
end
这是归并排序：
program guibing
var
a,temp:array[1..100000]of longint
n:longint
procedure init
begin
assign(input,'a.in')reset(input)
n:=1
while not eof do
begin read(a[n])inc(n)end
dec(n)
close(input)
end
procedure sort(l,r:longint)
var
i,j,p,mid:longint
begin
if l=r then exit
mid:=(l+r)shr 1
sort(l,mid)
sort(mid+1,r)
i:=lj:=mid+1p:=l
while (i<=mid)or(j<=r)do
begin
if (i<=mid)and(j<=r)then
begin
if a[i]<a[j] then
begin temp[p]:=a[i]inc(i)end
else begin temp[p]:=a[j]inc(j)end
end
else
begin
if i<=mid then begin temp[p]:=a[i]inc(i)end
else begin temp[p]:=a[j]inc(j)end
end
inc(p)
end
for i:=l to r do a[i]:=temp[i]
end
procedure ansit
var
i:longint
begin
for i:=1 to n do write(a[i],' ')writeln
end
begin
init
sort(1,n)
ansit
end.
压堆是为了删掉最上面的根再找到新的最大的根而用的，
如果初始状态不是已经排好的根堆，压堆不会使其成为
一个根堆，而顶堆 *** 作则可生成堆．
我的哪个程序有错？
你需要哪个排序的解释？
快排：
在数组中找一个数，使它左边的数都小于它，右边的数都大于它，并找
到这个数的位置，明显是把整个数组排好序后的位置（记为mid).。再更深一层的
递归，即sort(l,mid-1)sort(mid+1)对这个数左右两边的数再排序，道理一
样，直到处理的数只剩下一个。具体实现你自己F7单步模拟一下吧。
归并：
将数组中的数均分的两部分有序的数归进一个暂时的数组中，从两
部分的起点开始，对当前的两个数比较，哪个小就把哪个送进暂时数组，并
让它在原数组中的下一个数参与下一次比较，直到两部分数全部进入暂时数
组后，将暂时数组的数据覆盖原数组中的数据，使其有序。因为均分的两部
分不一定是有序的，所以要先递归到底，即一个数，在不断回溯时，进行归
并，这时的两部分就是有序的了。
顶堆：
当读入数据时，数据在末尾，这时要不断的向上顶，与它的父亲比较，
直到顶到父亲比自己大或自己在顶点为止，对每一个数据都这样就形成了堆。
压堆：
当最小的数，即堆顶舍弃不用，而需要第二小的数时，就把末尾的数
覆盖到堆顶后向下压，是顶堆的逆过程，即如果叶子比自己小就调换，直到
换不了为止。 *** 作后数据减少一个，但仍是堆。
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）