Question

在排序算法中，是快速排序好还是冒泡排序好？？

这是基于pascal复赛操作中而言，知道的请回答，万分感谢！！

Answer 1

不，应该相对而言，最快的往往是最不稳定的
给你看看下面的各种排序
二叉树排序
program pxtree;
const
a:array[1..8] of integer=(10,18,3,8,12,2,7,3);
type point=^nod;
nod=record
w:integer;
right,left:point ;
end;
var root,first:point;k:boolean;i:integer;
procedure hyt(d:integer;var p:point);
begin
if p=nil then
begin
new(p);
with p^ do begin w:=d;right:=nil;left:=nil end;
if k then begin root:=p; k:=false end;
end
else with p^ do if d>=w then hyt(d,right) else hyt(d,left);
end;
procedure hyt1(p:point);
begin
with p^ do
begin
if left<>nil then hyt1(left);
write(w:4);
if right<>nil then hyt1(right);
end
end;
begin
first:=nil;k:=true;
for i:=1 to 8 do hyt(a[i],first);
hyt1(root);writeln;
end.

我自己做的排序

var a,b,c:array [1..1000] of longint;
i,j,t,x,n:longint;
begin
read(n);
j:=n;
for i:=1 to n do
read(a[i]);
i:=0;
repeat
inc(i);
dec(j);
if a[i]<=a[j] then
begin
t:=a[i];
a[i]:=a[j];
a[j]:=t;
end;
until i=j;
for i:=1 to n do
write(a[i],' ');
end.

气泡排序 （不是冒泡）

procedure Bubblesort (var R:filetype);
begin
for i:=1 to n-1 do
noswap:=true;
for j:=n-1 downto i do
if R[j+1].key < R[j].key then
temp :=R[j+1];
R[j+1]:=R[j];
R[j]:=temp;
noswap:=false
endif
endfor;
if noswap then
return;
endif
endfor
end;
procedure selectsort (var R:filetype);
begin
for i:=1 to n-1 do
k:=i;
for j:=i+1 to n do
if R[j].key < R[k].key then
k:=j
endif
endfor;
if k<>i then
temp:R[i];
R[i]:=R[k];
R[k]:=temp
endif
endfor
end;
主程序自己加吧

冒泡
type element=array[0..10001]of integer;
var arrhead,arrend:longint;
n,i:longint;
a:element;

procedure merge(var a:element;x,y,z:longint);
var temp1,temp2:element;
lengthA,lengthB,i,j,count:longint;

begin
for i:=x to y do temp1[i-x+1]:=a[i];
for j:=y+1 to z do temp2[j-y]:=a[j];
lengthA:=y-x+1;
lengthB:=z-y;
i:=1; j:=1; count:=x-1;
while (i<=lengthA)and(j<=lengthB) do
begin
inc(count);
if temp1[i]>temp2[j] then begin a[count]:=temp2[j]; inc(j); end
else begin a[count]:=temp1[i]; inc(i); end;

end;
if i>lengthA then for i:=j to lengthB do a[count+i-j+1]:=temp2[i]
else for j:=i to lengthA do a[count+j-i+1]:=temp1[j];
end;

procedure sort(var a:element;x,y:longint);
var mid:longint;
begin
mid:=(x+y) div 2;
if mid<>x then sort(a,x,mid);
if mid+1<>y then sort(a,mid+1,y);
merge(a,x,mid,y);
end;

begin
read(n);
for i:=1 to n do read(a[i]);
arrhead:=1;
arrend:=n;
sort(a,arrhead,arrend);
for i:=1 to n do begin write(a[i],' '); if i mod 5=0 then writeln; end;
end.

并归排序

type element=array[0..10001]of integer;
var arrhead,arrend:longint;
n,i:longint;
a:element;

procedure merge(var a:element;x,y,z:longint);
var temp1,temp2:element;
lengthA,lengthB,i,j,count:longint;

begin
for i:=x to y do temp1[i-x+1]:=a[i];
for j:=y+1 to z do temp2[j-y]:=a[j];
lengthA:=y-x+1;
lengthB:=z-y;
i:=1; j:=1; count:=x-1;
while (i<=lengthA)and(j<=lengthB) do
begin
inc(count);
if temp1[i]>temp2[j] then begin a[count]:=temp2[j]; inc(j); end
else begin a[count]:=temp1[i]; inc(i); end;

end;
if i>lengthA then for i:=j to lengthB do a[count+i-j+1]:=temp2[i]
else for j:=i to lengthA do a[count+j-i+1]:=temp1[j];
end;

procedure sort(var a:element;x,y:longint);
var mid:longint;
begin
mid:=(x+y) div 2;
if mid<>x then sort(a,x,mid);
if mid+1<>y then sort(a,mid+1,y);
merge(a,x,mid,y);
end;

begin
read(n);
for i:=1 to n do read(a[i]);
arrhead:=1;
arrend:=n;
sort(a,arrhead,arrend);
for i:=1 to n do begin write(a[i],' '); if i mod 5=0 then writeln; end;
end.

插入排序

const max=100;
type arr=array[0..max]of integer;
var a:arr;
i,n:integer;
fin:text;
procedure InsSort(var r:arr; rn:integer);
var i,j:integer;
begin
for i:=2 to rn do
begin
r[0]:=r[i];
j:=i-1;
while(r[0]<r[j]) do
begin
r[j+1]:=r[j];
dec(j);
end;
r[j+1]:=r[0];
end;
end;

begin
assign(fin,'input.txt');
reset(fin);
readln(fin,n);
for i:=1 to n do read(fin,a[i]);
write('before sort:');
for i:=1 to n do write(a[i]:5); writeln;
InsSort(a,n);
write('after sort: ');
for i:=1 to n do write(a[i]:5); writeln;
close(fin);
readln;
end.

堆排
const maxn=1000;
var a:array[1..maxn] of longint;
size:longint;
i,n:longint;
procedure swap(var a,b:longint);
var t:longint;
begin
t:=a;
a:=b;
b:=t;
end;
procedure insert(x:longint);
var p:longint;
begin
inc(size);
p:=size;
while (a[p div 2]>x) and (p>1) do begin
a[p]:=a[p div 2];
p:=p div 2;
end;
a[p]:=x;
end;
procedure heapfy(idx:longint);
var l,r,low:longint;
begin
l:=2*idx;
r:=2*idx+1;
if (a[l]<a[idx]) and (l<=size) then low:=l
else low:=idx;
if (a[r]<a[low]) and (r<=size) then low:=r;
if idx<>low then begin
swap(a[idx],a[low]);
heapfy(low);
end;
end;
function getmin:longint;
begin
exit(a[1]);
end;
function pop:longint;
begin
pop:=a[1];
a[1]:=a[size];
dec(size);
heapfy(1);
end;
begin
readln(n);
size:=0;
for i:=1 to n do
insert(random(100));
for i:=1 to n do
a[n-i+1]:=pop;
for i:=1 to n do
write(a[i],' ');
writeln;
end.

至于哪个速度快些就自己去试试吧

Answer 2

快速排序好。
快速排序、堆排序是基于比较的排序方法中最好的。还有归并排序。他们都是O(nlogn)的。
冒泡法、插入排序、选择排序都是基本排序，O(n*n)的。Shell排序做了些改进。

不是基于比较的排序方法典型的是计数排序和桶排序，O(n)，能达到线性时间下界。

Answer 3

当然是快速了，快速平均时间o(nlogn)，冒泡平均时间o(n^2)，空间都是o(1)

Answer 4

冒泡的时间复杂度不管好坏情况都是O(n的平方)，而插入排序在最好情况下是O(n)，最坏情况是是O(n的平方)。但是平均情况下，插入排序比冒泡排序复杂度要低。